Submission #863135

#	Time	Username	Problem	Language	Result	Execution time	Memory
863135		3omar_ahmed	Osumnjičeni (COCI21_osumnjiceni)	C++17	110 / 110	986 ms	117324 KiB

Main

#include <bits/stdc++.h>
using namespace std ;
#define int long long
#define endl '\n'
#define all(a) a.begin() , a.end()
#define alr(a) a.rbegin() , a.rend()

struct segtree {
    int sz;
    vector < int > tree, lazy;
    void init(int n) {
        sz = 1;
        while(sz <= n) sz <<= 1;
        lazy = tree = vector < int > (sz << 2, 1e9);
    }

    void prop(int node) {
        if(lazy[node] != 1e9) {
            tree[node * 2 + 1] = tree[node * 2 + 2] = lazy[node];
            lazy[node * 2 + 1] = lazy[node * 2 + 2] = lazy[node];

            lazy[node] = 1e9;
        }
    }

    void update(int node, int lnode, int rnode, int l, int r, int val) {
        if(rnode <= l || r <= lnode) return;
        if(lnode >= l && rnode <= r) {
            tree[node] = lazy[node] = val;
            return;
        }
        int mid = (lnode + rnode) >> 1;
        prop(node);
        update(node * 2 + 1, lnode, mid, l, r, val);
        update(node * 2 + 2, mid, rnode, l, r, val);
        tree[node] = min(tree[node * 2 + 1], tree[node * 2 + 2]);
    }
    void update(int l, int r, int val) {
        update(0, 0, sz, l, r, val);
    }

    int query(int node, int lnode, int rnode, int l, int r) {
        if(rnode <= l || r <= lnode) return 1e9;
        if(lnode >= l && rnode <= r) {
            return tree[node];
        }
        int mid = (lnode + rnode) >> 1;
        prop(node);
        int a = query(node * 2 + 1, lnode, mid, l, r);
        int b = query(node * 2 + 2, mid, rnode, l, r);
        return min(a, b);
    }
    int query(int l, int r) {
        return query(0, 0, sz, l, r);
    }
};


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

    int n;
    cin >> n;
    n += 1;
    vector < pair < int , int >> a(n);
    set < int > ss;
    for(int i = 0 ; i + 1 < n ; i++) {
        cin >> a[i].first >> a[i].second;
        ss.insert(a[i].first);
        ss.insert(a[i].second);
    }    
    map < int,  int > mp;
    int cnt = 1;
    for(auto i : ss) {
        mp[i] = cnt++;
    }
    for(int i = 0 ; i + 1 < n ; i++) {
        a[i].first = mp[a[i].first];
        a[i].second = mp[a[i].second];
    }

    a[n - 1] = {1, n};
    vector < vector < int >> nxt(20, vector < int > (n + 1, -1));
    nxt[0][n - 1] = n - 1;

    segtree s; s.init(ss.size() + 10);
    for(int i = n - 2 ; i >= 0 ; i--) {
        nxt[0][i] = min(nxt[0][i + 1], n - 2);
        nxt[0][i] = min(nxt[0][i], s.query(a[i].first, a[i].second + 1));
        s.update(a[i].first, a[i].second + 1, i - 1);
    }

    // for(int i = 0 ; i < n - 1 ; i ++) cout << nxt[0][i] + 1 << " ";
    // cout << endl;

    for(int i = 1 ; i < 20 ; i++) {
        for(int j = 0 ; j < n ; j++) {
            if(nxt[i - 1][j] != -1)
                nxt[i][j] = nxt[i - 1][nxt[i - 1][j] + 1];
        }
    }

    int q;
    cin >> q;
    while(q--) {
        int l, r;
        cin >> l >> r;
        l -= 1, r -= 1;
        int ans = 0;
        for(int i = 19 ; i >= 0 ; i--) {
            if(nxt[i][l] <= r && nxt[i][l] != -1) {
                ans += (1ll << i);
                l = nxt[i][l] + 1;
            }
        }
        ans += (l <= r);
        cout << ans << endl;
    }
    return 0 ;
}

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