oj.uz

Submission #1022874

# Submission time Handle Problem Language Result Execution time Memory
1022874 2024-07-14T06:53:22 Z hqminhuwu Specijacija (COCI20_specijacija) C++14
20 / 110
 4000 ms 356108 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){
    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 << "\n";
    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 << "\n";
        // cout << v << " " << vv << "\n";
        if (uu == vv){
            pre = min(u, v);
            cout << min(u, v) << "\n";
            continue;
        }

        ll s = lca(uu, vv);

       // cout << s << "\n";

        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 551 ms 347732 KB Output is correct
2 Correct 44 ms 48720 KB Output is correct
3 Correct 569 ms 347884 KB Output is correct
4 Correct 278 ms 194360 KB Output is correct
5 Correct 548 ms 347916 KB Output is correct
6 Correct 153 ms 121168 KB Output is correct
7 Correct 400 ms 356108 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 551 ms 347732 KB Output is correct
2 Correct 44 ms 48720 KB Output is correct
3 Correct 569 ms 347884 KB Output is correct
4 Correct 278 ms 194360 KB Output is correct
5 Correct 548 ms 347916 KB Output is correct
6 Correct 153 ms 121168 KB Output is correct
7 Correct 400 ms 356108 KB Output is correct
8 Correct 214 ms 28512 KB Output is correct
9 Correct 139 ms 27396 KB Output is correct
10 Correct 219 ms 28240 KB Output is correct
11 Correct 83 ms 26416 KB Output is correct
12 Correct 215 ms 28244 KB Output is correct
13 Correct 102 ms 26940 KB Output is correct
14 Correct 200 ms 28760 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 551 ms 347732 KB Output is correct
2 Correct 44 ms 48720 KB Output is correct
3 Correct 569 ms 347884 KB Output is correct
4 Correct 278 ms 194360 KB Output is correct
5 Correct 548 ms 347916 KB Output is correct
6 Correct 153 ms 121168 KB Output is correct
7 Correct 400 ms 356108 KB Output is correct
8 Correct 214 ms 28512 KB Output is correct
9 Correct 139 ms 27396 KB Output is correct
10 Correct 219 ms 28240 KB Output is correct
11 Correct 83 ms 26416 KB Output is correct
12 Correct 215 ms 28244 KB Output is correct
13 Correct 102 ms 26940 KB Output is correct
14 Correct 200 ms 28760 KB Output is correct
15 Execution timed out 4061 ms 348800 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 4050 ms 348900 KB Time limit exceeded
2 Halted 0 ms 0 KB -