Submission #541162

#	Time	Username	Problem	Language	Result	Execution time	Memory
541162		AlperenT	Osumnjičeni (COCI21_osumnjiceni)	C++17	110 / 110	272 ms	33644 KiB

Main

#include <bits/stdc++.h>

using namespace std;

const int N = 2e5 + 5, K = 20, INF = 1e9 + 5;

int n, q, a, b, nxt[N], binlift[N][K];

pair<int, int> arr[N];

multiset<pair<int, int>> st;

int main(){
    ios_base::sync_with_stdio(false);cin.tie(NULL);

    cin >> n;

    for(int i = 1; i <= n; i++) cin >> arr[i].first >> arr[i].second;

    int r = 0;

    for(int i = 1; i <= n; i++){
        while(r <= n - 1){
            auto it = st.insert(arr[r + 1]);

            if(it != st.begin() && prev(it)->second >= arr[r + 1].first){
                st.erase(st.find(arr[r + 1]));
                break;
            }
            if(next(it) != st.end() && next(it)->first <= arr[r + 1].second){
                st.erase(st.find(arr[r + 1]));
                break;
            } 

            r++;
        }

        nxt[i] = r + 1;

        st.erase(st.find(arr[i]));
    }

    for(int i = n; i >= 1; i--){
        binlift[i][0] = nxt[i];

        for(int j = 1; j < K; j++) binlift[i][j] = binlift[binlift[i][j - 1]][j - 1];
    }

    cin >> q;

    while(q--){
        cin >> a >> b;

        int ans = 0;

        for(int i = K - 1; i >= 0; i--){
            if(binlift[a][i] != 0 && binlift[a][i] <= b){
                ans += 1 << i;
                a = binlift[a][i];
            }
        }

        cout << ans + 1 << "\n";
    }
}

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