oj.uz

Submission #446200

# Submission time Handle Problem Language Result Execution time Memory
446200 2021-07-21T08:53:50 Z Jasiekstrz Specijacija (COCI20_specijacija) C++17
110 / 110
 1870 ms 915752 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 912 ms 901664 KB Output is correct
2 Correct 59 ms 62188 KB Output is correct
3 Correct 911 ms 880932 KB Output is correct
4 Correct 438 ms 459380 KB Output is correct
5 Correct 905 ms 875728 KB Output is correct
6 Correct 245 ms 263492 KB Output is correct
7 Correct 443 ms 498968 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 912 ms 901664 KB Output is correct
2 Correct 59 ms 62188 KB Output is correct
3 Correct 911 ms 880932 KB Output is correct
4 Correct 438 ms 459380 KB Output is correct
5 Correct 905 ms 875728 KB Output is correct
6 Correct 245 ms 263492 KB Output is correct
7 Correct 443 ms 498968 KB Output is correct
8 Correct 194 ms 5856 KB Output is correct
9 Correct 171 ms 4224 KB Output is correct
10 Correct 195 ms 6024 KB Output is correct
11 Correct 143 ms 2888 KB Output is correct
12 Correct 193 ms 5828 KB Output is correct
13 Correct 171 ms 3452 KB Output is correct
14 Correct 192 ms 5628 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 912 ms 901664 KB Output is correct
2 Correct 59 ms 62188 KB Output is correct
3 Correct 911 ms 880932 KB Output is correct
4 Correct 438 ms 459380 KB Output is correct
5 Correct 905 ms 875728 KB Output is correct
6 Correct 245 ms 263492 KB Output is correct
7 Correct 443 ms 498968 KB Output is correct
8 Correct 194 ms 5856 KB Output is correct
9 Correct 171 ms 4224 KB Output is correct
10 Correct 195 ms 6024 KB Output is correct
11 Correct 143 ms 2888 KB Output is correct
12 Correct 193 ms 5828 KB Output is correct
13 Correct 171 ms 3452 KB Output is correct
14 Correct 192 ms 5628 KB Output is correct
15 Correct 1844 ms 883896 KB Output is correct
16 Correct 849 ms 169156 KB Output is correct
17 Correct 1827 ms 887256 KB Output is correct
18 Correct 870 ms 178544 KB Output is correct
19 Correct 1860 ms 889148 KB Output is correct
20 Correct 830 ms 155464 KB Output is correct
21 Correct 1518 ms 502036 KB Output is correct

Subtask #4
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 1870 ms 897304 KB Output is correct
2 Correct 1210 ms 427416 KB Output is correct
3 Correct 1869 ms 915752 KB Output is correct
4 Correct 1185 ms 395816 KB Output is correct
5 Correct 1840 ms 902960 KB Output is correct
6 Correct 1236 ms 445612 KB Output is correct
7 Correct 1646 ms 571784 KB Output is correct