Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- #define endl '\n'
- #define st first
- #define nd second
- #define pb push_back
- #define db(x) cout << #x << " == " << (x) << endl
- #define dbs(x) cout << x << endl
- typedef long long ll;
- typedef vector <int> vi;
- typedef pair <int, int> pii;
- const int N = 4e5+5;
- int bit[N];
- int n, cnt=0;
- map <int, int> cp, id;
- vector <pii> read;
- vi val;
- void add(int p){
- for(; p<=cnt; p+=p&(-p)) bit[p]++;
- }
- int sum(int p){
- int ans=0;
- for(; p>=1; p-=p&(-p)) ans+=bit[p];
- return ans;
- }
- int main(){
- ios_base::sync_with_stdio(0);
- cin.tie(0);
- cin >> n;
- vector <pii> read;
- vi ans(n+1);
- int a, b;
- for(int i=1; i<=n; i++){
- cin >> a >> b;
- read.pb(make_pair(b,a));
- val.pb(a);
- val.pb(b);
- id[a]=i;
- }
- sort(val.begin(), val.end());
- for(auto v: val) cp[v]=++cnt;
- sort(read.begin(), read.end());
- for(auto p: read){
- add(cp[p.nd]);
- ans[id[p.nd]]=sum(cp[p.st]) - sum(cp[p.nd]-1);
- }
- for(int i=1; i<=n; i++) cout << ans[i]-1 << endl;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement