Submission #724596

#	Time	Username	Problem	Language	Result	Execution time	Memory
724596		TheSahib	Osumnjičeni (COCI21_osumnjiceni)	C++17	110 / 110	694 ms	32892 KiB

Main

#include <bits/stdc++.h>
 
#pragma GCC optimize("O3")
 
#define ll long long
#define oo 1e9 + 9
#define pii pair<int, int>
 
using namespace std;

const int MAX = 2e5 + 5;

int n, q;
pii arr[MAX];

int st[20][MAX];

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

void calcMaxR(){
    set<pii> s;
    int l = 0;
    for (int i = 0; i < n; i++)
    {
        while(!s.empty()){
            auto itr1 = s.upper_bound({arr[i].first, oo});
            auto itr2 = s.upper_bound({arr[i].second, oo});
            if(itr1 != s.begin()) --itr1;
            if(itr2 != s.begin()) --itr2;
            if((checkRange(arr[i], (*itr1))) || checkRange(arr[i], (*itr2))){
                st[0][l] = i;
                s.erase(arr[l]);
                ++l;
            }
            else{
                break;
            }
        }
        s.insert(arr[i]);
    }
    
    for (int j = l; j <= n; j++)
    {
        st[0][j] = n;
    }
}


void build(){
    for (int j = 1; j < 20; j++)
    {
        for (int i = 0; i <= n; i++)
        {
            st[j][i] = st[j - 1][st[j - 1][i]];
        }
    }
}

int ask(int l, int r){
    int ans = 1;
    for(int j = 19; j >= 0; --j){
        if(st[j][l] <= r){
            l = st[j][l];
            ans += (1 << j);
        }
    }
    return ans;
}

int main(){
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        cin >> arr[i].first >> arr[i].second;
    }
    calcMaxR();
    build();

    cin >> q;
    while(q--){
        int l, r; cin >> l >> r;
        --l; --r;
        cout << ask(l, r) << '\n';
    }
}

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