Submission #1054517

#	Time	Username	Problem	Language	Result	Execution time	Memory
1054517		hotboy2703	Abracadabra (CEOI22_abracadabra)	C++17	0 / 100	225 ms	53716 KiB

Main

#include<bits/stdc++.h>
using ll = long long;
using namespace std;
#define pll pair <ll,ll>
#define fi first
#define se second
#define MP make_pair
#define sz(a) (ll((a).size()))
#define BIT(mask,i) (((mask) >> (i))&1)
#define MASK(i) (1LL << (i))	
const ll MAXN = 2e5+100;
ll n,q;
pair <pll,ll> all[1'000'100];
ll ans[1'000'100];
ll p[MAXN],pos[MAXN];
ll nxt[MAXN];
ll tree[MAXN*4];
void update(ll id,ll l,ll r,ll i,ll v){
	if (l > i || r < i)return;
	if (l == r){
		tree[id]+=v;
		return;
	}
	ll mid = (l + r) >> 1;
	update(id<<1,l,mid,i,v);
	update(id<<1|1,mid+1,r,i,v);
	tree[id] = tree[id<<1] + tree[id<<1|1];
}
pair <ll,pll> get(ll id,ll l,ll r,ll k){
	if (l == r)return MP(l,MP(k,tree[id]));
	ll mid = (l + r) >> 1;
	if (tree[id<<1] >= k)return get(id<<1,l,mid,k);
	else return get(id<<1|1,mid+1,r,k-tree[id<<1]);
}
int main(){
	ios_base::sync_with_stdio(0);cin.tie(nullptr);
	cin>>n>>q;
	for (ll i = 1;i <= n;i ++){cin>>p[i];pos[p[i]] = i;}
	deque <ll> max1;
	for (ll i = n;i >= 1;i --){
		while (!max1.empty() && p[max1.back()] < p[i])max1.pop_back();
		if (max1.empty())nxt[i] = n+1;
		else nxt[i] = max1.back();
		max1.push_back(i);
	}
	set <pll> L,R;
	{
		ll cur = 1;
		while (cur <= n){
			pll x = MP(p[cur],nxt[cur]-cur);
			update(1,1,n,x.fi,x.se);
			cur = nxt[cur];
		}
	}
	for (ll i = 1;i <= q;i ++){
		cin>>all[i].fi.fi>>all[i].fi.se;
		all[i].fi.se = min(all[i].fi.se,n);
		all[i].se = i;
	}
	sort(all+1,all+1+q);
	for (ll i = 0,ptr = 1;i <= n;i ++){
		while (ptr<=q&&all[ptr].fi.fi == i){
			pair <ll,pll> tmp = get(1,1,n,all[ptr].fi.se);
			ans[all[ptr].se] = p[pos[tmp.fi] + tmp.se.fi - 1];
			ptr++;
		}
		pair <ll,pll> tmp = get(1,1,n,n/2+1);
		update(1,1,n,tmp.fi,-tmp.se.se+(tmp.se.fi-1));
		ll cur = pos[tmp.fi] + tmp.se.fi - 1;
		ll r = pos[tmp.fi] + tmp.se.se - 1;
		while (cur <= r){
			pll x = MP(p[cur],nxt[cur]-cur);
			update(1,1,n,x.fi,x.se);
			cur = nxt[cur];
		}
		// cout<<i<<' '<<ptr<<endl;
	}
	for (ll i = 1;i <= q;i ++)cout<<ans[i]<<'\n';
}

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