Submission #745205

#	Time	Username	Problem	Language	Result	Execution time	Memory
745205		Ahmed57	Osumnjičeni (COCI21_osumnjiceni)	C++17	110 / 110	722 ms	42188 KiB

Main

//LCA
#include <bits/stdc++.h>

using namespace std;
int P[200001][18];
int main(){
    int n;
    cin>>n;
    for(int i = 0;i<=n;i++)P[i][0]= n;
    multiset<pair<pair<int,int>,int>> s;
    set<int> ind;
    for(int i = 0;i<n;i++)ind.insert(i);
    for(int i = 0;i<n;i++){
        int a,b;cin>>a>>b;
        int ma = -1;
        pair<pair<int,int>,int> p = {{a,0},0};
        auto it = s.lower_bound(p);
        if(it!=s.begin()){
            it--;
            if((*it).first.second>=a){
                ma = max(ma,(*it).second);
                s.erase(it);
            }
        }
        it = s.lower_bound(p);
        while(it!=s.end()&&(*it).first.first<=b){
            ma = max(ma,(*it).second);
            s.erase(it);
            it = s.lower_bound(p);
        }
        p.second = i;
        p.first.second = b;
        s.insert(p);
        while(!ind.empty()&&(*ind.begin())<=ma){
            P[(*ind.begin())][0] = i;
            ind.erase(ind.begin());
        }
    }
    for(int i = n;i>=0;i--){
        for(int j= 1;j<=17;j++){
            P[i][j] = P[P[i][j-1]][j-1];
        }
    }
    int q;cin>>q;
    while(q--){
        int x,y;cin>>x>>y;
        x--;y--;
        long long sum = 0;
        for(int j = 17;j>=0;j--){
            if(P[x][j]<=y){
                x = P[x][j];
                sum+=(1<<j);
            }
        }
        cout<<sum+1<<endl;
    }
}

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