Advertisement
Guest User

Untitled

a guest
Apr 7th, 2020
210
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.24 KB | None | 0 0
  1.     #include <bits/stdc++.h>
  2.     using namespace std;
  3.      
  4.     #define endl '\n'
  5.     #define st first
  6.     #define nd second
  7.     #define pb push_back
  8.     #define db(x) cout << #x  << " == " << (x) << endl
  9.     #define dbs(x) cout << x << endl
  10.     typedef long long ll;
  11.     typedef vector <int> vi;
  12.     typedef pair <int, int> pii;
  13.     const int N = 4e5+5;
  14.      
  15.     int bit[N];
  16.     int n, cnt=0;
  17.     map <int, int> cp, id;
  18.     vector <pii> read;
  19.     vi val;
  20.     void add(int p){
  21.       for(; p<=cnt; p+=p&(-p)) bit[p]++;
  22.     }
  23.      
  24.     int sum(int p){
  25.       int ans=0;
  26.       for(; p>=1; p-=p&(-p)) ans+=bit[p];
  27.       return ans;
  28.     }
  29.      
  30.     int main(){
  31.       ios_base::sync_with_stdio(0);
  32.       cin.tie(0);
  33.       cin >> n;
  34.       vector <pii> read;
  35.       vi ans(n+1);
  36.       int a, b;
  37.       for(int i=1; i<=n; i++){
  38.         cin >> a >> b;
  39.         read.pb(make_pair(b,a));
  40.         val.pb(a);
  41.         val.pb(b);
  42.         id[a]=i;
  43.       }
  44.       sort(val.begin(), val.end());
  45.       for(auto v: val) cp[v]=++cnt;
  46.       sort(read.begin(), read.end());
  47.       for(auto p: read){
  48.         add(cp[p.nd]);
  49.         ans[id[p.nd]]=sum(cp[p.st]) - sum(cp[p.nd]-1);
  50.       }
  51.       for(int i=1; i<=n; i++) cout << ans[i]-1 << endl;
  52.     }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement