oj.uz

Submission #502249

# Submission time Handle Problem Language Result Execution time Memory
502249 2022-01-05T15:46:29 Z Victor Specijacija (COCI20_specijacija) C++17
110 / 110
 1689 ms 257504 KB 
// #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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 562 ms 250288 KB Output is correct
2 Correct 40 ms 24020 KB Output is correct
3 Correct 552 ms 252576 KB Output is correct
4 Correct 282 ms 135344 KB Output is correct
5 Correct 556 ms 252500 KB Output is correct
6 Correct 167 ms 79296 KB Output is correct
7 Correct 329 ms 250752 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 562 ms 250288 KB Output is correct
2 Correct 40 ms 24020 KB Output is correct
3 Correct 552 ms 252576 KB Output is correct
4 Correct 282 ms 135344 KB Output is correct
5 Correct 556 ms 252500 KB Output is correct
6 Correct 167 ms 79296 KB Output is correct
7 Correct 329 ms 250752 KB Output is correct
8 Correct 190 ms 9160 KB Output is correct
9 Correct 154 ms 8340 KB Output is correct
10 Correct 188 ms 9208 KB Output is correct
11 Correct 113 ms 7492 KB Output is correct
12 Correct 167 ms 9156 KB Output is correct
13 Correct 135 ms 8004 KB Output is correct
14 Correct 168 ms 9732 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 562 ms 250288 KB Output is correct
2 Correct 40 ms 24020 KB Output is correct
3 Correct 552 ms 252576 KB Output is correct
4 Correct 282 ms 135344 KB Output is correct
5 Correct 556 ms 252500 KB Output is correct
6 Correct 167 ms 79296 KB Output is correct
7 Correct 329 ms 250752 KB Output is correct
8 Correct 190 ms 9160 KB Output is correct
9 Correct 154 ms 8340 KB Output is correct
10 Correct 188 ms 9208 KB Output is correct
11 Correct 113 ms 7492 KB Output is correct
12 Correct 167 ms 9156 KB Output is correct
13 Correct 135 ms 8004 KB Output is correct
14 Correct 168 ms 9732 KB Output is correct
15 Correct 1656 ms 257432 KB Output is correct
16 Correct 955 ms 57556 KB Output is correct
17 Correct 1681 ms 257504 KB Output is correct
18 Correct 908 ms 59040 KB Output is correct
19 Correct 1689 ms 257440 KB Output is correct
20 Correct 923 ms 52788 KB Output is correct
21 Correct 1500 ms 257184 KB Output is correct

Subtask #4
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 1640 ms 251092 KB Output is correct
2 Correct 1259 ms 126516 KB Output is correct
3 Correct 1674 ms 257468 KB Output is correct
4 Correct 1245 ms 122492 KB Output is correct
5 Correct 1614 ms 257372 KB Output is correct
6 Correct 1240 ms 137112 KB Output is correct
7 Correct 1495 ms 257156 KB Output is correct