oj.uz

Submission #1096801

# Submission time Handle Problem Language Result Execution time Memory
1096801 2024-10-05T07:22:35 Z vjudge1 Abracadabra (CEOI22_abracadabra) C++14
10 / 100
 3000 ms 28148 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1166 ms 27472 KB Output is correct
2 Correct 1153 ms 27204 KB Output is correct
3 Correct 1068 ms 26448 KB Output is correct
4 Correct 1043 ms 25172 KB Output is correct
5 Correct 1121 ms 26964 KB Output is correct
6 Correct 1049 ms 25680 KB Output is correct
7 Correct 1203 ms 27180 KB Output is correct
8 Correct 1123 ms 25688 KB Output is correct
9 Correct 1055 ms 25344 KB Output is correct
10 Correct 1110 ms 25788 KB Output is correct
11 Correct 1074 ms 25536 KB Output is correct
12 Correct 1062 ms 24660 KB Output is correct
13 Correct 1067 ms 25424 KB Output is correct
14 Correct 1088 ms 26192 KB Output is correct
15 Correct 1131 ms 26196 KB Output is correct
16 Correct 0 ms 344 KB Output is correct
17 Correct 1093 ms 24972 KB Output is correct
18 Correct 1069 ms 24660 KB Output is correct
19 Correct 0 ms 344 KB Output is correct
20 Correct 1 ms 604 KB Output is correct

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3063 ms 28148 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3043 ms 4436 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1166 ms 27472 KB Output is correct
2 Correct 1153 ms 27204 KB Output is correct
3 Correct 1068 ms 26448 KB Output is correct
4 Correct 1043 ms 25172 KB Output is correct
5 Correct 1121 ms 26964 KB Output is correct
6 Correct 1049 ms 25680 KB Output is correct
7 Correct 1203 ms 27180 KB Output is correct
8 Correct 1123 ms 25688 KB Output is correct
9 Correct 1055 ms 25344 KB Output is correct
10 Correct 1110 ms 25788 KB Output is correct
11 Correct 1074 ms 25536 KB Output is correct
12 Correct 1062 ms 24660 KB Output is correct
13 Correct 1067 ms 25424 KB Output is correct
14 Correct 1088 ms 26192 KB Output is correct
15 Correct 1131 ms 26196 KB Output is correct
16 Correct 0 ms 344 KB Output is correct
17 Correct 1093 ms 24972 KB Output is correct
18 Correct 1069 ms 24660 KB Output is correct
19 Correct 0 ms 344 KB Output is correct
20 Correct 1 ms 604 KB Output is correct
21 Execution timed out 3063 ms 28148 KB Time limit exceeded
22 Halted 0 ms 0 KB -