Submission #502231

#	Time	Username	Problem	Language	Result	Execution time	Memory
502231		JovanB	Osumnjičeni (COCI21_osumnjiceni)	C++17	110 / 110	315 ms	28416 KiB

Main

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using ld = long double;

const int N = 200000;
const int LOG = 20;

set <pair <int, int>> q;

bool intersects(int l, int r){
    if(q.empty()) return 0;
    auto x = q.lower_bound({l, -1});
    if(x != q.end()){
        if(x->first <= r) return 1;
    }
    if(x != q.begin()){
        x--;
        if(x->second >= l) return 1;
    }
    return 0;
}

int sl[N+5], sr[N+5];
int gde[LOG+1][N+5];

int main(){
    ios_base::sync_with_stdio(false), cin.tie(0);
    cout.precision(10);
    cout << fixed;

    int n;
    cin >> n;
    for(int i=1; i<=n; i++){
        cin >> sl[i] >> sr[i];
    }
    int j = n;
    for(int i=n; i>=1; i--){
        while(intersects(sl[i], sr[i])){
            q.erase({sl[j], sr[j]});
            j--;
        }
        q.insert({sl[i], sr[i]});
        gde[0][i] = j + 1;
    }
    gde[0][n+1] = n + 1;
    for(int j=1; j<=LOG; j++){
        for(int i=1; i<=n+1; i++){
            gde[j][i] = gde[j-1][gde[j-1][i]];
        }
    }
    int qrs;
    cin >> qrs;
    while(qrs--){
        int l, r;
        cin >> l >> r;
        r++;
        int res = 0;
        for(int j=LOG; j>=0; j--){
            if(gde[j][l] < r) l = gde[j][l], res += (1 << j);
        }
        res++;
        cout << res << "\n";
    }
    return 0;
}

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