제출 #1163042

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1163042		yhkhoo	Specijacija (COCI20_specijacija)	C++20	0 / 110	407 ms	149204 KiB

Main

#include <bits/stdc++.h>
using namespace std;

#define int long long

typedef pair<int, int> pii;
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define lb lower_bound
#define ub upper_bound
#define vub(x, v) (ub((v).begin(), (v).end(), x))

const int MAXN = 200005, MAXD = 20*MAXN;

int timer = 0;

int t[MAXD], cl[MAXD], cr[MAXD], rn[MAXN], a[MAXN], s[MAXN], cs[MAXN], p[MAXN], twok[MAXN][18], dep[MAXN], cd[MAXN][2], ta[MAXN], tb[MAXN];
vector<int> m[MAXN];

void build(int v, int tl, int tr) {
    if (tl == tr) {
        t[v] = 1;
    } else {
        int tm = (tl + tr) / 2;
        cl[v] = ++timer;
        cr[v] = ++timer;
        build(cl[v], tl, tm);
        build(cr[v], tm+1, tr);
        t[v] = t[cl[v]] + t[cr[v]];
    }
}

int query(int v, int tl, int tr, int l, int r){
    if(l>r) return 0;
    if(l==tl && r==tr) return t[v];
    int tm = (tl + tr)/2;
    return query(cl[v], tl, tm, l, min(r, tm)) + query(cr[v], tm+1, tr, max(l, tm+1), r);
}

int bs(int v, int tl, int tr, int k) {
    if (k > t[v]) return -1;
    if (tl == tr) return tl;
    int tm = (tl + tr) / 2;
    if (t[cl[v]] >= k){
        return bs(cl[v], tl, tm, k);
    }
    else{
        return bs(cr[v], tm+1, tr, k - t[cl[v]]);
    }
}

int update(int v, int tl, int tr, int pos){
    int v2 = ++timer;
    if(tl == tr){
        t[v2] = 0;
    }
    else{
        int tm = (tl+tr)/2;
        cl[v2] = cl[v], cr[v2] = cr[v];
        if(pos<=tm){
            cl[v2] = update(cl[v], tl, tm, pos);
        }
        else{
            cr[v2] = update(cr[v], tm+1, tr, pos);
        }
        t[v2] = t[cl[v2]] + t[cr[v2]];
    }
    return v2;
}

int kpar(int x,int k){
    for (int i=0;i<18;i++){
        if (k & (1<<i)) x = twok[x][i];
    }
    return x;
}

int lca(int a,int b){
    if (dep[a] > dep[b]) swap(a,b);
    b = kpar(b, dep[a] - dep[b]);
    if (a == b) return a; // edge case where a is an ancestor of b
    for (int k=17;k>=0;k--){
        if (twok[a][k] != twok[b][k]){
            a = twok[a][k]; b = twok[b][k];
        }
    }
    return twok[a][0];
}

signed main(){
    memset(twok, -1, sizeof(twok));
    cin.tie(0); ios_base::sync_with_stdio(0);
    int n, q, t;
    cin >> n >> q >> t;
    int ts = (n+1)*(n+2)/2; // pmo icl
    s[0] = 1;
    for(int i=1; i<=n; i++){
        s[i] = s[i-1] + i;
    }
    for(int i=0; i<n; i++){
        cin >> a[i];
    }
    build(0, 0, n);
    rn[n] = 0;
    p[0] = -1;
    for(int i=n-1; i>=0; i--){
        int pos = a[i] - s[i] + 1;
        ta[i] = bs(rn[i+1], 0, n, pos), tb[i] = bs(rn[i+1], 0, n, pos+1);
        rn[i] = update(rn[i+1], 0, n, tb[i]);
        m[ta[i]].pb(a[i]);
        m[tb[i]].pb(a[i]);
        if(cs[ta[i]] != 0){
            twok[cs[ta[i]]][0] = i;
            cd[i][0] = cs[ta[i]];
        }
        if(cs[tb[i]] != 0){
            twok[cs[tb[i]]][0] = i;
            cd[i][1] = cs[tb[i]];
        }
        cs[ta[i]] = i;
    }
    for(int i=0; i<=n; i++){
        sort(m[i].begin(), m[i].end());
    }
    for(int k=0; k<18; k++){
        for(int i=0; i<n; i++){
            twok[i][k] = twok[twok[i][k-1]][k-1];
        }
    }
    for(int i=0; i<n; i++){
        for(auto j: cd[i]){
            if(j != 0){
                dep[j] = dep[i] + 1;
            }
        }
    }
    int pz = 0;
    while(q--){
        int xt, yt, x, y, xl, yl, xc, yc, xp, yp, xpl, ypl, lcp, lcpc, lcpc1;
        cin >> xt >> yt;
        x = ((xt - 1 + t * pz) % ts) + 1, y = ((yt - 1 + t * pz) % ts) + 1;
        if(x > y) swap(x, y); // x is shallower
        xl = ub(s, s+n+1, x)-s-1, yl = ub(s, s+n+1, y)-s-1;
        xc = bs(rn[xl], 0, n, x - s[xl] + 1), yc = bs(rn[yl], 0, n, y - s[yl] + 1);
        xp = *(vub(x, m[xc])-1), yp = *(vub(y, m[yc])-1);
        xpl = ub(s, s+n+1, xp)-s-1, ypl = ub(s, s+n+1, yp)-s-1;
        lcp = lca(xpl, ypl);
        if((xc < tb[lcp]) == (yc < tb[lcp])){
            cout << x << '\n';
        }
        else{
            cout << a[lcp] << '\n';
        }
    }
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 30
• Subtask 4: 0 / 60