CRATE - Coder Rating
Tác giả: khuc_tuan
Ngôn ngữ: C++
#include <iostream>
#include <algorithm>
#include <cstdio>
using namespace std;
struct Coder {
int a, b;
int id;
bool operator<(Coder c)const {
if(a==c.a) return b < c.b;
else return a < c.a;
}
};
int n;
Coder coder[300030];
int res[300010], bit[100010];
int get(int i) {
int r = 0;
for(;i>0;i-=i&(-i))r+=bit[i];
return r;
}
void update(int i){
for(;i<100010;i+=i&(-i))bit[i]++;
}
int main() {
scanf("%d", &n);
for(int i=0;i<n;++i) {
scanf("%d%d", &coder[i].a, &coder[i].b);
coder[i].id = i;
}
sort(coder,coder+n);
for(int i=0;i<n;++i) {
int j = i;
while(j < n && coder[j].a == coder[i].a) ++j;
--j;
for(int k=i;k<=j;++k) {
res[coder[k].id] += get(coder[k].b+1);
}
for(int k=i;k<=j;++k)
update(coder[k].b+1);
int st = i;
for(int k=i;k<=j;++k) {
while(st <= j && coder[st].b < coder[k].b) ++st;
res[coder[k].id] += st - i;
}
i = j;
}
for(int i=0;i<n;++i) printf("%d\n", res[i]);
return 0;
}