Submission #1096801

#	Time	Username	Problem	Language	Result	Execution time	Memory
1096801		vjudge1	Abracadabra (CEOI22_abracadabra)	C++14	10 / 100	3063 ms	28148 KiB

Main

#include<bits/stdc++.h>
#define MP make_pair
#define PII pair<int,int>
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
using namespace std;
typedef long long ll;
const int INF=0x3f3f3f3f;
const int N=2e5+5,Q=1e6+5;
int n,a[N],q;
int b[N],p1,p2;
struct Que{
	int t,x,id;
	friend bool operator<(Que x,Que y){return x.t<y.t;}
}que[Q];
int ans[Q];
bool doit(){
	bool tag=1;
	for(int i=1;i<=n/2;i++){
		if(a[i]>a[n/2+1]){
			tag=0;
			break;
		}
	}
	if(tag)return 1;
	p1=1,p2=n/2+1;
	for(int i=1;i<=n;i++){
		if(p1==n/2+1||(p2!=n+1&&a[p1]>a[p2]))
			b[i]=a[p2++];
		else b[i]=a[p1++];
	}
	for(int i=1;i<=n;i++)a[i]=b[i];
	return 0;
}
int main(){
	ios::sync_with_stdio(0);
	cin>>n>>q;
	for(int i=1;i<=n;i++)cin>>a[i];
	for(int i=1;i<=q;i++)cin>>que[i].t>>que[i].x,que[i].id=i;
	sort(que+1,que+q+1);
	int p=0;
	bool tag=0;
	for(int i=1;i<=q;i++){
		if(tag){
			ans[que[i].id]=a[que[i].x];
			continue;
		}
		while(p<que[i].t){
			if(doit()){
				tag=1;
				break;
			}
			p++;
		}
		ans[que[i].id]=a[que[i].x];
	}
	for(int i=1;i<=q;i++)cout<<ans[i]<<endl;
	return 0;
}

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