Submission #725898

#	Time	Username	Problem	Language	Result	Execution time	Memory
725898		amunduzbaev	Abracadabra (CEOI22_abracadabra)	C++17	100 / 100	1012 ms	63140 KiB

Main

#include "bits/stdc++.h"
using namespace std;
 
#define ar array
typedef long long ll;
#define int ll

const int N = 2e5 + 5;
struct ST{
	int tree[N << 2];
	
	void add(int i, int v, int lx = 0, int rx = N, int x = 1){
		if(lx == rx){
			tree[x] += v; return;
		}
		int m = (lx + rx) >> 1;
		if(i <= m) add(i, v, lx, m, x << 1);
		else add(i, v, m + 1, rx, x << 1 | 1);
		tree[x] = tree[x << 1] + tree[x << 1 | 1];
	}
	
	int sum(int l, int r, int lx = 0, int rx = N, int x = 1){
		if(lx > r || rx < l) return 0;
		if(lx >= l && rx <= r) return tree[x];
		int m = (lx + rx) >> 1;
		return sum(l, r, lx, m, x << 1) + sum(l, r, m + 1, rx, x << 1 | 1);
	}
	
	int get(int v, int lx = 0, int rx = N, int x = 1){
		if(lx == rx) return lx;
		int m = (lx + rx) >> 1;
		if(tree[x << 1] > v) return get(v, lx, m, x << 1);
		else return get(v - tree[x << 1], m + 1, rx, x << 1 | 1);
	}
}tree;

signed main(){
	ios::sync_with_stdio(0); cin.tie(0);
	
	int n, q; cin >> n >> q;
	vector<int> a(n);
	for(int i=0;i<n;i++){
		cin >> a[i]; a[i]--;
	}
	
	vector<int> t(q), id(q);
	vector<int> p(q), res(q, -1);
	for(int i=0;i<q;i++){
		cin >> t[i] >> id[i]; --id[i];
		p[i] = i;
	}
	
	sort(p.begin(), p.end(), [&](int i, int j){
		if(t[i] != t[j]) return t[i] < t[j];
		else return id[i] < id[j];
	});
	int j = 0;
	while(j < q && t[p[j]] == 0){
		res[p[j]] = a[id[p[j]]];
		j++;
	}
	vector<int> cnt(n), pos(n), par(n, n), ss;
	for(int i=n-1;~i;i--){
		pos[a[i]] = i;
		while(!ss.empty() && a[ss.back()] < a[i]) ss.pop_back();
		if(!ss.empty()) par[i] = ss.back();
		ss.push_back(i);
	}
	{
		int i = 0, m = n / 2;
		while(i < m){
			cnt[a[i]] = min(m, par[i]) - i;
			tree.add(a[i], cnt[a[i]]);
			i = par[i];
		}
		i = m;
		while(i < n){
			cnt[a[i]] = par[i] - i;
			tree.add(a[i], cnt[a[i]]);
			i = par[i];
		}
	}
	
		//~ for(int i=0;i<n;i++){
			//~ cout<<cnt[i]<<" ";
		//~ } cout<<"\n";
	for(int i=1;i<=n;i++){
		while(j < q && t[p[j]] == i){
			int k = tree.get(id[p[j]]), sum = (k ? tree.sum(0, k - 1) : 0);
			res[p[j]] = a[pos[k] + (id[p[j]] - sum)];
			j++;
		}
		int P = tree.get(n / 2 - 1);
		int rem = tree.sum(0, P) - n / 2;
		
		if(!rem){
			break;
		}
		//~ cout<<P<<" "<<rem<<endl;
		cnt[P] -= rem;
		tree.add(P, -rem);
		P = pos[P] + cnt[P];
		int k = P; P += rem;
		while(k < P){
			//~ assert(!cnt[a[k]]);
			cnt[a[k]] = min(P, par[k]) - k;
			//~ assert(!tree.sum(a[k], a[k]));
			tree.add(a[k], cnt[a[k]] - tree.sum(a[k], a[k]));
			k = par[k];
		}
		//~ for(int i=0;i<n;i++){
			//~ cout<<cnt[i]<<" ";
		//~ } cout<<"\n";
	}
	
	while(j < q){
		int k = tree.get(id[p[j]]), sum = (k ? tree.sum(0, k - 1) : 0);
		res[p[j]] = a[pos[k] + (id[p[j]] - sum)];
		j++;
	}
	for(int i=0;i<q;i++){
		cout<<++res[i]<<"\n";
	}
}

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