Submission #537925

#	Time	Username	Problem	Language	Result	Execution time	Memory
537925		davi_bart	Osumnjičeni (COCI21_osumnjiceni)	C++14	110 / 110	703 ms	60296 KiB

Main

#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define int ll
#define fi first
#define se second
#define ld long double
#define pb push_back
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int N, Q;
vector<array<int, 2> > v;
struct segment {
    const int dim = 1 << 19;
    struct node {
        int val, prop;
        node(int a = -1, int b = -1) {
            val = a;
            prop = b;
        }
    };
    vector<node> s = vector<node>(2 * dim);
    void prop(int pos) {
        if (pos >= dim || s[pos].prop == -1) return;
        s[2 * pos].val = s[pos].prop;
        s[2 * pos].prop = s[pos].prop;

        s[2 * pos + 1].val = s[pos].prop;
        s[2 * pos + 1].prop = s[pos].prop;
    }
    void upd(int pos, int l, int r, int a, int b, int k) {
        prop(pos);
        if (r < a || l > b) return;
        if (a <= l && r <= b) {
            s[pos].val = k;
            s[pos].prop = k;
            return;
        }
        int m = (l + r) / 2;
        upd(2 * pos, l, m, a, b, k);
        upd(2 * pos + 1, m + 1, r, a, b, k);
        s[pos].val = max(s[2 * pos].val, s[2 * pos + 1].val);
        s[pos].prop = -1;
    }

    int query(int pos, int l, int r, int a, int b) {
        prop(pos);
        if (r < a || l > b) return -1;
        if (a <= l && r <= b) return s[pos].val;
        int m = (l + r) / 2;
        return max(query(2 * pos, l, m, a, b), query(2 * pos + 1, m + 1, r, a, b));
    }
    void upd(int a, int b, int k) {
        upd(1, 0, dim - 1, a, b, k);
    }
    int query(int a, int b) {
        return query(1, 0, dim - 1, a, b);
    }
} seg;
int r[20][200010];
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> N;
    vector<int> x;
    for (int i = 0; i < N; i++) {
        int a, b;
        cin >> a >> b;
        v.pb({a, b});
        x.pb(a);
        x.pb(b);
    }
    sort(x.begin(), x.end());
    x.resize(unique(x.begin(), x.end()) - x.begin());
    for (int i = 0; i < N; i++) {
        v[i][0] = lower_bound(x.begin(), x.end(), v[i][0]) - x.begin();
        v[i][1] = lower_bound(x.begin(), x.end(), v[i][1]) - x.begin();
    }
    for (int i = 0; i < N; i++) {
        r[0][i] = seg.query(v[i][0], v[i][1]);
        seg.upd(v[i][0], v[i][1], i);
        if (i) r[0][i] = max(r[0][i], r[0][i - 1]);
    }
    for (int i = 1; i < 19; i++) {
        for (int j = 0; j < N; j++) {
            if (r[i - 1][j] == -1)
                r[i][j] = -1;
            else
                r[i][j] = r[i - 1][r[i - 1][j]];
        }
    }

    cin >> Q;
    for (int i = 0; i < Q; i++) {
        int a, b;
        cin >> a >> b;
        a--;
        b--;
        int tot = 1;
        int pos = b;
        int q = 18;
        while (q >= 0) {
            if (r[q][pos] >= a) {
                tot += (1 << q);
                pos = r[q][pos];
            }
            q--;
        }
        cout << tot << '\n';
    }
}

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