Submission #1144098

#	Time	Username	Problem	Language	Result	Execution time	Memory
1144098		0pt1mus23	Osumnjičeni (COCI21_osumnjiceni)	C++20	30 / 110	1100 ms	300760 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define int long long int
#define ins insert
#define pb  push_back
#define pii pair<int,int>
#define endl '\n' 
#define all(x) x.begin(),x.end()

const int mod = 998244353;
const int inf = INT_MAX;
const int LG  = 23;
const int sze = 2e5+23;

struct segtreeMAX{
    vector<pii> T;
    segtreeMAX(int n){
        T.resize(4*n,{-inf,-inf});
    }
    void upd(int node,int idx,int l,int r,pii v){
        if(l==r){
            T[node]=v;
            return;
        }
        int mid = (l+r)/2;
        if(idx<=mid) upd(2*node,idx,l,mid,v);
        else upd(2*node +1,idx,mid+1,r,v);

        T[node]=max(T[node*2],T[node *2+1]);
    }
    pii qry(int node,int l,int r,int lx,int rx){
        if(lx>r || rx<l) return {-inf,-inf  };
        if(lx>=l && rx<=r) return T[node];
        return max( qry(2*node,l,r,lx,(lx+rx)/2), qry(2*node +1,l,r,(lx+rx)/2 +1, rx) );
    }
};
struct segtreeMIN{
    vector<pii> T;
    segtreeMIN(int n){
        T.resize(4*n,{inf,inf});
    }
    void upd(int node,int idx,int l,int r,pii v){
        if(l==r){
            T[node]=v;
            return;
        } 
        int mid = (l+r)/2;
        if(idx<=mid) upd(2*node,idx,l,mid,v);
        else upd(2*node +1,idx,mid+1,r,v);

        T[node]=min(T[node*2],T[node *2+1]);
    }
    pii qry(int node,int l,int r,int lx,int rx){
        if(lx>r || rx<l) return {inf,inf};
        if(lx>=l && rx<=r) return T[node];
        return min( qry(2*node,l,r,lx,(lx+rx)/2), qry(2*node +1,l,r,(lx+rx)/2 +1, rx) );
    }
};

int dp[LG][sze];

void fast(){
    int n;
    cin>>n;
    vector<pii> arr(n);
    map<int,int> cp;
    for(int i=0;i<n;i++){
        cin>>arr[i].first>>arr[i].second;
        cp[arr[i].first]++;
        cp[arr[i].second]++;
    }
    int c=0;
    for(auto &v:cp){
        v.second = (c++);
    }
    for(int i=0;i<n;i++){
        arr[i].first = cp[arr[i].first];
        arr[i].second = cp[arr[i].second];
        // cout<<arr[i].first<<" "<<arr[i].second<<endl; 
    }
    int M = n*10;
    segtreeMAX st1(M+23); // [0, L] {R,i}
    segtreeMIN st2(M+23); // [R, N] {L,i}
    int r = n;

    for(int i=n-1;i>=0;i--){
        while(true){
            pii it = st1.qry(1,0,arr[i].first,0,M);
            if(it.first >=arr[i].first ){
                r = min(r,it.second);
                st1.upd(1,arr[it.second].first,0,M,{-inf,-inf});
            }
            else{
                break;
            }
        }
        while(true){
            pii it = st1.qry(1,arr[i].first,arr[i].second,0,M);
            // cout<<it.first<<endl;
            if(it.first != (-inf)){
                r=min(r,it.second);
                st1.upd(1,arr[it.second].first,0,M,{-inf,-inf});
            }
            else{
                break;
            }
        }
        while(true){
            pii it = st2.qry(1,arr[i].second,M,0,M);
            if(it.first <= arr[i].second){
                r=min(r, it.second );
                st2.upd(1,arr[it.second].second,0,M,{inf,inf});
            }
            else{
                break;
            }
        }

        dp[0][i]=r;
        st1.upd(1,arr[i].first,0,M,{arr[i].second,i});
        st2.upd(1,arr[i].second,0,M,{arr[i].first,i});
    }
    // cout<<dp[0][1]<<endl;
    dp[0][n]=n;
    for(int i= 1;i<LG;i++){
        for(int j=0;j<=n;j++){
            if(j==n){
                dp[i][j]=n;
            }
            else{
                dp[i][j]=dp[i-1][ dp[i-1][j] ];
            }
        }
    }
    // cout<<dp[17][0]<<endl;
    int q;
    cin>>q;
    while(q--){
        int l,r;
        cin>>l>>r;
        --l;
        --r;
        int ans=0;
        for(int i = LG-1;i>=0;i--){
            if( dp[i][l] <= r ){
                // cout<<i<<endl;
                ans|=(1<<i);
                l = dp[i][l];   
            }    
        }
        cout<<ans+1<<endl;
    }



}

signed main(){
    // ios::sync_with_stdio(false);
    // cin.tie(nullptr);
    
    int tt =1;

    // cin>>tt;
    while(tt--){
        fast();
    }

    return 0;
}

• Subtask 1: 0 / 10
• Subtask 2: 10 / 10
• Subtask 3: 20 / 20
• Subtask 4: 0 / 20
• Subtask 5: 0 / 50