oj.uz

Submission #1022857

# Submission time Handle Problem Language Result Execution time Memory
1022857 2024-07-14T06:38:22 Z hqminhuwu Specijacija (COCI20_specijacija) C++14
20 / 110
 4000 ms 479496 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));
}

pll walk (node *i, ll l, ll r, ll 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 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], n, q, t, u, v, cc, d[N], up[20][N], f[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 (int u){
    for (int 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);
    }
}

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]);
    //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];
        int w = a[i] - i * (i - 1) / 2;
        //cout << w << "\n";
        pll u = walk(root[i], 1, n + 1, w);
        pll 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 665 ms 471240 KB Output is correct
2 Correct 49 ms 57684 KB Output is correct
3 Correct 670 ms 471152 KB Output is correct
4 Correct 319 ms 258388 KB Output is correct
5 Correct 622 ms 471124 KB Output is correct
6 Correct 172 ms 157352 KB Output is correct
7 Correct 542 ms 479496 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 665 ms 471240 KB Output is correct
2 Correct 49 ms 57684 KB Output is correct
3 Correct 670 ms 471152 KB Output is correct
4 Correct 319 ms 258388 KB Output is correct
5 Correct 622 ms 471124 KB Output is correct
6 Correct 172 ms 157352 KB Output is correct
7 Correct 542 ms 479496 KB Output is correct
8 Correct 475 ms 28604 KB Output is correct
9 Correct 418 ms 27468 KB Output is correct
10 Correct 450 ms 28568 KB Output is correct
11 Correct 287 ms 26312 KB Output is correct
12 Correct 496 ms 28752 KB Output is correct
13 Correct 331 ms 27116 KB Output is correct
14 Correct 474 ms 29264 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 665 ms 471240 KB Output is correct
2 Correct 49 ms 57684 KB Output is correct
3 Correct 670 ms 471152 KB Output is correct
4 Correct 319 ms 258388 KB Output is correct
5 Correct 622 ms 471124 KB Output is correct
6 Correct 172 ms 157352 KB Output is correct
7 Correct 542 ms 479496 KB Output is correct
8 Correct 475 ms 28604 KB Output is correct
9 Correct 418 ms 27468 KB Output is correct
10 Correct 450 ms 28568 KB Output is correct
11 Correct 287 ms 26312 KB Output is correct
12 Correct 496 ms 28752 KB Output is correct
13 Correct 331 ms 27116 KB Output is correct
14 Correct 474 ms 29264 KB Output is correct
15 Execution timed out 4066 ms 472136 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 4067 ms 472252 KB Time limit exceeded
2 Halted 0 ms 0 KB -