oj.uz

답안 #1022868

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1022868 2024-07-14T06:47:05 Z hqminhuwu Specijacija (COCI20_specijacija) C++14
20 / 110
 4000 ms 356152 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);
} 

int get (node *i, int l, int r, int u, int v){
    if (l > v || r < u || u > v) return 0;
    if (l >= u && r <= v) return i -> val;
    int 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 <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 << 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

# 결과 실행 시간 메모리 Grader output
1 Correct 556 ms 347796 KB Output is correct
2 Correct 43 ms 48724 KB Output is correct
3 Correct 558 ms 347992 KB Output is correct
4 Correct 332 ms 194352 KB Output is correct
5 Correct 544 ms 347728 KB Output is correct
6 Correct 146 ms 121196 KB Output is correct
7 Correct 400 ms 356152 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 556 ms 347796 KB Output is correct
2 Correct 43 ms 48724 KB Output is correct
3 Correct 558 ms 347992 KB Output is correct
4 Correct 332 ms 194352 KB Output is correct
5 Correct 544 ms 347728 KB Output is correct
6 Correct 146 ms 121196 KB Output is correct
7 Correct 400 ms 356152 KB Output is correct
8 Correct 426 ms 28308 KB Output is correct
9 Correct 363 ms 27216 KB Output is correct
10 Correct 419 ms 28240 KB Output is correct
11 Correct 321 ms 26452 KB Output is correct
12 Correct 436 ms 28240 KB Output is correct
13 Correct 307 ms 26964 KB Output is correct
14 Correct 457 ms 28756 KB Output is correct

Subtask #3
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 556 ms 347796 KB Output is correct
2 Correct 43 ms 48724 KB Output is correct
3 Correct 558 ms 347992 KB Output is correct
4 Correct 332 ms 194352 KB Output is correct
5 Correct 544 ms 347728 KB Output is correct
6 Correct 146 ms 121196 KB Output is correct
7 Correct 400 ms 356152 KB Output is correct
8 Correct 426 ms 28308 KB Output is correct
9 Correct 363 ms 27216 KB Output is correct
10 Correct 419 ms 28240 KB Output is correct
11 Correct 321 ms 26452 KB Output is correct
12 Correct 436 ms 28240 KB Output is correct
13 Correct 307 ms 26964 KB Output is correct
14 Correct 457 ms 28756 KB Output is correct
15 Execution timed out 4075 ms 348968 KB Time limit exceeded
16 Halted 0 ms 0 KB -

Subtask #4
0 / 60.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 4045 ms 348940 KB Time limit exceeded
2 Halted 0 ms 0 KB -