제출 #1247088

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1247088		ivaziva	Osumnjičeni (COCI21_osumnjiceni)	C++20	110 / 110	444 ms	44408 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#define MAXN 200002
#define MAXM 18
#define int long long

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

int32_t main()
{
    ios_base::sync_with_stdio(false);ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    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});
            if (it!=s.end()) {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],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: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 20 / 20
• Subtask 4: 20 / 20
• Subtask 5: 50 / 50