oj.uz

Submission #1022886

# Submission time Handle Problem Language Result Execution time Memory
1022886 2024-07-14T07:10:47 Z hqminhuwu Specijacija (COCI20_specijacija) C++14
110 / 110
 1624 ms 364220 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair <int,int> pll;
typedef pair <int,int> pii;
typedef pair <int,pii> piii;

#define forr(_a,_b,_c) for(ll _a = (_b); _a <= (_c); ++_a)
#define ford(_a,_b,_c) for(ll _a = (_b) + 1; _a --> (_c);)
#define forf(_a,_b,_c) for(ll _a = (_b); _a < (_c); ++_a)
#define st first
#define nd second
#define pb push_back
#define mp make_pair
#define all(x) begin(x),end(x)
#define mask(i) (1ll << (i))
#define bit(x, i) (((x) >> (i)) & 1)
#define bp __builtin_popcountint
#define file "test"

template<class X, class Y>
    bool minz(X &x, const Y &y) {
        if (x > y) {
            x = y;
            return true;
        } return false;
    }
template<class X, class Y>
    bool maxz(X &x, const Y &y) {
        if (x < y) {
            x = y;
            return true;
        } return false;
    }

const int N = 1e6 + 5;
const ll oo = (ll) 1e16;
const int mod = 1e9 + 7; // 998244353;

struct node {
    int val = 0, comp = 0;
    node *l, *r;
    node (int u, int v) : val(u), comp(v), l(nullptr), r(nullptr){}
    node (node *u, node *v){
        l = u;
        r = v;
        val = l -> val + r -> val;
    }
    node (node *cp) : val(cp -> val), l(cp -> l), r(cp -> r){}
};
 
node *build (int l, int r){
    if (l == r) return new node(1, l);
    int mid = (l + r) >> 1;
    return new node(build(l, mid), build(mid + 1, r));
}
 
node *update (node *i, int l, int r, int u, int val, int comp){
    if (l == r) return new node(val, comp);
    int mid = (l + r) >> 1;
    if (u <= mid)
        return new node (update(i -> l, l, mid, u, val, comp), i -> r);
    return new node (i -> l, update(i -> r, mid + 1, r, u, val, comp));
}

pii walk (node *i, int l, int r, int u){
    if (l == r) return mp(l, i -> comp);
    int mid = (l + r) >> 1;
    if (u <= (i -> l) -> val){
        return walk(i -> l, l, mid, u);
    } 
    return walk(i -> r, mid + 1, r, u - (i -> l) -> val);
} 



ll a[N], f[N], t, u, v;
ll n, q, cc, d[N], up[20][N];
vector <int> g[N];
node *root[N];

ll getdep(ll x){
    ll l = 1, r = n + 1;

    while (l < r){
        ll mid = (l + r + 1) >> 1;
        if ((mid * (mid - 1) / 2) < x)
            l = mid;
        else r = mid - 1;
    }
    
    return l;
}

void dfs (int u){
    for (int v : g[u]){
        d[v] = d[u] + 1;
        up[0][v] = u;
        forr (i, 1, 18){
            up[i][v] = up[i - 1][up[i - 1][v]];
        }
        dfs(v);
    }
}

int jump (int u, int v){
    forr (i, 0, 18)
    if (bit(v, i))
        u = up[i][u];
    return u;
}

int lca (int u, int v){
    if (d[u] < d[v]) swap(u, v);

    u = jump(u, d[u] - d[v]);

    if (u == v) return u;

    ford (i, 18, 0)
    if (up[i][u] != up[i][v]){
        u = up[i][u];
        v = up[i][v];
    }

    return up[0][u];
}

