oj.uz

Submission #745202

# Submission time Handle Problem Language Result Execution time Memory
745202 2023-05-19T14:40:20 Z Ahmed57 Osumnjičeni (COCI21_osumnjiceni) C++17
0 / 110
 232 ms 23756 KB 
//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;
    set<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);
        if(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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 220 ms 22604 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 16 ms 884 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 16 ms 884 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 232 ms 23756 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 220 ms 22604 KB Output isn't correct
2 Halted 0 ms 0 KB -