oj.uz

Submission #1022862

# Submission time Handle Problem Language Result Execution time Memory
1022862 2024-07-14T06:44:22 Z hqminhuwu Specijacija (COCI20_specijacija) C++14
20 / 110
 4000 ms 479404 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair <ll,ll> pll;
typedef pair <ll,ll> pii;
typedef pair <ll,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_popcountll
#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 ll N = 1e6 + 5;
const ll oo = (ll) 1e16;
const ll mod = 1e9 + 7; // 998244353;

struct node {
    ll val = 0, comp = 0;
    node *l, *r;
    node (ll u, ll 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 (ll l, ll r){
    if (l == r) return new node(1, l);
    ll mid = (l + r) >> 1;
    return new node(build(l, mid), build(mid + 1, r));
}
 
node *update (node *i, ll l, ll r, ll u, ll val, ll comp){
    if (l == r) return new node(val, comp);
    ll 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, ll l, ll r, ll u){
    if (l == r) return mp(l, i -> comp);
    ll 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 get (node *i, ll l, ll r, ll u, ll v){
    if (l > v || r < u || u > v) return 0;
    if (l >= u && r <= v) return i -> val;
    ll mid = (l + r) >> 1;
    return get(i -> l, l, mid, u, v) + get(i -> r, mid + 1, r, u, v);
}


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

ll getdep(ll x){
    forr (i, 1, n){
        if (x - i <= 0)
            return i;
        x -= i;
    }
    return n + 1;
}

void dfs (ll u){
    for (ll v : g[u]){
        d[v] = d[u] + 1;
        up[0][v] = u;
        //cout << u << " " << v << "\n";
        forr (i, 1, 18){
            up[i][v] = up[i - 1][up[i - 1][v]];
        }
        dfs(v);
    }
}

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

ll lca (ll u, ll v){
    if (d[u] < d[v]) swap(u, v);
    u = jump(u, d[u] - d[v]);
    //cout << u << " " << v << endl;
    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);
    //cout << x << " " << u << " " << v << "\n";
    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;
        //cout << w << "\n";
        pii u = walk(root[i], 1, n + 1, w);
        pii v = walk(root[i], 1, n + 1, w + 1);
        //cout << u.st << " " << u.nd << " " << v.st << " " << v.nd << "\n";
        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);
        // cout << u << " " << uu << endl;
        // cout << v << " " << vv << endl;
        if (uu == vv){
            pre = min(u, v);
            cout << min(u, v) << endl;
            continue;
        }

        ll s = lca(uu, vv);

       // cout << s << endl;

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

    return 0;
}
/*



*/

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 654 ms 470992 KB Output is correct
2 Correct 47 ms 57476 KB Output is correct
3 Correct 651 ms 471084 KB Output is correct
4 Correct 371 ms 258388 KB Output is correct
5 Correct 769 ms 471216 KB Output is correct
6 Correct 194 ms 157296 KB Output is correct
7 Correct 486 ms 479404 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 654 ms 470992 KB Output is correct
2 Correct 47 ms 57476 KB Output is correct
3 Correct 651 ms 471084 KB Output is correct
4 Correct 371 ms 258388 KB Output is correct
5 Correct 769 ms 471216 KB Output is correct
6 Correct 194 ms 157296 KB Output is correct
7 Correct 486 ms 479404 KB Output is correct
8 Correct 598 ms 28504 KB Output is correct
9 Correct 438 ms 27564 KB Output is correct
10 Correct 529 ms 28724 KB Output is correct
11 Correct 315 ms 26452 KB Output is correct
12 Correct 520 ms 28712 KB Output is correct
13 Correct 349 ms 26968 KB Output is correct
14 Correct 523 ms 29268 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 654 ms 470992 KB Output is correct
2 Correct 47 ms 57476 KB Output is correct
3 Correct 651 ms 471084 KB Output is correct
4 Correct 371 ms 258388 KB Output is correct
5 Correct 769 ms 471216 KB Output is correct
6 Correct 194 ms 157296 KB Output is correct
7 Correct 486 ms 479404 KB Output is correct
8 Correct 598 ms 28504 KB Output is correct
9 Correct 438 ms 27564 KB Output is correct
10 Correct 529 ms 28724 KB Output is correct
11 Correct 315 ms 26452 KB Output is correct
12 Correct 520 ms 28712 KB Output is correct
13 Correct 349 ms 26968 KB Output is correct
14 Correct 523 ms 29268 KB Output is correct
15 Execution timed out 4070 ms 471716 KB Time limit exceeded
16 Halted 0 ms 0 KB -

Subtask #4
0 / 60.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4081 ms 471460 KB Time limit exceeded
2 Halted 0 ms 0 KB -