Submission #996200

#	Time	Username	Problem	Language	Result	Execution time	Memory
996200		IBory	Abracadabra (CEOI22_abracadabra)	C++17	100 / 100	850 ms	65168 KiB

Main

#include <bits/stdc++.h>
#define pii pair<int, int>
using namespace std;

const int SZ = 1 << 18;
int A[SZ], B[SZ], R[SZ], IB[SZ], ans[1000007];

struct Seg {
	int T[SZ << 1];
	void Update(int i, int v) {
		T[i += SZ - 1] = v;
		while (i >>= 1) T[i] = T[i * 2] + T[i * 2 + 1];
	}
	pii Query(int k) {
		int sL = 1, sR = SZ, n = 1;
		while (sL != sR) {
			int mid = (sL + sR) >> 1;
			if (k <= T[n * 2]) sR = mid, n = n * 2;
			else sL = mid + 1, k -= T[n * 2], n = n * 2 + 1;
		}
		return {sL, k};
	}
} T;

int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	int N, Q;
	cin >> N >> Q;
	for (int i = 1; i <= N; ++i) cin >> A[i];
	map<int, vector<pii>> P;
	for (int i = 1; i <= Q; ++i) {
		int a, b;
		cin >> a >> b;
		P[a].emplace_back(b, i);
	}

	if (P.count(0)) for (auto [a, b] : P[0]) ans[b] = A[a];

	int a = 1, b = (N / 2) + 1, idx = 1;
	while (a <= N / 2 || b <= N) {
		if (N < b) B[idx++] = A[a++];
		else if (N / 2 < a) B[idx++] = A[b++];
		else B[idx++] = A[(A[a] < A[b] ? a : b)++];
	}

	vector<int> ST;
	memset(R, 0x3f, sizeof(R));
	for (int i = 1; i <= N; ++i) {
		IB[B[i]] = i;
		while (!ST.empty() && B[ST.back()] < B[i]) {
			R[ST.back()] = i;
			ST.pop_back();
		}
		ST.push_back(i);
	}

	priority_queue<tuple<int, int, int>> PQ;
	int Z = N, l = 1;
	for (int i = 1; i <= N; ++i) {
		if (B[l] < B[i]) {
			PQ.emplace(B[l], l, i - 1);
			T.Update(B[l], i - l);
			l = i;
		}
	}
	PQ.emplace(B[l], l, N);
	T.Update(B[l], N + 1 - l);

	int turn = 1;
	while (1) {
		if (P.count(turn)) {
			for (auto [k, id] : P[turn]) {
				auto [p, off] = T.Query(k);
				ans[id] = B[IB[p] + off - 1];
			}
		}

		tuple<int, int, int> last;
		while (N / 2 < Z) {
			last = PQ.top(); PQ.pop();
			auto [_, a, b] = last;
			Z -= b - a + 1;
		}

		if (Z == N / 2) break;
		turn++;

		auto [v, a, b] = last;
		int m = a + (N / 2 - Z) - 1;
		PQ.emplace(v, a, m);
		T.Update(v, m - a + 1);

		int l = m + 1;
		while (l <= b) {
			int r = min(R[l] - 1, b);
			PQ.emplace(B[l], l, r);
			T.Update(B[l], r - l + 1);
			l = r + 1;
		}

		Z += b - a + 1;
	}

	for (auto& [_, v] : P) for (auto [k, id] : v) {
		if (ans[id]) continue;
		auto [p, off] = T.Query(k);
		ans[id] = B[IB[p] + off - 1];
	}

	for (int i = 1; i <= Q; ++i) cout << ans[i] << '\n';
	return 0;
}

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