Submission #703618

#	Time	Username	Problem	Language	Result	Execution time	Memory
703618		GusterGoose27	Abracadabra (CEOI22_abracadabra)	C++11	100 / 100	648 ms	40716 KiB

Main

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 2e5;
const int MAXQ = 1e6;
typedef pair<int, int> pii;

int nxt[MAXN];
int sz[MAXN];
int bit[2*MAXN];
int n_round;
int arr[MAXN];
int inv[MAXN];
int queries[MAXQ];
int ans[MAXQ];
pii sorted[MAXQ];
int n, q;

void upd(int x, int v) {
	for (; x < n_round; x|=(x+1)) bit[x] += v;
}

pii get_pos(int l = 0, int r = n_round, int v = n/2) { // first pos such that including it is greater than v, along with how much v left
	if (r == l+1) return pii(l, v);
	if (bit[(l+r)/2-1] > v) return get_pos(l, (l+r)/2, v);
	return get_pos((l+r)/2, r, v-bit[(l+r)/2-1]);
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	cin >> n >> q;
	n_round = 1<<(32-__builtin_clz(n-1));
	vector<int> stck;
	for (int i = 0; i < n; i++) {
		cin >> arr[i]; arr[i]--;
		inv[arr[i]] = i;
		while (!stck.empty() && arr[i] > arr[stck.back()]) {
			nxt[stck.back()] = i;
			stck.pop_back();
		}
		stck.push_back(i);
	}
	for (int v: stck) nxt[v] = n;
	int cur = 0;
	while (cur != n) {
		sz[arr[cur]] = nxt[cur]-cur;
		upd(arr[cur], sz[arr[cur]]);
		cur = nxt[cur];
	}
	for (int i = 0; i < q; i++) {
		int p, t; cin >> t >> p;
		queries[i] = p;
		sorted[i] = pii(t, i);
	}
	sort(sorted, sorted+q);
	int t = 0;
	int j = 0;
	while (j < q) {
		while (j < q && sorted[j].first == t) {
			pii p = get_pos(0, n_round, queries[sorted[j].second]-1);
			ans[sorted[j].second] = (1+arr[inv[p.first]+p.second]);
			j++;
		}
		t++;
		pii p = get_pos();
		if (p.second == 0) break; // stabilized
		upd(p.first, -sz[p.first]+p.second);
		sz[p.first] = p.second;
		int cur = inv[p.first]+p.second;
		while (cur < nxt[inv[p.first]]) {
			assert(sz[arr[cur]] == 0);
			nxt[cur] = min(nxt[cur], nxt[inv[p.first]]);
			sz[arr[cur]] = nxt[cur]-cur;
			upd(arr[cur], sz[arr[cur]]);
			cur = nxt[cur];
		}
		nxt[inv[p.first]] = inv[p.first]+p.second;
	}
	while (j < q) {
		pii p = get_pos(0, n_round, queries[sorted[j].second]-1);
		ans[sorted[j].second] = 1+arr[inv[p.first]+p.second];
		j++;
	}
	for (int i = 0; i < q; i++) cout << ans[i] << "\n";
}

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