Submission #1022874

#	Time	Username	Problem	Language	Result	Execution time	Memory
1022874		hqminhuwu	Specijacija (COCI20_specijacija)	C++14	20 / 110	4061 ms	356108 KiB

Main

#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 / 10
• Subtask 2: 10 / 10
• Subtask 3: 0 / 30
• Subtask 4: 0 / 60