| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 244301 | TadijaSebez | Treasure Hunt (CEOI11_tre) | C++11 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#include "treasure.h"
using namespace std;
#define pb push_back
const int N=400050*2;
int go[N][2],fa[N],sz[N],fir[N],las[N],my_sz[N],tag[N],tsz;
void pull(int x){sz[x]=sz[go[x][0]]+my_sz[x]+sz[go[x][1]];}
void upd(int x){swap(go[x][0],go[x][1]);swap(fir[x],las[x]);tag[x]^=1;}
void push(int x){if(tag[x])upd(go[x][0]),upd(go[x][1]),tag[x]=0;}
int pd(int x){return go[fa[x]][0]==x?0:go[fa[x]][1]==x?1:-1;}
void rot(int x){
int y=fa[x],z=fa[y],p=pd(x),q=pd(y),w=go[x][p^1];
if(~q)go[z][q]=x;go[x][p^1]=y;go[y][p]=w;
if(w)fa[w]=y;fa[y]=x;fa[x]=z;
pull(y);pull(x);
}
void cl(int x){if(~pd(x))cl(fa[x]);push(x);}
void splay(int x){for(cl(x);~pd(x);rot(x))if(~pd(fa[x]))rot(pd(x)==pd(fa[x])?fa[x]:x);}
void access(int x){for(splay(x),go[x][1]=0,pull(x);fa[x];rot(x))splay(fa[x]),go[fa[x]][1]=x,pull(fa[x]);}
void make_rt(int x){access(x);upd(x);}
void take_path(int x,int y){make_rt(x);access(y);}
int Get(int x,int k){
push(x);
if(sz[go[x][0]]>k)return Get(go[x][0],k);
k-=sz[go[x][0]];
if(my_sz[x]>k)return x;
k-=my_sz[x];
return Get(go[x][1],k);
}
void cut(int u,int v){
make_rt(u);access(v);
go[v][0]=0;fa[u]=0;
pull(v);
}
int LCA(int u,int v){
make_rt(1);
access(u);
access(v);
splay(u);
if(!fa[u])return u;
return fa[u];
}
void P(int u){
if(!u)return;
push(u);
P(go[u][0]);
printf("(%i - %i) ",fir[u],las[u]);
P(go[u][1]);
}
int n;
int dwn[N],up[N];
map<pair<int,int>,int> nodes;
int AddNode(int l,int r){
tsz++;
fir[tsz]=l;las[tsz]=r;my_sz[tsz]=r-l+1;pull(tsz);
nodes[{l,r}]=tsz;
return tsz;
}
void init(){
//tsz++;fir[tsz]=las[tsz]=my_sz[tsz]=1;pull(tsz);nodes[{1,1}]=tsz;
AddNode(1,1);
n=1;
}
int GetNode(int u){
auto it=nodes.upper_bound({u+1,0});
it--;
return it->second;
}
void Extract(int u){
//make_rt(1);
int nd=GetNode(u);
splay(nd);
if(fir[nd]==las[nd])return;
assert(fir[nd]<las[nd]);
if(u==las[nd])return;
//if(fir[nd]>las[nd])swap(fir[nd],las[nd]);
//printf("Extract %i from (%i %i)\n",u,fir[nd],las[nd]);
nodes.erase({fir[nd],las[nd]});
int U=up[nd],D=dwn[nd];
//printf("U (%i-%i) D (%i-%i)\n",fir[U],las[U],fir[D],las[D]);
int F=fir[nd],L=las[nd];
access(U);
splay(nd);
fa[nd]=0;
//cut(U,nd);
//if(D)cut(D,nd);
vector<int> nds;
nds.pb(AddNode(F,u));
//splay(nd);
nds.pb(nd);fir[nd]=u+1;las[nd]=L;my_sz[nd]=L-u;pull(nd);nodes[{u+1,L}]=nd;
//if(L!=u)nds.pb(AddNode(u+1,L));
int tmp=U;
for(int i:nds){
//printf("%i do %i\n",fir[i],las[i]);
up[i]=tmp;
fa[i]=tmp;
dwn[tmp]=i;
tmp=i;
}
/*dwn[tmp]=D;
if(D){
make_rt(D);
fa[D]=up[D]=tmp;
}*/
}
void path(int u,int len){
//tsz++;fir[tsz]=n+1;las[tsz]=n+len;my_sz[tsz]=len;pull(tsz);nodes[{n+1,n+len}]=tsz;
int now=AddNode(n+1,n+len);
Extract(u);
fa[now]=up[now]=GetNode(u);
n+=len;
}
/*void FixLCA(int u,int v){
int lca=LCA(u,v);
//printf("FIX (%i %i) for (%i %i) ^ (%i %i)\n",fir[lca],las[lca],fir[u],las[u],fir[v],las[v]);
splay(lca);
if(fir[lca]==las[lca])return;
Extract(las[lca]-1);
}*/
int dig(int u,int v){
Extract(u);Extract(v);
int nu=GetNode(u);
int nv=GetNode(v);
//printf("%i %i\n",nu,nv);
//FixLCA(nu,nv);
int lca=LCA(nu,nv);
take_path(nu,nv);
splay(lca);
int ssz=sz[lca]-(my_sz[lca]-1);
int need=(ssz-1)/2;
if(sz[go[lca][0]]+1<=need)need+=my_sz[lca]-1;
//splay(nu);
//printf("ssz %i pre %i\n",ssz,need);
//P(nu);printf("\n");
int mid_node=Get(lca,need);
splay(mid_node);
int ost=need-sz[go[mid_node][0]];
int ans;
if(fir[mid_node]<las[mid_node])ans=fir[mid_node]+ost;
else ans=fir[mid_node]-ost;
make_rt(1);
return ans;
}
//---------------------//
/*
int main(){
int q;scanf("%i",&q);
while(q--){
char c;int u,v;
scanf("\n%c %i %i",&c,&u,&v);
if(c=='i')init();
else if(c=='p')path(u,v);
else printf("%i\n",dig(u,v));
//for(int i=1;i<=tsz;i++)printf("(%i %i)\n",fir[i],las[i]);
}
return 0;
}
*/
//---------------------//