Submission #720677

#	Time	Username	Problem	Language	Result	Execution time	Memory
720677		Yell0	Osumnjičeni (COCI21_osumnjiceni)	C++17	110 / 110	318 ms	32852 KiB

Main

#include <bits/stdc++.h>
#define f first
#define s second
using namespace std;
typedef pair<int,int> pii;
const int MN=4e5+5,LOG=20;
int N,Q,st[LOG][MN];
pii a[MN];
set<pii> s;

bool chk(int i) {
    if(s.empty()) return 1;
    auto nxt=s.lower_bound(a[i]);
    if(a[i].f<=nxt->f&&nxt->f<=a[i].s) return 0;
    if(nxt!=s.begin()) {
        nxt--;
        if(nxt->f<=a[i].f&&a[i].f<=nxt->s) return 0;
    }
    return 1;
}

int main() {
    ios::sync_with_stdio(0);cin.tie(0);
    cin>>N;
    for(int i=1;i<=N;i++) cin>>a[i].f>>a[i].s;
    for(int l=1,r=1;l<=N;l++) {
        while(r<=N&&chk(r)) {s.insert(a[r]);r++;}
        st[0][l]=r;
        s.erase(a[l]);
    }
    st[0][N+1]=N+1;
    for(int k=1;k<LOG;k++)
        for(int i=1;i<=N+1;i++) {
            st[k][i]=st[k-1][st[k-1][i]];
        }
    cin>>Q;
    int p,q;
    while(Q--) {
        cin>>p>>q;
        int ans=1;
        for(int k=LOG-1;k>=0;k--)
            if(st[k][p]&&st[k][p]<=q) {
                p=st[k][p];
                ans+=1<<k;
            }
        cout<<ans<<'\n';
    }
    return 0;
}

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