ll getcc (ll x){
    ll u = getdep(x);
    ll v = x - (u * (u - 1) / 2);
    return walk(root[u], 1, n + 1, v).nd;
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    #ifdef hqm
        freopen(file".inp", "r", stdin); freopen(file".out", "w", stdout);
    #endif  

    cin >> n >> q >> t;

    forr (i, 1, n){
        cin >> a[i];
    }

    forr (i, 1, n + 1)
        f[i] = n * (n + 1) / 2 + i;

    root[n + 1] = build(1, n + 1);
    cc = n + 1;

    ford (i, n, 1){
        root[i] = root[i + 1];
        ll w = a[i] - i * (i - 1) / 2;

        pii u = walk(root[i], 1, n + 1, w);
        pii v = walk(root[i], 1, n + 1, w + 1);

        root[i] = update(root[i], 1, n + 1, u.st, 1, ++cc);
        root[i] = update(root[i], 1, n + 1, v.st, 0, 0);

        g[cc].pb(u.nd);
        g[cc].pb(v.nd);
        f[cc] = a[i];
    }

    dfs(cc);

    ll pre = 0;

    while (q--){
        cin >> u >> v;
        u = (u - 1 + pre * t) % ((n + 1) * (n + 2) / 2) + 1;
        v = (v - 1 + pre * t) % ((n + 1) * (n + 2) / 2) + 1;

        ll uu = getcc(u);
        ll vv = getcc(v);

        if (uu == vv){
            pre = min(u, v);
            cout << min(u, v) << "\n";
            continue;
        }

        ll s = lca(uu, vv);

        if (s == uu){
            pre = u;
            cout << u << "\n";
        } else 
        if (s == vv){
            pre = v;
            cout << v << "\n"; 
        } else {
            pre = f[s];
            cout << f[s] << "\n";
        }
    }

    return 0;
}
/*



*/

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 516 ms 349468 KB Output is correct
2 Correct 40 ms 50120 KB Output is correct
3 Correct 563 ms 349268 KB Output is correct
4 Correct 270 ms 195996 KB Output is correct
5 Correct 548 ms 349264 KB Output is correct
6 Correct 149 ms 122452 KB Output is correct
7 Correct 401 ms 357896 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 516 ms 349468 KB Output is correct
2 Correct 40 ms 50120 KB Output is correct
3 Correct 563 ms 349268 KB Output is correct
4 Correct 270 ms 195996 KB Output is correct
5 Correct 548 ms 349264 KB Output is correct
6 Correct 149 ms 122452 KB Output is correct
7 Correct 401 ms 357896 KB Output is correct
8 Correct 128 ms 29776 KB Output is correct
9 Correct 106 ms 29008 KB Output is correct
10 Correct 143 ms 29704 KB Output is correct
11 Correct 77 ms 27880 KB Output is correct
12 Correct 126 ms 29780 KB Output is correct
13 Correct 90 ms 28244 KB Output is correct
14 Correct 150 ms 30468 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 516 ms 349468 KB Output is correct
2 Correct 40 ms 50120 KB Output is correct
3 Correct 563 ms 349268 KB Output is correct
4 Correct 270 ms 195996 KB Output is correct
5 Correct 548 ms 349264 KB Output is correct
6 Correct 149 ms 122452 KB Output is correct
7 Correct 401 ms 357896 KB Output is correct
8 Correct 128 ms 29776 KB Output is correct
9 Correct 106 ms 29008 KB Output is correct
10 Correct 143 ms 29704 KB Output is correct
11 Correct 77 ms 27880 KB Output is correct
12 Correct 126 ms 29780 KB Output is correct
13 Correct 90 ms 28244 KB Output is correct
14 Correct 150 ms 30468 KB Output is correct
15 Correct 1611 ms 354324 KB Output is correct
16 Correct 618 ms 92756 KB Output is correct
17 Correct 1580 ms 354452 KB Output is correct
18 Correct 577 ms 94548 KB Output is correct
19 Correct 1620 ms 354316 KB Output is correct
20 Correct 496 ms 86352 KB Output is correct
21 Correct 1279 ms 364204 KB Output is correct

Subtask #4
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 1609 ms 354904 KB Output is correct
2 Correct 1039 ms 182868 KB Output is correct
3 Correct 1593 ms 354384 KB Output is correct
4 Correct 1028 ms 177848 KB Output is correct
5 Correct 1624 ms 354192 KB Output is correct
6 Correct 1113 ms 196736 KB Output is correct
7 Correct 1238 ms 364220 KB Output is correct