fork(1) download
copy 
  1. #include<cstdio>
  2. #include<iostream>
  3. #include<algorithm>
  4. #include<string>
  5. #include<cstring>
  6. #include<vector>
  7. #include<stack>
  8. #include<queue>
  9. #include<deque>
  10. #include<map>
  11. #include<set>
  12. #include<limits>
  13. #include<climits>
  14. #include<cmath>
  15. #include<functional>
  16. #include<ctime>
  17. #include<cstdlib>
  18. #include<fstream>
  19. #include<typeinfo>
  20.  
  21. using namespace std;
  22.  
  23. typedef long long int ll;
  24. typedef unsigned long long int u64;
  25. typedef unsigned u32;
  26.  
  27. struct bit
  28. {
  29.     int a[1<<17];
  30.     void Initialize()
  31.     {
  32.         memset(a,0,sizeof(a));
  33.     }
  34.     void Update(int pos, int val)
  35.     {
  36.         for(;pos<=100000;pos+=pos&(-pos))
  37.             a[pos]+=val;
  38.     }
  39.     int Query(int pos)
  40.     {
  41.         int ans=0;
  42.         for(;pos>=1;pos-=pos&(-pos))
  43.             ans+=a[pos];
  44.         return ans;
  45.     }
  46. }it;
  47.  
  48. struct coder
  49. {
  50.     int a,h,number;
  51.     coder(){}
  52.     coder(int x, int y)
  53.     {
  54.         a=x;
  55.         h=y;
  56.     }
  57.     bool operator<(const coder &x) const
  58.     {
  59.         if(a<x.a)
  60.             return true;
  61.         if(a>x.a)
  62.             return false;
  63.         return h<x.h;
  64.     }
  65.     bool operator==(const coder &x) const
  66.     {
  67.         return (a==x.a && h==x.h);
  68.     }
  69. };
  70.  
  71. map <coder,int> m;
  72. coder a[1<<19];
  73. int ans[1<<19];
  74. int n;
  75.  
  76. void input()
  77. {
  78.     scanf("%d", &n);
  79.     int i;
  80.     for(i=1;i<=n;i++)
  81.     {
  82.         scanf("%d %d", &a[i].a, &a[i].h);
  83.         a[i].number=i;
  84.     }
  85. }
  86.  
  87. void solve()
  88. {
  89.     it.Initialize();
  90.     sort(a+1,a+1+n);
  91.     int i;
  92.     for(i=1;i<=n;i++)
  93.     {
  94.         ans[a[i].number]=it.Query(a[i].h)-m[a[i]];
  95.         m[a[i]]++;
  96.         it.Update(a[i].h,1);
  97.     }
  98.     for(i=1;i<=n;i++)
  99.         printf("%d\n", ans[i]);
  100. }
  101.  
  102. int main()
  103. {
  104.     input();
  105.     solve();
  106.     return 0;
  107. }
  108.  
Success #stdin #stdout 0s 11848KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/Jq5ae5
language:
C++14 (gcc 8.3)
created:
11 years ago
visibility:
public

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!