CSES – Nested Ranges Check

#include<bits/stdc++.h>
#define int long long
#define pii pair<int,int>
#define f first
#define s second
#define fastio ios_base::sync_with_stdio(0);cin.tie(0)
using namespace std;
//declare
const int maxn = 2e5+5;
int n,L[maxn],R[maxn],ans1[maxn],ans2[maxn],bit[2*maxn];
vector<int> v;
void disc(){
    for(int i=0;i<n;i++) v.push_back(L[i]), v.push_back(R[i]);
    sort(v.begin(),v.end());
    v.erase(unique(v.begin(),v.end()), v.end());
    for(int i=0;i<n;i++){
        L[i] = lower_bound(v.begin(),v.end(),L[i]) - v.begin();
        R[i] = lower_bound(v.begin(),v.end(),R[i]) - v.begin();
    }
}
int lowbit(int x){
    return x & (-x);
}
void modify(int x){
    for(int i=x; i<2*maxn; i += lowbit(i)){
        bit[i]++;
    }
}
int query(int x){
    int ret = 0;
    for(int i=x; i>0; i -= lowbit(i)){
        ret += bit[i];
    }
    return ret;
}
signed main(){
    fastio;
    cin>>n;
    for(int i=0;i<n;i++) cin>>L[i]>>R[i];
    disc();
    vector<int> ord(n); iota(ord.begin(),ord.end(),0);
    sort(ord.begin(),ord.end(),[](int i,int j){
        if(L[i] == L[j]) return R[i] > R[j];
        return L[i] < L[j];
    });
    int sum = 0;
    for(int i:ord){
        ans2[i] = sum - query(R[i]-1);
        modify(R[i]);
        sum++;
    }
    for(int i=1;i<2*maxn;i++) bit[i] = 0;
    reverse(ord.begin(),ord.end());
    for(int i:ord){
        ans1[i] = query(R[i]);
        modify(R[i]);
    }
    for(int i=0;i<n;i++) cout<<(bool)ans1[i]<<" ";
    cout<<"\n";
    for(int i=0;i<n;i++) cout<<(bool)ans2[i]<<" ";
    cout<<"\n";
    return 0;
}