oj.uz

Submission #650867

# Submission time Handle Problem Language Result Execution time Memory
650867 2022-10-15T22:12:14 Z Antekb Abracadabra (CEOI22_abracadabra) C++14
10 / 100
 3000 ms 45156 KB 
#include<bits/stdc++.h>
 
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("trapv")
 
#define st first
#define nd second
#define pb push_back
#define pp pop_back
#define eb emplace_back
#define mp(a, b) make_pair(a, b)
#define all(x) (x).begin(), (x).end()
#define rev(x) reverse(all(x))
#define sor(x) sort(all(x))
#define sz(x) (int)(x).size()
#define rsz(x) resize(x)
 
using namespace std;
 
///~~~~~~~~~~~~~~~~~~~~~~~~~~
 
template <typename H, typename T> 
ostream& operator<<(ostream& os, pair<H, T> m){
	return os <<"("<< m.st<<", "<<m.nd<<")";
}
template <typename H> 
ostream& operator<<(ostream& os, vector<H> V){
	os<<"{";
	for(int i=0; i<V.size(); i++){
		if(i)os<<" ";
		os<<V[i];
	}
	os<<"}";
	return os;
}
 
void debug(){cerr<<"\n";}
template <typename H, typename... T>
void debug(H h, T... t) {cerr<<h; if (sizeof...(t)) cerr << ", "; debug(t...);}
#define deb(x...) cerr<<#x<<" = ";debug(x);
 
///~~~~~~~~~~~~~~~~~~~~~~~~~
 
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<pii > vii;
typedef vector<ll> vl;
typedef vector<pll> vll;
typedef string str;
 
#define BOOST ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
 
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
 
const int N=(1<<18), INF=1e9+5, mod=1e9+7;
int val[N], ile[N+N], par[N], siz[N], gdzie[N];
vi co[N], sum[N];
void add(int i, int v){
	for(i+=N; i; i>>=1){
		ile[i]+=v;
	}
}
pair<int, int> find(int s){
	int v=1;
	while(v<N){
		if(ile[v+v]<s){
			s-=ile[v+v];
			v=v+v+1;
		}
		else v=v+v;
	}
	return mp(v-N, s);
}
void split(int i, int a){
	assert(a!=siz[i]);
	//deb(i, siz[i], a);
	add(val[i], a-siz[i]);
	while(siz[i]>a){
		int j=co[i].back();
		co[i].pp();
		siz[i]-=siz[j];
		add(val[j], siz[j]);
		if(siz[i]<a){
			split(j, a-siz[i]);
			siz[i]+=siz[j];
			co[i].pb(j);
			add(val[j], -siz[j]);
		}
	}
	//add(val[i], siz[i]);
}
int ans[int(1e6+5)];
int main(){
	BOOST;
	int n, q;
	cin>>n>>q;
	vi V;
	val[0]=n+5;
	V.pb(0);
	for(int i=1; i<=n; i++){
		cin>>val[i];
		gdzie[val[i]]=i;
		while(val[V.back()]<val[i])V.pp();
		par[i]=V.back();
		V.pb(i);
	}
	for(int i=n; i>0; i--){
		siz[i]++;
		siz[par[i]]+=siz[i];
		co[i].pb(i);
		//sum[i].pb(1);
	}
	for(int i=1; i<=n; i++){
		co[par[i]].pb(i);
		//sum[par[i]].pb(sum[par[i]].back()+siz[i]);
		if(par[i]==0){
			add(val[i], siz[i]);
		}
	}
	//deb(co[6]);
	vector<pair<pii, int> > Q(q);
	for(int qq=0; qq<q; qq++){
		cin>>Q[qq].st.st>>Q[qq].st.nd;
		Q[qq].nd=qq;
	}
	sor(Q);
	int wsk=0;
	for(int t=0; ;t++){
		assert(ile[1]==n);
		bool b=1;
		while(wsk<q && Q[wsk].st.st==t){
			pii a=find(Q[wsk].st.nd);
			//deb(a, Q[wsk]);
			ans[Q[wsk].nd]=val[gdzie[a.st]+a.nd-1];
			wsk++;
		}
		b=0;
		pii c=find(n/2);
		if(c.nd!=siz[gdzie[c.st]])split(gdzie[c.st], c.nd), b=1;
		//for(int i=1; i<=n; i++)cerr<<ile[N+i]<<" ";cerr<<"\n";
		if(!b){
			while(wsk<q){
				pii a=find(Q[wsk].st.nd);
				deb(a, wsk);
				ans[Q[wsk].nd]=val[gdzie[a.st]+a.nd-1];
				wsk++;
			}
			break;
		}
	}
	for(int i=0; i<q; i++)cout<<ans[i]<<"\n";
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 505 ms 32700 KB Output is correct
2 Correct 507 ms 36524 KB Output is correct
3 Correct 483 ms 35548 KB Output is correct
4 Correct 463 ms 37772 KB Output is correct
5 Correct 460 ms 38268 KB Output is correct
6 Correct 432 ms 37332 KB Output is correct
7 Correct 472 ms 37340 KB Output is correct
8 Correct 476 ms 36652 KB Output is correct
9 Correct 456 ms 36932 KB Output is correct
10 Correct 452 ms 36940 KB Output is correct
11 Correct 460 ms 36720 KB Output is correct
12 Correct 435 ms 36180 KB Output is correct
13 Correct 474 ms 36412 KB Output is correct
14 Correct 483 ms 38636 KB Output is correct
15 Correct 487 ms 38840 KB Output is correct
16 Correct 7 ms 12780 KB Output is correct
17 Correct 436 ms 37228 KB Output is correct
18 Correct 429 ms 37100 KB Output is correct
19 Correct 7 ms 12628 KB Output is correct
20 Correct 7 ms 12704 KB Output is correct

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3075 ms 45156 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 3067 ms 24532 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 505 ms 32700 KB Output is correct
2 Correct 507 ms 36524 KB Output is correct
3 Correct 483 ms 35548 KB Output is correct
4 Correct 463 ms 37772 KB Output is correct
5 Correct 460 ms 38268 KB Output is correct
6 Correct 432 ms 37332 KB Output is correct
7 Correct 472 ms 37340 KB Output is correct
8 Correct 476 ms 36652 KB Output is correct
9 Correct 456 ms 36932 KB Output is correct
10 Correct 452 ms 36940 KB Output is correct
11 Correct 460 ms 36720 KB Output is correct
12 Correct 435 ms 36180 KB Output is correct
13 Correct 474 ms 36412 KB Output is correct
14 Correct 483 ms 38636 KB Output is correct
15 Correct 487 ms 38840 KB Output is correct
16 Correct 7 ms 12780 KB Output is correct
17 Correct 436 ms 37228 KB Output is correct
18 Correct 429 ms 37100 KB Output is correct
19 Correct 7 ms 12628 KB Output is correct
20 Correct 7 ms 12704 KB Output is correct
21 Execution timed out 3075 ms 45156 KB Time limit exceeded
22 Halted 0 ms 0 KB -