Submission #446160

#	Time	Username	Problem	Language	Result	Execution time	Memory
446160		Jasiekstrz	Specijacija (COCI20_specijacija)	C++17	0 / 110	281 ms	319260 KiB

Main

#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=4e6;
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;
}

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