//#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define pii pair<int,int>
#define pll pair<ll,ll>
#define ldb double
template<typename T>void ckmn(T&a,T b){a=min(a,b);}
template<typename T>void ckmx(T&a,T b){a=max(a,b);}
void rd(int&x){scanf("%i",&x);}
void rd(ll&x){scanf("%lld",&x);}
void rd(char*x){scanf("%s",x);}
void rd(ldb&x){scanf("%lf",&x);}
void rd(string&x){scanf("%s",&x);}
template<typename T1,typename T2>void rd(pair<T1,T2>&x){rd(x.first);rd(x.second);}
template<typename T>void rd(vector<T>&x){for(T&i:x)rd(i);}
template<typename T,typename...A>void rd(T&x,A&...args){rd(x);rd(args...);}
template<typename T>void rd(){T x;rd(x);return x;}
int ri(){int x;rd(x);return x;}
template<typename T>vector<T> rv(int n){vector<T> x(n);rd(x);return x;}
template<typename T>void ra(T a[],int n,int st=1){for(int i=0;i<n;++i)rd(a[st+i]);}
template<typename T1,typename T2>void ra(T1 a[],T2 b[],int n,int st=1){for(int i=0;i<n;++i)rd(a[st+i]),rd(b[st+i]);}
template<typename T1,typename T2,typename T3>void ra(T1 a[],T2 b[],T3 c[],int n,int st=1){for(int i=0;i<n;++i)rd(a[st+i]),rd(b[st+i]),rd(c[st+i]);}
void re(vector<int> E[],int m,bool dir=0){for(int i=0,u,v;i<m;++i){rd(u,v);E[u].pb(v);if(!dir)E[v].pb(u);}}
template<typename T>void re(vector<pair<int,T>> E[],int m,bool dir=0){for(int i=0,u,v;i<m;++i){T w;rd(u,v,w);E[u].pb({v,w});if(!dir)E[v].pb({u,w});}}
const int N=200050;
const int M=20000000;
const int inf=1e9;
mt19937 rng(time(0));
int ls[M],rs[M],tsz,pri[M],val[M],R[M],sz[M],mxR[M];
int make(int x,int y){tsz++;pri[tsz]=rng();val[tsz]=x;R[tsz]=mxR[tsz]=y;sz[tsz]=1;return tsz;}
int cpy(int c){tsz++;ls[tsz]=ls[c];rs[tsz]=rs[c];pri[tsz]=pri[c];val[tsz]=val[c];R[tsz]=R[c];sz[tsz]=sz[c];mxR[tsz]=mxR[c];return tsz;}
void pull(int c){sz[c]=sz[ls[c]]+1+sz[rs[c]];mxR[c]=rs[c]?mxR[rs[c]]:R[c];}
void rot_l(int&c){int a=rs[c],b=ls[a];rs[c]=b;ls[a]=c;pull(c);pull(a);c=a;}
void rot_r(int&c){int a=ls[c],b=rs[a];ls[c]=b;rs[a]=c;pull(c);pull(a);c=a;}
void Ins(int p,int&c,int x,int y){
if(!p)c=make(x,y);
else{
c=cpy(p);
if(val[c]<x){
Ins(rs[p],rs[c],x,y);
if(pri[rs[c]]>pri[c])rot_l(c);
else pull(c);
}else{
Ins(ls[p],ls[c],x,y);
if(pri[ls[c]]>pri[c])rot_r(c);
else pull(c);
}
}
}
void Del(int p,int&c,int x){
if(val[c]==x){
//printf("%i %i %i\n",c,val[c],x);
if(!ls[c])c=rs[c];
else if(!rs[c])c=ls[c];
else if(pri[ls[c]]>pri[rs[c]]){
c=cpy(c);ls[c]=cpy(ls[c]);
rot_r(c);Del(rs[p],rs[c],x);
pull(c);
}else{
c=cpy(c);rs[c]=cpy(rs[c]);
rot_l(c);Del(ls[p],ls[c],x);
pull(c);
}
}else{
c=cpy(p);
if(val[c]<x)Del(rs[p],rs[c],x);
else Del(ls[p],ls[c],x);
pull(c);
}
}
int Kth(int c,int k){
if(!c)return 0;
if(sz[ls[c]]+1<k)return Kth(rs[c],k-sz[ls[c]]-1);
if(sz[ls[c]]+1==k)return c;
return Kth(ls[c],k);
}
int Find(int c,int x){
if(!c)return 0;
if(val[c]<=x&&R[c]>=x)return c;
if(x<val[c])return Find(ls[c],x);
return Find(rs[c],x);
}
int CntLo(int c,int x){
if(!c)return 0;
int ans=0;
if(mxR[ls[c]]<x){
ans+=sz[ls[c]];
if(R[c]<x)ans++;
ans+=CntLo(rs[c],x);
}
else ans+=CntLo(ls[c],x);
return ans;
}
void P(int c,bool nl=1){
if(!c)return;
P(ls[c],0);
printf("(%i %i, %i) ",val[c],R[c],sz[ls[c]]+1);
P(rs[c],0);
if(nl)printf("\n");
}
int p[N],w[N],_sz[N];
void init(int n){for(int i=1;i<=n;i++)p[i]=i,_sz[i]=1;}
int Find(int x){return p[x]==x?x:Find(p[x]);}
void Union(int x,int y,int z){
x=Find(x);y=Find(y);
if(_sz[x]>_sz[y])swap(x,y);
p[x]=y;
w[x]=z;
_sz[y]+=_sz[x];
//printf("U %i %i %i\n",x,y,z);
}
int root[N];
ll a[N];
int b[N];
int main(){
int n,q,t;rd(n,q,t);
ra(a,n);
for(int i=1;i<=n;i++){
b[i]=a[i]-(ll)i*(i-1)/2;
//printf("%i ",b[i]);
}
//printf("\n");
init(n+1);
for(int i=1;i<=n+1;i++)Ins(root[n+1],root[n+1],i,i);
for(int i=n;i>=1;i--){
int o=Kth(root[i+1],b[i]);
int l=Kth(root[i+1],b[i]+1);
//printf("%i %i\n",val[o],val[l]);
root[i]=root[i+1];
Del(root[i],root[i],val[o]);
Del(root[i],root[i],val[l]);
Union(Find(val[o]),Find(val[l]),i);
Ins(root[i],root[i],val[o],R[l]);
//P(root[i]);
}
//for(int i=n+1;i>=1;i--)P(root[i]);
auto lvl=[&](ll x){
int bot=1,top=n+1,ans=0;
while(top>=bot){
int mid=top+bot>>1;
if((ll)mid*(mid-1)/2<x)ans=mid,bot=mid+1;
else top=mid-1;
}
return ans;
};
ll z=0,mod=(ll)(n+1)*(n+2)/2;
while(q--){
ll x,y;rd(x,y);
//printf("x: %lld y: %lld\n",x,y);
x=(x-1+t*z)%mod+1;
y=(y-1+t*z)%mod+1;
if(x==y){
z=x;
}else{
//printf("x: %lld y: %lld\n",x,y);
int lx=lvl(x);
int ly=lvl(y);
//printf("lx: %i ly: %i\n",lx,ly);
x-=(ll)lx*(lx-1)/2;
y-=(ll)ly*(ly-1)/2;
//printf("x: %lld y: %lld\n",x,y);
//P(root[lx]);
//P(root[ly]);
int nx=Kth(root[lx],x);
int ny=Kth(root[ly],y);
//printf("(%i %i) (%i %i)\n",val[nx],R[nx],val[ny],R[ny]);
int a=min(val[nx],val[ny]);
int b=max(R[nx],R[ny]);
//printf("a:%i b:%i\n",a,b);
int ans=min(lx,ly);
while(a!=b){
//printf("%i %i %i %i %i %i\n",a,p[a],w[a],b,p[b],w[b]);
if(w[a]<w[b])swap(a,b);
ckmn(ans,w[a]);
a=p[a];
}
z=(ll)ans*(ans-1)/2+CntLo(root[ans],a)+1;
}
printf("%lld\n",z);
}
return 0;
}
Compilation message
road_construction.cpp: In function 'void rd(std::string&)':
road_construction.cpp:17:27: warning: format '%s' expects argument of type 'char*', but argument 2 has type 'std::string*' {aka 'std::__cxx11::basic_string<char>*'} [-Wformat=]
17 | void rd(string&x){scanf("%s",&x);}
| ~^ ~~
| | |
| | std::string* {aka std::__cxx11::basic_string<char>*}
| char*
road_construction.cpp: In lambda function:
road_construction.cpp:148:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
148 | int mid=top+bot>>1;
| ~~~^~~~
road_construction.cpp: In function 'void rd(int&)':
road_construction.cpp:13:21: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
13 | void rd(int&x){scanf("%i",&x);}
| ~~~~~^~~~~~~~~
road_construction.cpp: In function 'void rd(long long int&)':
road_construction.cpp:14:20: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
14 | void rd(ll&x){scanf("%lld",&x);}
| ~~~~~^~~~~~~~~~~
road_construction.cpp: In function 'void rd(char*)':
road_construction.cpp:15:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
15 | void rd(char*x){scanf("%s",x);}
| ~~~~~^~~~~~~~
road_construction.cpp: In function 'void rd(double&)':
road_construction.cpp:16:21: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
16 | void rd(ldb&x){scanf("%lf",&x);}
| ~~~~~^~~~~~~~~~
road_construction.cpp: In function 'void rd(std::string&)':
road_construction.cpp:17:24: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
17 | void rd(string&x){scanf("%s",&x);}
| ~~~~~^~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
10076 ms |
1240 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
291 ms |
295216 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
162 ms |
168060 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
162 ms |
168060 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
10076 ms |
1240 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
10076 ms |
1240 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
