Submission #488278

#	Time	Username	Problem	Language	Result	Execution time	Memory
488278		TadijaSebez	Road Construction (JOI21_road_construction)	C++11	0 / 100	10076 ms	295216 KiB

road_construction

//#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 (stderr)

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);}
      |                   ~~~~~^~~~~~~~~

• Subtask 1: 0 / 5
• Subtask 2: 0 / 6
• Subtask 3: 0 / 7
• Subtask 4: 0 / 20
• Subtask 5: 0 / 27
• Subtask 6: 0 / 35