Submission #1139938

#	Time	Username	Problem	Language	Result	Execution time	Memory
1139938		anmattroi	Specijacija (COCI20_specijacija)	C++17	110 / 110	1105 ms	230996 KiB

Main

#include <bits/stdc++.h>
#define maxn 200005
using namespace std;

int n, q, t;
int st[4*maxn];
int64_t a[maxn];
int c[maxn];
int id = 0;
void upd(int u, int d, int r = 1, int lo = 1, int hi = n+1) {
    if (lo == hi) {
        st[r] = d;
        return;
    }
    int mid = (lo + hi) >> 1;
    if (u <= mid) upd(u, d, r<<1, lo, mid);
    else upd(u, d, r<<1|1, mid+1, hi);
    st[r] = st[r<<1] + st[r<<1|1];
}

void build(int r = 1, int lo = 1, int hi = n+1) {
    st[r] = hi-lo+1;
    if (lo == hi) return;
    int mid = (lo + hi) >> 1;
    build(r<<1, lo, mid);
    build(r<<1|1, mid+1, hi);
}

int kth(int k, int r = 1, int lo = 1, int hi = n+1) {
    if (lo == hi) return lo;
    int mid = (lo + hi) >> 1, trai = st[r<<1];
    if (k <= trai) return kth(k, r<<1, lo, mid);
    return kth(k-trai, r<<1|1, mid+1, hi);
}

int f[20][2*maxn];
int d[2*maxn];
int64_t rem[2*maxn];
vector<int> adj[2*maxn];
int z[2*maxn], pos[2*maxn], m = 0;

void pfs(int u, int dad) {
    f[0][u] = dad;
    for (int i = 1; i < 20; i++) f[i][u] = f[i-1][f[i-1][u]];
    for (int v : adj[u])
    if (v != dad) {
        d[v] = d[u] + 1;
        pfs(v, u);
    }
    z[++m] = u;
    pos[u] = m;
}

int LCA(int u, int v) {
    auto jump = [&](int x, int k) -> int {
        for (int i = 0; i < 20; i++) if (k>>i&1) x = f[i][x];
        return x;
    };

    if (d[u] > d[v]) swap(u, v);
    if (d[u] < d[v]) v = jump(v, d[v]-d[u]);

    if (u == v) return u;
    for (int i = 19; i >= 0; i--)
    if (f[i][u] != f[i][v]) {
        u = f[i][u];
        v = f[i][v];
    }
    return f[0][u];
}

int it[130*maxn], L[130*maxn], R[130*maxn];
int nt = 0;

int root[maxn];

int pbuild(int lo = 1, int hi = id) {
    if (lo == hi) return ++nt;
    int cur = ++nt, mid = (lo + hi) >> 1;
    L[cur] = pbuild(lo, mid);
    R[cur] = pbuild(mid+1, hi);
    return cur;
}

int pupd(int u, int d, int oldver, int lo = 1, int hi = id) {
    if (lo == hi) {
        it[++nt] = d;
        return nt;
    }
    int cur = ++nt, mid = (lo + hi) >> 1;
    if (u <= mid) {
        L[cur] = pupd(u, d, L[oldver], lo, mid);
        R[cur] = R[oldver];
    } else {
        L[cur] = L[oldver];
        R[cur] = pupd(u, d, R[oldver], mid+1, hi);
    }
    it[cur] = it[L[cur]] + it[R[cur]];
    return cur;
}

int bfind(int k, int v, int lo = 1, int hi = id) {
    if (lo == hi) return lo;
    int mid = (lo + hi) >> 1, trai = it[L[v]];
    if (k > trai) return bfind(k-trai, R[v], mid+1, hi);
    return bfind(k, L[v], lo, mid);
}

int level(int64_t x) {
    int lo = -1, hi = n;
    while (hi-lo>1) {
        int mid = (lo+hi)>>1;
        if (x <= 1LL*(mid+1)*(mid+2)/2) hi = mid;
        else lo = mid;
    }
    return hi+1;
}

int64_t Fn(int Lv) {
    return 1LL * Lv * (Lv+1) / 2;
}

int64_t solve(int64_t x, int64_t y) {
    int Lv1 = level(x), Lv2 = level(y);
    int component1 = z[bfind(x-Fn(Lv1-1), root[Lv1])],
        component2 = z[bfind(y-Fn(Lv2-1), root[Lv2])];
    int w = LCA(component1, component2);
    return min({x, y, rem[w]});
}

map<int64_t, int> nho;

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

    cin >> n >> q >> t;

    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= n+1; i++) {
        c[i] = ++id;
        rem[id] = 1LL * n * (n+1) / 2 + i;
    }
    build();

    for (int level = n; level >= 1; level--) {
        int64_t L = a[level]+level, R = L+1;
        int64_t piv = 1LL * level * (level+1) / 2;
        int p1 = kth(L-piv), p2 = kth(R-piv);
        rem[++id] = a[level];
        nho[a[level]] = id;
        adj[id].emplace_back(c[p1]);
        adj[id].emplace_back(c[p2]);
        c[p1] = id;
        upd(p2, 0);
    }

    pfs(id, 0);

    root[0] = pbuild();
    root[1] = pupd(pos[id], 1, root[0]);

    for (int i = 2; i <= n+1; i++) {
        root[i] = root[i-1];
        int lt = nho[a[i-1]];
        root[i] = pupd(pos[lt], 0, root[i]);
        root[i] = pupd(pos[adj[lt][0]], 1, root[i]);
        root[i] = pupd(pos[adj[lt][1]], 1, root[i]);
    }

    int64_t last = 0;
    while (q--) {
        int64_t x, y; cin >> x >> y;
        x = (x-1 + t * last) % (1LL * (n+1) * (n+2) / 2) + 1;
        y = (y-1 + t * last) % (1LL * (n+1) * (n+2) / 2) + 1;
        cout << (last = solve(x, y)) << "\n";
    }

}
/*
3 5 1
1 2 6
7 10
8 5
6 2
9 10
2 3
-------
1
6
2
1
1
*/

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