Submission #1256720

#	Time	Username	Problem	Language	Result	Execution time	Memory
1256720		RandomUser	Osumnjičeni (COCI21_osumnjiceni)	C++20	110 / 110	568 ms	50632 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 segment_tree {
    int n;
    vector<int> tree, lazy;

    segment_tree(int _n) : n(_n), tree(4*n), lazy(4*n) {}

    void push(int u, int tl, int tr) {
        if(!lazy[u]) return ;
        tree[u] += lazy[u];

        if(tl != tr) {
            lazy[2*u] += lazy[u];
            lazy[2*u+1] += lazy[u];
        }

        lazy[u] = 0;
    }

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

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

        int tm = (tl + tr) / 2;
        update(2*u, tl, tm, l, r, v);
        update(2*u+1, tm+1, tr, l, r, v);
        tree[u] = max( tree[2*u], tree[2*u+1] );
    }

    int query() {
        push(1, 1, n);
        return tree[1];
    }

    void update(int l, int r, int v) { update(1, 1, n, l, r, v); }
};

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

    int n; cin >> n;
    set<int> st = { -1 };
    vector<int> L(n+1), R(n+1);
    for(int i=1; i<=n; i++) {
        cin >> L[i] >> R[i];
        st.insert(L[i]);
        st.insert(R[i]);
    }

    vector<int> comp( st.begin(), st.end() );
    for(int i=1; i<=n; i++) {
        L[i] = lower_bound(comp.begin(), comp.end(), L[i]) - comp.begin();
        R[i] = lower_bound(comp.begin(), comp.end(), R[i]) - comp.begin();
    }

    int m = comp.size();
    segment_tree sgt(m);
    
    int up[n+2][20];
    for(int i=1; i<=n+1; i++)
        for(int j=0; j<20; j++) up[i][j] = n+1;

    for(int i=n,j=n; i>=1; i--) {
        sgt.update(L[i], R[i], 1);
        while(j > i && sgt.query() > 1) {
            sgt.update(L[j], R[j], -1);
            j--;
        }
        up[i][0] = j+1;
    }

    for(int j=1; j<20; j++)
        for(int i=1; i<=n; i++)
            up[i][j] = up[ up[i][j-1] ][j-1];

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

        for(int j=19; j>=0; j--) {
            if(up[l][j] <= r) {
                ans ^= 1 << j;
                l = up[l][j];
            }
        }

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

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