Submission #1247077

#	Time	Username	Problem	Language	Result	Execution time	Memory
1247077		ivaziva	Osumnjičeni (COCI21_osumnjiceni)	C++20	0 / 110	87 ms	2624 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#define MAXN 200002
#define MAXM 18

int n,q,l[MAXN],r[MAXN];
int parent[MAXM][MAXN];
set<pair<int,int>> s;

int main()
{
    cin>>n;for (int i=1;i<=n;i++) {cin>>l[i]>>r[i];parent[0][i]=i;}
    int pointer=0;
    for (int i=1;i<=n;i++)
    {
        if (pointer<i) {s.clear();pointer=i;s.insert({l[i],i});}
        while (pointer+1<=n)
        {
            if (s.size()==0) {pointer++;s.insert({l[pointer],pointer});continue;}
            auto it=s.lower_bound({l[pointer+1],0});int pos1=it->second;
            if (l[pointer+1]<=l[pos1] and l[pos1]<=r[pointer+1]) break;
            if (it!=s.begin()) {it--;int pos2=it->second;if (l[pos2]<=l[pointer+1] and l[pointer+1]<=r[pos2]) break;}
            pointer++;s.insert({l[pointer],r[pointer]});
        }
        parent[0][i]=pointer+1;s.erase({l[i],i});
    }
    parent[0][n+1]=n+1;
    for (int j=1;j<MAXM;j++)
    {
        for (int i=1;i<=n+1;i++) parent[j][i]=parent[j-1][parent[j-1][i]];
    }
    cin>>q;
    for (int i=1;i<=q;i++)
    {
        int x,y;cin>>x>>y;int ans=0;
        for (int bit=MAXM-1;bit>=0;bit--)
        {
            if (parent[bit][x]<=y and parent[bit][x]!=0) {ans+=(1<<bit);x=parent[bit][x];}
        }
        cout<<ans+1<<endl;
    }
}

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