Submission #1186866

#	Time	Username	Problem	Language	Result	Execution time	Memory
1186866		1bin	Specijacija (COCI20_specijacija)	C++20	0 / 110	124 ms	108072 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#define all(v) v.begin(), v.end()
typedef long long ll;
const int B = 1<<18;
namespace pst {
    struct node {
        int c, v;
        int l, r;
    } nd[22 * B];
    int root[B];
    int t = 0;

    int new_node(int c, int v) {
        nd[++t] = node(c, v, 0, 0);
        return t;
    }
    int init(int l, int r) {
        int ix = new_node(0, 0);
        if (l == r) return ix;
        int m = (l + r) / 2;
        nd[ix].l = init(l, m);
        nd[ix].r = init(m + 1, r);
        return ix;
    }
    int upd(int prev, int l, int r, int i, int c, int v) {
        int ix = new_node(nd[prev].c + c, v);
        if (l == r) return ix;
        int m = (l + r) / 2;
        if (i <= m) {
            nd[ix].l = upd(nd[prev].l, l, m, i, c, v);
            nd[ix].r = nd[prev].r;
        }
        else {
            nd[ix].l = nd[prev].l;
            nd[ix].r = upd(nd[prev].r, m + 1, r, i, c, v);
        }
        return ix;
    }
    int kth(int i, int l, int r, int k, int f = 0) {
        while (l ^ r) {
            int cnt = nd[nd[i].l].c;
            int m = l + r >> 1;
            if (k <= cnt) r = m, i = nd[i].l;
            else l = m + 1, k -= cnt, i = nd[i].r;
        }
        if (f) return l;
        return nd[i].v;
    }
}

int q, t, num, p[B * 2][20], lv[B * 2];
ll n, a[B], base[B], x, y, z, _x, _y, mod, ND[B * 2];
vector<int> adj[B * 2];

void dfs(int x) {
    for (int& nx : adj[x]) {
        lv[nx] = lv[x] + 1;
        p[nx][0] = x;
        dfs(nx);
    }
}

int lca(int a, int b) {
    if (lv[a] < lv[b]) swap(a, b);
    for (int i = 19; i >= 0; i--)
        if (lv[a] - lv[b] >= (1<<i)) a = p[a][i];
    if (a == b) return a;
    for (int i = 19; i >= 0; i--)
        if (p[a][i] != p[b][i]) a = p[a][i], b = p[b][i];
    return p[a][0];
}

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

    cin >> n >> q >> t;
    mod = (n + 1) * (n + 2) / 2;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        base[i] = base[i - 1] + i;
        a[i] -= base[i - 1];
    }

    n++;
    pst::root[n] = pst::init(1, n);
    for (int i = 1; i <= n; i++) pst::root[n] = pst::upd(pst::root[n], 1, n, i, 1,++num);
    for (int i = n - 1; i; i--) {
        int r = pst::kth(pst::root[i + 1], 1, n, a[i] + 1, 1);
        int rn = pst::kth(pst::root[i + 1], 1, n, a[i] + 1);
        int l = pst::kth(pst::root[i + 1], 1, n, a[i], 1);
        int ln = pst::kth(pst::root[i + 1], 1, n, a[i]);

        pst::root[i] = pst::upd(pst::root[i + 1], 1, n, r, -1, 0);
        pst::root[i] = pst::upd(pst::root[i], 1, n, l, 0, ++num);
        ND[num] = a[i] + base[i - 1];
        adj[num].emplace_back(ln);
        adj[num].emplace_back(rn);
    }
    p[num][0] = num;
    dfs(num);

    for (int j = 1; j < 20; j++)
        for (int i = 1; i <= num; i++) p[i][j] = p[p[i][j - 1]][j - 1];

    // for (int i = 1; i <= n; i++) {
    //     for (int j = 1; j <= i; j++) cout << pst::kth(pst::root[i], 1, n, j) << ' ';
    //     cout << endl;
    // }

    while (q--) {
        cin >> _x >> _y;
        x = (_x - 1 + t * z) % mod + 1;
        y = (_y - 1 + t * z) % mod + 1;

        int lvx = lower_bound(base + 1, base + n, x) - base;
        int lvy = lower_bound(base + 1, base + n, y) - base;
        int xn = pst::kth(pst::root[lvx], 1, n, x - base[lvx - 1]);
        int yn = pst::kth(pst::root[lvy], 1, n, y - base[lvy - 1]);

        if (xn == yn) z = min(x, y);
        else z = ND[lca(xn, yn)];
        cout << z << '\n';
    }
    return 0;
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 30
• Subtask 4: 0 / 60