oj.uz

Submission #936440

# Submission time Handle Problem Language Result Execution time Memory
936440 2024-03-01T19:29:53 Z JuanJL Abracadabra (CEOI22_abracadabra) C++17
10 / 100
 529 ms 524288 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp> 

#define fst first 
#define snd second
#define pb push_back
#define forn(i,a,b) for(int i = a; i < b; i++)
#define ALL(x) x.begin(),x.end()
#define SZ(x) (int)x.size()
#define mset(a,v) memset((a),(v),sizeof(a))
#define FIN ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define dbg(v) cout<<"Line("<<__LINE__<<"): "<<#v<<" = "<<v<<'\n';
#define pi pair<int,int>
#define pll pair<ll,ll>
typedef long long ll;
using namespace std;
using namespace __gnu_pbds;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> indexed_set;
typedef tree<int,null_type,less_equal<int>,rb_tree_tag,tree_order_statistics_node_update> indexed_multiset;

int main(){FIN;
	ll n,q; cin>>n>>q;
	vector<vector<ll>> states;
	states.pb({});
	states[0].resize(n);
	forn(i,0,n) cin>>states[0][i];
	
	bool repeat=false;
	while(!repeat){
		
		queue<ll> A,B;
		forn(i,0,n/2) A.push(states[SZ(states)-1][i]);
		forn(i,n/2,n) B.push(states[SZ(states)-1][i]);
		
		states.pb({});
		states[SZ(states)-1].resize(n);
		
		forn(i,0,n){
			if(A.empty()){
				states[SZ(states)-1][i]=B.front();	B.pop();
			}else if(B.empty()){
				states[SZ(states)-1][i]=A.front();	A.pop();
			}else if(A.front()<B.front()){
				states[SZ(states)-1][i]=A.front();	A.pop();
			}else{
				states[SZ(states)-1][i]=B.front();	B.pop();
			}
		}
		repeat = true;
		ll maxi = 0;
		forn(i,0,n/2) maxi = max(maxi,states[SZ(states)-1][i]);
		if(states[SZ(states)-1][n/2]<maxi) repeat = false;
	}
	
	ll t, i;
	while(q--){
		cin>>t>>i;
		if(SZ(states)<=t){
			cout<<states[SZ(states)-1][i-1]<<'\n';
		}else{
			cout<<states[t][i-1]<<'\n';
		}
	}
	
	return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 202 ms 16264 KB Output is correct
2 Correct 166 ms 10008 KB Output is correct
3 Correct 158 ms 11632 KB Output is correct
4 Correct 145 ms 7508 KB Output is correct
5 Correct 165 ms 9512 KB Output is correct
6 Correct 160 ms 8432 KB Output is correct
7 Correct 167 ms 9552 KB Output is correct
8 Correct 148 ms 8340 KB Output is correct
9 Correct 143 ms 7760 KB Output is correct
10 Correct 147 ms 8120 KB Output is correct
11 Correct 146 ms 8276 KB Output is correct
12 Correct 143 ms 7252 KB Output is correct
13 Correct 157 ms 7504 KB Output is correct
14 Correct 165 ms 8532 KB Output is correct
15 Correct 150 ms 7600 KB Output is correct
16 Correct 0 ms 344 KB Output is correct
17 Correct 144 ms 7252 KB Output is correct
18 Correct 149 ms 7252 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Runtime error 529 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 477 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 202 ms 16264 KB Output is correct
2 Correct 166 ms 10008 KB Output is correct
3 Correct 158 ms 11632 KB Output is correct
4 Correct 145 ms 7508 KB Output is correct
5 Correct 165 ms 9512 KB Output is correct
6 Correct 160 ms 8432 KB Output is correct
7 Correct 167 ms 9552 KB Output is correct
8 Correct 148 ms 8340 KB Output is correct
9 Correct 143 ms 7760 KB Output is correct
10 Correct 147 ms 8120 KB Output is correct
11 Correct 146 ms 8276 KB Output is correct
12 Correct 143 ms 7252 KB Output is correct
13 Correct 157 ms 7504 KB Output is correct
14 Correct 165 ms 8532 KB Output is correct
15 Correct 150 ms 7600 KB Output is correct
16 Correct 0 ms 344 KB Output is correct
17 Correct 144 ms 7252 KB Output is correct
18 Correct 149 ms 7252 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Runtime error 529 ms 524288 KB Execution killed with signal 9
22 Halted 0 ms 0 KB -