Submission #1046394

#	Time	Username	Problem	Language	Result	Execution time	Memory
1046394		Tob	Abracadabra (CEOI22_abracadabra)	C++14	100 / 100	393 ms	80540 KiB

Main

#include <bits/stdc++.h>

#define F first
#define S second
#define all(x) x.begin(), x.end()
#define pb push_back
#define FIO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)

using namespace std;

typedef long long ll;
typedef pair <ll, ll> pii;

const int N = 2e5 + 7, Q = 1e6 + 7;

int n, q;
int a[N], a_[N], res[Q], gr[N], fen[N];
pii g[N];
vector <pii> qu[Q];

void add(int x, int val) {for (; x < N; x += x & -x) fen[x] += val;}
int get(int x) {
	int out = 0;
	for (; x; x -= x & -x) out += fen[x];
	return out;
}
int kth(int k) {
	int sum = 0, x = 0;
	for (int i = 17; i >= 0; i--) {
		if (x+(1<<i) >= N) continue;
		if (sum + fen[x+(1<<i)] <= k) {x += (1 << i); sum += fen[x];}
	}
	return x+1;
}

int main () {
	FIO;
	cin >> n >> q;
	
	for (int i = 0; i < n; i++) cin >> a_[i];
	
	for (int i = 0; i < q; i++) {
		int t, x; cin >> t >> x; x--;
		qu[min(n, t)].pb({x, i});
	}
	for (auto x : qu[0]) res[x.S] = a_[x.F];
	
	for (int i = 0, n1 = 0, n2 = 0; i < n; i++) {
		if (n2 == n/2 || (n1 < n/2 && a_[n1] < a_[n/2+n2])) a[i] = a_[n1++];
		else a[i] = a_[n/2+n2++];
	}
	
	for (auto x : qu[1]) res[x.S] = a[x.F];
	
	stack <int> st;
	for (int i = 0; i < n; i++) {
		while (!st.empty() && a[st.top()] < a[i]) {
			gr[a[st.top()]] = i;
			st.pop();
		}
		st.push(i);
	}
	while (!st.empty()) {
		gr[a[st.top()]] = n;
		st.pop();
	}
	
	for (int i = 0; i < n; i = gr[a[i]]) {
		g[a[i]] = {i, gr[a[i]]-1};
		add(a[i], gr[a[i]]-i);
	}
	
	for (int i = 2; i <= n; i++) {
		int x = kth(n/2);
		int y = get(x-1);
		if (y < n/2) {
			int l = g[x].F, r = g[x].S;
			add(x, n/2-y-r+l-1);
			l += n/2-y;
			g[x].S = l-1;
			for (int j = l; j <= r; j = gr[a[j]]) {
				add(a[j], min(r+1, gr[a[j]])-j);
				g[a[j]] = {j, min(r, gr[a[j]]-1)};
			}
		}
		for (auto z : qu[i]) {
			int h = kth(z.F);
			res[z.S] = a[g[h].F+z.F-get(h-1)];
		}
	}
	
	for (int i = 0; i < q; i++) cout << res[i] << "\n";

	return 0;
}

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