Submission #796286

#	Time	Username	Problem	Language	Result	Execution time	Memory
796286		amirhoseinfar1385	Abracadabra (CEOI22_abracadabra)	C++17	0 / 100	260 ms	32720 KiB

Main

#include<bits/stdc++.h>
using namespace std;
const int maxn=200000+10;
int n,q;
int all[maxn],res[maxn],link[maxn];
set<int>st;

void solve(int v){
	st.insert(n+1);
	for(int i=1;i<=n;i++){
		link[all[i]]=i;
	}
	int now=n;
	for(int i=n;i>=1;i--){
		//<<i<<endl;
		auto x=*st.lower_bound(link[i]);
		if(x==link[i])
		{
			continue;
		}
		int len=x-link[i];
		//<<"salam2"<<endl;
		int ted=now-(n/2);
		//<<"salam3 "<<ted<<endl;

		int z=0;
		if(ted>0){
			z=len-min((len-1)/ted,v)*ted;
		}
		else{
			z=len;
		}
		//<<len<<" "<<ted<<" "<<z<<endl; 
		st.insert(link[i]);
		for(int j=z-1;j>=0;j--){
			//<<j<<" "<<link[i]<<" "<<all[link[i]+j]<<" "<<len<<" "<<now<<endl;
			res[now]=all[link[i]+j];
			st.insert(link[all[link[i]+j]]);
			now--;
			//<<"salam"<<endl;
		}
	}
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>q;
	for(int i=1;i<=n;i++){
		cin>>all[i];
	}
	int u,v;
	cin>>v>>u;
	solve(v);
	cout<<res[u]<<"\n";
	for(int i=1;i<q;i++){
		cin>>v>>u;
		cout<<res[u]<<"\n";
	}
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 40
• Subtask 3: 0 / 25
• Subtask 4: 0 / 25