Submission #502249

#	Time	Username	Problem	Language	Result	Execution time	Memory
502249		Victor	Specijacija (COCI20_specijacija)	C++17	110 / 110	1689 ms	257504 KiB

Main

// #pragma GCC target ("avx,avx2,fma")
// #pragma GCC optimize ("Ofast,inline") // O1 - O2 - O3 - Os - Ofast
// #pragma GCC optimize ("unroll-loops")
#include <bits/stdc++.h>

using namespace std;

#define rep(i, a, b) for (int i = (a); i < (b); ++i)
#define per(i, a, b) for (int i = (b - 1); i >= (a); --i)
#define trav(a, x) for (auto &a : x)

#define all(x) x.begin(), x.end()
#define sz(x) x.size()
#define pb push_back
#define debug(x) cout << #x << " = " << x << endl

#define umap unordered_map
#define uset unordered_set

typedef pair<int, int> ii;
typedef pair<int, ii> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<vi> vvi;

typedef long long ll;
typedef pair<ll, ll> pll;
typedef vector<ll> vll;
typedef vector<pll> vpll;

const int INF = 1'000'000'007;

struct Node {
    Node *l, *r;
    int lo, hi, val;
    Node(int L, int R) : lo(L), hi(R) {
        val = hi - lo;
        if (hi - lo != 1) {
            int mid = (lo + hi) / 2;
            l = new Node(lo, mid);
            r = new Node(mid, hi);
        }
    }
    Node() { ; }

    int query(int L, int R) {
        if (hi <= L || R <= lo) return 0;
        if (L <= lo && hi <= R) return val;
        return l->query(L, R) + r->query(L, R);
    }

    int walk(int indx) {
        // cout<<"lo = "<<lo<<" hi = "<<hi<<" indx = "<<indx<<endl;
        if (hi - lo == 1) return lo;
        if (indx <= l->val)
            return l->walk(indx);
        else
            return r->walk(indx - l->val);
    }
};

Node *roots[200001];
int n, q, pos;

void new_root(int change) {
    roots[pos - 1] = new Node();

    Node *cur = roots[pos - 1], *prev = roots[pos];

    while (1) {
        cur->val = prev->val - 1;
        cur->lo = prev->lo;
        cur->hi = prev->hi;
        if (cur->hi - cur->lo == 1) break;

        int mid = (cur->lo + cur->hi) / 2;
        if (change < mid) {
            cur->r = prev->r;
            cur->l = new Node();

            cur = cur->l;
            prev = prev->l;

        } else {
            cur->l = prev->l;
            cur->r = new Node();

            cur = cur->r;
            prev = prev->r;
        }
    }
    --pos;
}

int cnt;
vii components[200005];
ll triangles[200005], vals[400005], depth[400005];
ll params[200005];
int jmp[20][400005];

ll lca(int u, int v) {
    if (depth[u] < depth[v]) swap(u, v);
    per(j, 0, 20) if (depth[u] - depth[v] >= (1 << j)) u = jmp[j][u];

    //cout << "u = " << u << " v = " << v << " du = " << depth[u] << " dv = " << depth[v] << endl;
    if (u == v) return vals[u];

    per(j, 0, 20) if (jmp[j][u] != jmp[j][v]) {
        u = jmp[j][u];
        v = jmp[j][v];
    }

    //cout<<"u = "<<u<<" du = "<<depth[u]<<" u = ";
    u = jmp[0][u];
    //cout<<u<<" du = "<<depth[u]<<endl;
    return vals[u];
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin.exceptions(cin.failbit);

    ll t;
    cin >> n >> q >> t;
    cnt = n * 2 + 1;
    pos = n;
    roots[n] = new Node(0, n + 1);
    triangles[0] = 0;
    rep(i, 0, n + 1) {
        triangles[i + 1] = ll(i + 1) * ll(i + 2) / 2LL;
        components[i].emplace_back(n, --cnt);
        vals[cnt] = ll(n) * ll(n + 1) / 2LL + i + 1;
    }

    rep(i, 0, n) cin >> params[i];
    per(i, 0, n) {
        int before = roots[pos]->walk(params[i] - triangles[i]);
        int change = roots[pos]->walk(params[i] - triangles[i] + 1);

        int component = components[before].back().second;
        jmp[0][component] = --cnt;
        component = components[change].back().second;
        jmp[0][component] = cnt;
        vals[cnt] = params[i];
        components[before].emplace_back(i, cnt);

        new_root(change);
        // cout<<"i = "<<i<<" indx = "<<params[i] - triangles[i]+1<<" change = "<<change+1<<endl;
    }

    // pos=1;
    // rep(i,1,n+2)rep(j,0,i)cout<<"val = "<<pos++<<" indx = "<<roots[i-1]->walk(j+1)+1<<endl;

    jmp[0][0] = 0;
    rep(j, 1, 20) rep(i, 0, n * 2 + 1) jmp[j][i] = jmp[j - 1][jmp[j - 1][i]];
    rep(i, 0, n + 1) reverse(all(components[i]));

    rep(i, 0, 2*n+ 1) {
        int d = 0, u = i;
        per(j, 0, 20) if (jmp[j][u]) {
            d += 1 << j;
            u = jmp[j][u];
        }
        d += (u != 0);
        depth[i] = d;
    }

    ll prev = 0;
    while (q--) {
        ll a, b;
        cin >> a >> b;
        a = ((a - 1 + t * prev) % triangles[n + 1]) + 1;
        b = ((b - 1 + t * prev) % triangles[n + 1]) + 1;

        int layer1 = lower_bound(triangles, triangles + n + 2, a) - triangles - 1;
        int layer2 = lower_bound(triangles, triangles + n + 2, b) - triangles - 1;

        int pos1 = roots[layer1]->walk(a - triangles[layer1]);
        int pos2 = roots[layer2]->walk(b - triangles[layer2]);

        int u = lower_bound(all(components[pos1]), ii(layer1, 0))->second;
        int v = lower_bound(all(components[pos2]), ii(layer2, 0))->second;

        prev = min(lca(u, v), min(a, b));
        cout << prev << '\n';
        //cout << "val = " << a + 1 << " layer = " << layer1 + 1 << " indx = " << pos1 + 1 << " u = " << u + 1 << endl;
        //cout << "val = " << b + 1 << " layer = " << layer2 + 1 << " indx = " << pos2 + 1 << " u = " << v + 1 << endl;
    }
    return 0;
}

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