これ色んな解法ありそう。
https://www.hackerrank.com/contests/yfkpo2/challenges/rival
問題
N体のゴリラがいる。
各ゴリラの体力はP[i]であり、自身がライバルとみなす体力の範囲は[L[i],R[i]]である(L[i]≦P[i]≦R[i])。
互いにライバルとみなすようなゴリラの対は何通りか。
解法
同じ体力のゴリラ同士は必ずライバル関係にあるので、まずそれらをカウントする。
Pの取りえる値の範囲が狭いので、これを総当たりしよう。
体力がxであるようなゴリラiのL[i]の集合をL'(x)、R[i]の集合をR'(x)と置くことにする。
L'(x)とR'(x)は先にソートしておく。
さて、体力がxであるゴリラとyであるゴリラが互いに何体かいたとき、条件を満たすのは何通りか考える。
x<yとすると、R'(x)のうちy以上の数と、L'(y)のうちx以下の数の積を取ればよい。
これはそれぞれlower_boundで数え上げることができる。
int N; vector<int> R[1010]; vector<int> L[1010]; void solve() { int i,j,k,l,r,x,y; string s; cin>>N; ll ret=0; FOR(i,N) { cin>>x>>j>>k; ret+=L[x].size(); L[x].push_back(j); R[x].push_back(k); } FOR(i,1001) { sort(ALL(L[i])); sort(ALL(R[i])); } FOR(y,1001) FOR(x,y) { int mor=R[x].size()-(lower_bound(ALL(R[x]),y)-R[x].begin()); int le=lower_bound(ALL(L[y]),x+1)-L[y].begin(); ret+=1LL*le*mor; } cout<<ret<<endl; }
まとめ
これ想定解なんなんだろうな。