Submission #650881

#	Time	Username	Problem	Language	Result	Execution time	Memory
650881		Antekb	Abracadabra (CEOI22_abracadabra)	C++14	100 / 100	2805 ms	83484 KiB

Main

#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], dep[N], opt[18][N], naj[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)];
set<int> S;
int roz(int i){
	return (*S.upper_bound(i))-i;
}
void split(int i, int s){
	add(val[i], s-roz(i));
	int t=i+s;
	//deb(i, s, t);
	int k=i+roz(i);
	while(k>t){
		int l=naj[k-t];
		int j;
		if(dep[opt[l][k-(1<<l)]]<=dep[opt[l][t]])j=opt[l][k-(1<<l)];
		else j=opt[l][t];
		add(val[j], roz(j));
		S.insert(j);
		//deb(j);
		k=j;
	}
}
int main(){
	naj[1]=0;
	for(int i=2; i<N; i++)naj[i]=naj[i/2]+1;
	BOOST;
	int n, q;
	cin>>n>>q;
	vi V;
	val[0]=n+5;
	V.pb(0);
	S.insert(n+1);
	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++){
		dep[i]=dep[par[i]]+1;
		opt[0][i]=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]);
			S.insert(i);
		}
	}
	for(int k=1; k<18; k++){
		for(int i=1; i<=n; i++){
			if(i+(1<<(k-1))>n)opt[k][i]=opt[k-1][i];
			else{
				if(dep[opt[k-1][i+(1<<(k-1))]]<=dep[opt[k-1][i]])opt[k][i]=opt[k-1][i+(1<<(k-1))];
				else opt[k][i]=opt[k-1][i];
				//assert(opt[k][i]);
			}
			//cerr<<opt[k][i]<<" ";
		}
		//cerr<<"\n";
	}
	//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 i=1; i<=n; i++)cerr<<ile[N+i]<<" ";cerr<<"\n";
	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!=roz(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";
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:169:3: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  169 |   for(int i=1; i<=n; i++)cerr<<ile[N+i]<<" ";cerr<<"\n";
      |   ^~~
Main.cpp:169:46: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  169 |   for(int i=1; i<=n; i++)cerr<<ile[N+i]<<" ";cerr<<"\n";
      |                                              ^~~~

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