#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
const int N=2e5;
const int L=20;
mt19937 gen(23112);
int rng(int l,int r)
{
return uniform_int_distribution<int>{l,r}(gen);
}
struct Treap
{
int p;
int pt;
int id;
int pr;
int lazy;
Treap *l,*r;
void init(int _p,int _pt,int _id)
{
p=_p;
pt=_pt;
id=_id;
lazy=0;
pr=rng(1,1e9);
return;
}
};
const int TM=1e7;
Treap treapmem[TM];
int treapit=0;
Treap* newtreap()
{
return &treapmem[treapit++];
}
pair<Treap*,Treap*> split(Treap* x,int idl)
{
if(x==nullptr)
return {nullptr,nullptr};
idl-=x->lazy;
auto y=newtreap();
(*y)=*x;
if(y->id<=idl)
{
auto [a,b]=split(y->r,idl);
y->r=a;
if(b!=nullptr)
b->lazy+=y->lazy;
return {y,b};
}
auto [a,b]=split(y->l,idl);
y->l=b;
if(a!=nullptr)
a->lazy+=y->lazy;
return {a,y};
}
Treap* merge(Treap* x,Treap* y)
{
if(y==nullptr)
{
auto xn=newtreap();
(*xn)=*x;
return xn;
}
if(x==nullptr)
{
auto yn=newtreap();
(*yn)=*y;
return yn;
}
auto xn=newtreap();
(*xn)=*x;
auto yn=newtreap();
(*yn)=*y;
if(x->pr<y->pr)
{
yn->lazy-=xn->lazy;
xn->r=merge(xn->r,yn);
return xn;
}
xn->lazy-=yn->lazy;
yn->l=merge(xn,yn->l);
return yn;
}
Treap* byid(Treap* x,int id)
{
id-=x->lazy;
if(x->id<id)
return byid(x->r,id);
if(x->id>id)
return byid(x->l,id);
return x;
}
Treap* rt[N+10];
pair<int,int> par[N+10];
int dep[N+10];
pair<int,int> jmp[N+10][L+2];
long long tab[N+10];
pair<int,int> get_par(long long x)
{
int bg=1,en=N+1;
while(bg<en)
{
int mid=(bg+en+1)/2;
if((long long)mid*(mid-1)/2<x)
bg=mid;
else
en=mid-1;
}
int nr=x-(long long)bg*(bg-1)/2;
auto it=byid(rt[bg],nr);
return {it->p,it->pt};
}
int lca(pair<int,int> a,pair<int,int> b)
{
if(dep[b.fi]<dep[a.fi])
swap(a,b);
for(int l=L;l>=0;l--)
{
if(dep[jmp[b.fi][l].fi]>=dep[a.fi])
b=jmp[b.fi][l];
}
if(a.fi==b.fi)
return (a.se!=b.se ? a.fi:-1);
for(int l=L;l>=0;l--)
{
if(jmp[a.fi][l].fi!=jmp[b.fi][l].fi)
{
a=jmp[a.fi][l];
b=jmp[b.fi][l];
}
}
a=par[a.fi];
b=par[b.fi];
return (a.se!=b.se ? a.fi:-1);
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int n,q,t;
cin>>n>>q>>t;
rt[1]=newtreap();
rt[1]->init(0,0,1);
for(int i=1;i<=n;i++)
{
long long x;
cin>>x;
tab[i]=x;
int nr=x-(long long)i*(i-1)/2;
auto [a,c]=split(rt[i],nr-1);
auto [old,b]=split(c,nr);
par[i]={old->p,old->pt};
auto t0=newtreap();
t0->init(i,0,nr);
rt[i]=merge(merge(a,t0),b);
auto t1=newtreap(),t2=newtreap();
t1->init(i,1,nr);
t2->init(i,2,nr+1);
Treap* bn=nullptr;
if(b!=nullptr)
{
bn=newtreap();
(*bn)=*b;
bn->lazy++;
}
rt[i+1]=merge(merge(a,merge(t1,t2)),bn);
}
//for(int i=1;i<=n+1;i++)
//{
// function<void(Treap*,int)> print_all=[&print_all](Treap* tr,int lazy)
// {
// if(tr==nullptr)
// return;
// lazy+=tr->lazy;
// print_all(tr->l,lazy);
// cerr<<tr->id+lazy<<" "<<tr->p<<" "<<tr->pt<<"\n";
// print_all(tr->r,lazy);
// return;
// };
// print_all(rt[i],0);
// cerr<<"\n";
//}
for(int i=1;i<=n;i++)
{
dep[i]=dep[par[i].fi]+1;
jmp[i][0]=par[i];
for(int l=1;l<=L;l++)
jmp[i][l]=jmp[jmp[i][l-1].fi][l-1];
}
long long lst=0;
auto decode=[&](long long x)
{
return (x-1+lst*t)%((long long)(n+1)*(n+2)/2)+1;
};
while(q--)
{
long long a,b;
cin>>a>>b;
a=decode(a);
b=decode(b);
int tmp=lca(get_par(a),get_par(b));
lst=(tmp==-1 ? min(a,b):tab[tmp]);
cout<<lst<<"\n";
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
689 ms |
797460 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
689 ms |
797460 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
689 ms |
797460 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
732 ms |
798068 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
