Submission #1256712

#	Time	Username	Problem	Language	Result	Execution time	Memory
1256712		RandomUser	Osumnjičeni (COCI21_osumnjiceni)	C++20	40 / 110	1093 ms	457980 KiB

Main

#include <bits/stdc++.h>
#define ar array
//#define int long long

using namespace std;

using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

const int mod = 1e9 + 7;
const ll inf = 1e9;
const int N = 2e5 + 5;

struct node {
    node *lc, *rc;
    int mx = 0, lazy = 0;

    node() { lc = rc = nullptr; }

    void extend() {
        if(lc != nullptr) return ;
        lc = new node();
        rc = new node();
    }

    void push(int tl, int tr) {
        if(!lazy) return ;
        mx += lazy;

        if(tl != tr) {
            extend();
            lc->lazy += lazy;
            rc->lazy += lazy;
        }

        lazy = 0;
    }

    void update(int tl, int tr, int l, int r, int v) {
        push(tl, tr);
        if(tl > r || l > tr) return ;

        if(l <= tl && tr <= r) {
            lazy += v;
            push(tl, tr);
            return ;
        }

        extend();
        int tm = (tl + tr) / 2;
        lc->update(tl, tm, l, r, v);
        rc->update(tm+1, tr, l, r, v);
        mx = max(lc->mx, rc->mx);
    }

    int query() {
        push(1, inf);
        return mx;
    }
};

signed main() {
    ios_base::sync_with_stdio(false);
    cout.tie(0); cin.tie(0);

    int n; cin >> n;
    vector<int> L(n+1), R(n+1);
    for(int i=1; i<=n; i++) cin >> L[i] >> R[i];

    node* root = new node();
    vector<int> nxt(n+1);

    for(int i=n,j=n; i>=1; i--) {
        root->update(1, inf, L[i], R[i], 1);
        while(j > i && root->query() > 1) {
            root->update(1, inf, L[j], R[j], -1);
            j--;
        }
        nxt[i] = j+1;
    }

    int q; cin >> q;
    while(q--) {
        int l, r, ans = 0;
        cin >> l >> r;

        while(l <= r) ans++, l = nxt[l];

        cout << ans << '\n';
    }
}

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