Submission #446200

#	Time	Username	Problem	Language	Result	Execution time	Memory
446200		Jasiekstrz	Specijacija (COCI20_specijacija)	C++17	110 / 110	1870 ms	915752 KiB

Main

#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=2e7;
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}));
		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]=mergev(clearnull({a,t1,t2,bn}));
		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;
}

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 30 / 30
• Subtask 4: 60 / 60