#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
const int N=2e5;
const int L=18;
const long long INF=1e18L+7;
mt19937 gen(23112);
long long rng()
{
return uniform_int_distribution<long long>{-INF,INF}(gen);
}
struct Treap
{
int p;
int pt;
int id;
long long pr;
int lazy;
Treap *l,*r;
void init(int _p,int _pt,int _id)
{
p=_p;
pt=_pt;
id=_id;
lazy=0;
pr=rng();
return;
}
};
const int TM=15e6;
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;
if(x->id<idl)
{
auto y=newtreap();
(*y)=*x;
auto [a,b]=split(y->r,idl);
y->r=a;
if(b!=nullptr)
b->lazy+=y->lazy;
return {y,b};
}
if(x->id>idl)
{
auto y=newtreap();
(*y)=*x;
auto [a,b]=split(y->l,idl);
y->l=b;
if(a!=nullptr)
a->lazy+=y->lazy;
return {a,y};
}
Treap *a=nullptr,*b=nullptr;
if(x->l!=nullptr)
{
a=newtreap();
(*a)=*(x->l);
a->lazy+=x->lazy;
}
if(x->r!=nullptr)
{
b=newtreap();
(*b)=*(x->r);
b->lazy+=x->lazy;
}
return {a,b};
}
//Treap* merge(Treap* x,Treap* y,int xl=0,int yl=0)
//{
// if(y==nullptr)
// {
// auto xn=newtreap();
// (*xn)=*x;
// xn->lazy+=xl;
// return xn;
// }
// if(x==nullptr)
// {
// auto yn=newtreap();
// (*yn)=*y;
// yn->lazy+=yl;
// return yn;
// }
// if(x->pr<y->pr)
// {
// auto xn=newtreap();
// (*xn)=*x;
// xn->lazy+=xl;
// yl-=xn->lazy;
// xn->r=merge(xn->r,y,0,yl);
// return xn;
// }
// auto yn=newtreap();
// (*yn)=*y;
// yn->lazy+=yl;
// xl-=yn->lazy;
// yn->l=merge(x,yn->l,xl,0);
// return yn;
//}
vector<Treap*> clearnull(vector<Treap*> vec)
{
vector<Treap*> ans;
for(auto v:vec)
{
if(v!=nullptr)
ans.push_back(v);
}
return ans;
}
Treap* mergev(vector<Treap*> vec,vector<int> vl={})
{
if(vec.empty())
return nullptr;
if(vl.empty())
{
vl.resize(vec.size());
fill(vl.begin(),vl.end(),0);
}
if(vec.size()==1)
{
if(vl[0]==0)
return vec[0];
auto y=newtreap();
(*y)=*vec[0];
y->lazy+=vl[0];
return y;
}
int g=0;
for(size_t i=0;i<vec.size();i++)
{
if(vec[i]->pr<vec[g]->pr)
g=i;
}
auto y=newtreap();
(*y)=*vec[g];
y->lazy+=vl[g];
vector<Treap*> vec1,vec2;
vector<int> vl1,vl2;
for(int i=0;i<g;i++)
{
vec1.push_back(vec[i]);
vl1.push_back(vl[i]-y->lazy);
}
if(y->l!=nullptr)
{
vec1.push_back(y->l);
vl1.push_back(0);
}
if(y->r!=nullptr)
{
vec2.push_back(y->r);
vl2.push_back(0);
}
for(size_t i=g+1;i<vec.size();i++)
{
vec2.push_back(vec[i]);
vl2.push_back(vl[i]-y->lazy);
}
y->l=mergev(vec1,vl1);
y->r=mergev(vec2,vl2);
return y;
}
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 old=byid(rt[i],nr);
par[i]={old->p,old->pt};
auto [a,b]=split(rt[i],nr);
auto t0=newtreap();
t0->init(i,0,nr);
rt[i]=mergev(clearnull({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]=mergev(clearnull({a,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 |
Execution timed out |
4090 ms |
571560 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
4090 ms |
571560 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
4090 ms |
571560 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
4086 ms |
589952 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
