Submission #502247

#	Time	Username	Problem	Language	Result	Execution time	Memory
502247		Victor	Specijacija (COCI20_specijacija)	C++17	0 / 110	1721 ms	258748 KiB

Main

// #pragma GCC target ("avx,avx2,fma")
// #pragma GCC optimize ("Ofast,inline") // O1 - O2 - O3 - Os - Ofast
// #pragma GCC optimize ("unroll-loops")
#include <bits/stdc++.h>

using namespace std;

#define rep(i, a, b) for (int i = (a); i < (b); ++i)
#define per(i, a, b) for (int i = (b - 1); i >= (a); --i)
#define trav(a, x) for (auto &a : x)

#define all(x) x.begin(), x.end()
#define sz(x) x.size()
#define pb push_back
#define debug(x) cout<<#x<<" = "<<x<<endl

#define umap unordered_map
#define uset unordered_set

typedef pair<int, int> ii;
typedef pair<int, ii> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<vi> vvi;

typedef long long ll;
typedef pair<ll,ll> pll;
typedef vector<ll> vll;
typedef vector<pll> vpll;

const int INF = 1'000'000'007;


struct Node {
    Node *l, *r;
    int lo,hi,val;
    Node(int L,int R) : lo(L),hi(R) {
        val=hi-lo;
        if(hi-lo!=1) {
            int mid=(lo+hi)/2;
            l=new Node(lo,mid);
            r=new Node(mid,hi);
        }
    }
    Node() {;}

    int query(int L,int R) {
        if(hi<=L||R<=lo)return 0;
        if(L<=lo&&hi<=R)return val;
        return l->query(L,R)+r->query(L,R);
    }

    int walk(int indx) {
        //cout<<"lo = "<<lo<<" hi = "<<hi<<" indx = "<<indx<<endl;
        if(hi-lo==1)return lo;
        if(indx<=l->val)return l->walk(indx);
        else return r->walk(indx - l->val);
    }
};

Node *roots[200001];
int n,q,pos;

void new_root(int change) {
    roots[pos-1]=new Node();

    Node *cur=roots[pos-1],*prev=roots[pos];
    
    while(1) {
        cur->val=prev->val-1;
        cur->lo=prev->lo;
        cur->hi=prev->hi;
        if(cur->hi - cur->lo==1) break;

        int mid=(cur->lo+cur->hi)/2;
        if(change < mid) {
            cur->r=prev->r;
            cur->l=new Node();

            cur=cur->l;
            prev=prev->l;

        } else {
            cur->l=prev->l;
            cur->r= new Node();

            cur=cur->r;
            prev=prev->r;
        }
    }
    --pos;
}

int cnt;
vii components[200001];
ll triangles[200001],vals[400001],depth[400001];
ll params[200001];
int jmp[20][400001];

ll lca(int u,int v) {
    if(depth[u]<depth[v])swap(u,v);
    per(j,0,20)if(depth[u]-depth[v]>=(1<<j))u=jmp[j][u];

    if(u==v)return vals[u];

    per(j,0,20)if(jmp[j][u]!=jmp[j][v]) {
        u=jmp[j][u];
        v=jmp[j][v];
    }

    u=jmp[0][u];
    return vals[u];
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin.exceptions(cin.failbit);

    ll t;
    cin>>n>>q>>t;
    cnt=n*2+1;
    pos=n;
    roots[n]=new Node(0,n+1);
    triangles[0]=0;
    rep(i,0,n+1) {
        triangles[i+1]=ll(i+1)*ll(i+2)/2LL;
        components[i].emplace_back(n, --cnt);
        vals[cnt]=ll(n)*ll(n+1)/2LL+i+1;
    }

    rep(i,0,n)cin>>params[i];
    per(i,0,n) {
        int before=roots[pos]->walk(params[i]-triangles[i]);
        int change=roots[pos]->walk(params[i]-triangles[i]+1);

        int component=components[before].back().second;
        jmp[0][component]=--cnt;
        component=components[change].back().second;
        jmp[0][component]=cnt;
        vals[cnt]=params[i];
        components[before].emplace_back(i,cnt);

        new_root(change);
        //cout<<"i = "<<i<<" indx = "<<params[i] - triangles[i]+1<<" change = "<<change+1<<endl;
    }

    //pos=1;
    //rep(i,1,n+2)rep(j,0,i)cout<<"val = "<<pos++<<" indx = "<<roots[i-1]->walk(j+1)+1<<endl;
    
    jmp[0][0]=0;
    per(j,1,20)rep(i,0,n*2+1) jmp[j][i]=jmp[j-1][jmp[j-1][i]];
    rep(i,0,n+1)reverse(all(components[i]));

    rep(i,0,n*2+1) {
        int d=0,u=i;
        per(j,0,20)if(jmp[j][u]) {
            d+=1<<j;
            u=jmp[j][u];
        }
        d+=(u!=0);
        depth[i]=d;
    }

    ll prev=0;
    while(q--) {
        ll a,b;
        cin>>a>>b;
        a=((a-1+t*prev)%triangles[n+1])+1;
        b=((b-1+t*prev)%triangles[n+1])+1;

        int layer1=lower_bound(triangles,triangles+n+2,a)-triangles-1;
        int layer2=lower_bound(triangles,triangles+n+2,b)-triangles-1;

        int pos1=roots[layer1]->walk(a-triangles[layer1]);
        int pos2=roots[layer2]->walk(b-triangles[layer2]);

        int u=lower_bound(all(components[pos1]), ii(layer1,0))->second;
        int v=lower_bound(all(components[pos2]), ii(layer2,0))->second;

        prev=min(lca(u,v),min(a,b));
        cout<<prev<<'\n';
        //cout<<"val = "<<a+1<<" layer = "<<layer1+1<<" indx = "<<pos1+1<<" u = "<<u+1<<endl;
    }
    return 0;
}

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