Submission #1028922

#	Time	Username	Problem	Language	Result	Execution time	Memory
1028922		vjudge1	Osumnjičeni (COCI21_osumnjiceni)	C++17	110 / 110	538 ms	31272 KiB

Main

#include <bits/stdc++.h>
using namespace std;

#define ll long long
int const N=2e5+5;
int const mod=1e9+7;

set<pair<int,int>> st;
pair<int,int> a[N];
int par[N][18];

bool check(int i){
    if(st.find(a[i])!=st.end())
        return 0;
    st.insert(a[i]);
    auto p=st.lower_bound(a[i]);
    p++;
    bool ok=1;
    if(p!=st.end()){
        auto nxt=*p;
        if(nxt.first<=a[i].second)
            ok=0;
    }
    p--;
    if(p!=st.begin()){
        p--;
        auto nxt=*p;
        if(nxt.second>=a[i].first)
            ok=0;
    }
    if(ok==0)
        st.erase(a[i]);
    return ok;
}

int main(){
    int n;
    cin>>n;
    for (int i = 1; i <=n; ++i)
        cin>>a[i].first>>a[i].second;
    int j=1;
    for(int i=1;i<=n;i++){
        while(j<=n and check(j))
            j++;
        par[i][0]=j;
        // cout<<j<<' ';
        st.erase(a[i]);
    }
    // cout<<endl;
    par[n+1][0]=n+1;
    for(int p=1;p<18;p++)
        for(int i=1;i<=n+1;i++)
            par[i][p]=par[par[i][p-1]][p-1];
    int q;
    cin>>q;
    while(q--){
        int u,v;
        cin>>u>>v;
        int ans=0;
        for(int p=17;p>=0;p--){
            // cout<<u<<' ';
            if(par[u][p]<=v){
                u=par[u][p];
                ans+=(1<<p);
            }
        }
        // cout<<endl;
        cout<<ans+1<<endl;
    }
    return 0;
}

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