Submission #1100107

#	Time	Username	Problem	Language	Result	Execution time	Memory
1100107		giorgi123glm	Osumnjičeni (COCI21_osumnjiceni)	C++17	0 / 110	684 ms	56236 KiB

Main

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
using namespace std;

class lazy_segtree {
    public:
        vector <int> segtree;
        vector <int> lazytree;
        int siz = 1, n = 0;

        inline void apply_lazy (int u, int l, int r) {
            if (lazytree[u] == 0)
                return;
            
            segtree[u] = lazytree[u];
            if (l != r) {
                lazytree[2 * u] = lazytree[u];
                lazytree[2 * u + 1] = lazytree[u];
            }

            lazytree[u] = 0;
        }

        int get_segtree (int L, int R, int u, int l, int r) {
            apply_lazy (u, l, r);

            if (r < L || R < l)
                return 2e9;
            
            if (L <= l && r <= R)
                return segtree[u];
            
            int m = (l + r) / 2;
            return min (
                get_segtree (L, R, 2 * u, l, m),
                get_segtree (L, R, 2 * u + 1, m + 1, r)
            );
        }

        void update_segtree (int L, int R, int K, int u, int l, int r) {
            apply_lazy (u, l, r);

            if (r < L || R < l)
                return;
            
            if (L <= l && r <= R) {
                lazytree[u] = K;
                apply_lazy (u, l, r);
                return;
            }

            int m = (l + r) / 2;
            update_segtree (L, R, K, 2 * u, l, m);
            update_segtree (L, R, K, 2 * u + 1, m + 1, r);
            segtree[u] = min (segtree[2 * u], segtree[2 * u + 1]);
        }

        lazy_segtree (int n1) {
            n = n1;
            while (siz <= n)
                siz *= 2;
            segtree.resize (2 * siz, 2e9);
            lazytree.resize (2 * siz, 2e9);
        }
};

int main () {
    ios::sync_with_stdio (false);
    cin.tie (0);
    cout.tie (0);

    int n = 0;
    cin >> n;

    vector <pair <int, int> > v (n + 1);
    for (int i = 1; i <= n; i++)
        cin >> v[i].first >> v[i].second;
    
    map <int, int> zip;
    {
        for (int i = 1; i <= n; i++)
            zip[v[i].first] = 0, zip[v[i].second] = 0;
        
        int ind = 1;
        for (auto it = zip.begin(); it != zip.end(); it++) {
            (*it).second = ind;
            ind++;
        }
    }
    
    lazy_segtree segtree (4 * 1e5 + 10);
    vector <vector <int> > binlift (n + 1, vector <int> (20, 2e9));
    for (int i = n; i >= 1; i--) {
        binlift[i][0] = segtree.get_segtree (zip[v[i].first], zip[v[i].second], 1, 1, segtree.siz);
        segtree.update_segtree (zip[v[i].first], zip[v[i].second], i, 1, 1, segtree.siz);
    }

    for (int p = 1; p < 20; p++)
        for (int i = 1; i <= n; i++)
            if (binlift[i][p - 1] <= n)
                binlift[i][p] = binlift[binlift[i][p - 1]][p - 1];

    int q = 0;
    cin >> q;

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

        int ans = 0;
        for (int p = 19; p >= 0; p--)
            if (binlift[l][p] - 1 <= r) {
                ans += (1 << p);
                l = binlift[l][p];
            }

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

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