fork download
copy 
  1. #include <cstdio>
  2. #include <algorithm>
  3. #include <map>
  4.  
  5. using namespace std;
  6.  
  7. struct coder{
  8.     int x,y,id;
  9.  
  10.     coder(){}
  11.     coder(int _x, int _y, int _id) :
  12.         x(_x), y(_y), id(_id){}
  13.  
  14.     bool operator < (coder X)const{
  15.         if(x != X.x) return x < X.x;
  16.         return y < X.y;
  17.     }
  18. }a[300000];
  19.  
  20. int ans[300000],bit[100001];
  21.  
  22. void update(int idx){
  23.     for(int x = idx;x <= 100000;x += x & -x)
  24.         ++bit[x];
  25. }
  26.  
  27. int query(int idx){
  28.     int ret = 0;
  29.  
  30.     for(int x = idx;x > 0;x -= x & -x)
  31.         ret += bit[x];
  32.  
  33.     return ret;
  34. }
  35.  
  36. int main(){
  37.     int N;
  38.  
  39.     scanf("%d",&N);
  40.  
  41.     for(int i = 0;i < N;++i){
  42.         scanf("%d %d",&a[i].x,&a[i].y);
  43.         a[i].id = i;
  44.     }
  45.  
  46.     sort(a,a + N);
  47.  
  48.     for(int i = 0;i < N;){
  49.         int e = i;
  50.  
  51.         while(e < N && a[e].x == a[i].x && a[e].y == a[i].y) ++e;
  52.  
  53.         for(int j = i;j < e;++j)
  54.             ans[ a[j].id ] = query(a[j].y);
  55.  
  56.         for(int j = i;j < e;++j)
  57.             update(a[j].y);
  58.  
  59.         i = e;
  60.     }
  61.  
  62.     for(int i = 0;i < N;++i)
  63.         printf("%d\n",ans[i]);
  64.  
  65.     return 0;
  66. }
Success #stdin #stdout 0s 8180KB
comments (?)
stdin
copy 
9
100 862
100 1014
100 1033
1075 200
300 1568
200 1656
200 2600
300 2575
300 1798
stdout
copy 
0
1
2
0
3
3
4
6
5
https://ideone.com/v6LBMt
language:
C++ (gcc 8.3)
created:
9 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!