Submission #725072

#	Time	Username	Problem	Language	Result	Execution time	Memory
725072		TahirAliyev	Osumnjičeni (COCI21_osumnjiceni)	C++17	110 / 110	760 ms	33656 KiB

Main

#include <bits/stdc++.h>

#pragma GCC optimize("O3")

using namespace std;
 
#define ll long long int
#define oo 1e18 + 5
#define pii pair<int, int>

const int MAX = 2e5 + 5;
const int LOGMAX = 20;

pii arr[MAX]; 
int par[LOGMAX + 1][MAX];

bool isOverlap(pii a, pii b){
    return a.second >= b.first && b.second >= a.first;
}

int binLift(int l, int r){
    int ans = 1;
    for(int j = LOGMAX; j >= 0; j--){
        if(par[j][l] <= r){
            l = par[j][l];
            ans += (1 << j);
        }
    }
    return ans;
}

int main(){
    int n, q; cin >> n;
    for (int i = 0; i < n; i++)
    {
        cin >> arr[i].first >> arr[i].second;
    }
    set<pii> s;
    int t = 0;
    for (int i = 0; i < n; i++)
    {
        while(!s.empty()){
            auto itr = s.upper_bound({arr[i].first, oo});
            auto itr2 = s.upper_bound({arr[i].second, oo});
            if(itr != s.begin()) itr--;
            if(itr2 != s.begin()) itr2--;
            if(isOverlap(*itr, arr[i]) || isOverlap(*itr2, arr[i])){
                par[0][t] = i;
                s.erase(arr[t]);
                t++;
            }
            else break;
        }
        s.insert(arr[i]);
    }
    for (int k = t; k <= n; k++)
    {
        par[0][k] = n;
    }
    for (int j = 1; j <= LOGMAX; j++)
    {
        for (int i = 0; i <= n; i++)
        {
            par[j][i] = par[j - 1][par[j - 1][i]];
        }
    }
    cin >> q;
    while(q--){
        int l, r; cin >> l >> r;
        l--;r--;
        cout << binLift(l, r) << '\n';
    }
}

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