fork download
copy 
  1. // Abhay Singh Bhadoria ( _Asb_ ) //
  2. #include<bits/stdc++.h>
  3. using namespace std;
  4. const int N = 1e5 + 5;
  5. struct S {
  6.     int x, y, pos;
  7.     bool operator < (S a) {
  8.         if(x == a.x) return y < a.y;
  9.         else return x < a.x;
  10.     }
  11. } ratings[3 * N];
  12. int bit[N];
  13. int res[3 * N];
  14. void update(int x) {
  15.     while(x <= 1e5) {
  16.         bit[x]++;
  17.         x += x & (-x);
  18.     }
  19. }
  20. int query(int x) {
  21.     int res = 0;
  22.     while(x > 0) {
  23.         res += bit[x];
  24.         x -= x & (-x);
  25.     }
  26.     return res;
  27. }
  28. int main() {
  29.     ios_base ::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
  30.     int n;
  31.     cin >> n;
  32.     for(int i = 0; i < n; ++i) {
  33.         cin >> ratings[i].x >> ratings[i].y;
  34.         ratings[i].pos = i;
  35.     }
  36.     sort(ratings, ratings + n);
  37.     for(int i = 0; i < n; ++i) {
  38.         int inc = query(ratings[i].y);
  39.         int same = i;
  40.         while(same < n && ratings[i].x == ratings[same].x && ratings[i].y == ratings[same].y) {
  41.             res[ratings[same].pos] = inc;
  42.             update(ratings[i].y);
  43.             ++same;
  44.         }
  45.         i = same - 1;
  46.     }
  47.     for(int i = 0; i < n; ++i) cout << res[i] << '\n';
  48. }
  49.  
Success #stdin #stdout 0s 21144KB
comments (?)
stdin
copy 
8
1798 1832
862 700
1075 1089
1568 1557
2575 1984
1033 950
1656 1649
1014 1473
stdout
copy 
6
0
2
4
7
1
5
1
https://ideone.com/T0rsrx
problem RATING, based on SPOJ submission 19060521 (CPP14), 2017-03-24 20:14:55
language:
C++14 (gcc 8.3)
created:
7 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!