oj.uz

Submission #996033

# Submission time Handle Problem Language Result Execution time Memory
996033 2024-06-10T07:29:43 Z IBory Abracadabra (CEOI22_abracadabra) C++17
0 / 100
 230 ms 36532 KB 
#include <bits/stdc++.h>
#define pii pair<int, int>
using namespace std;

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

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)++];
	}
	for (int i = 1; i <= N; ++i) IB[B[i]] = 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);
		PQ.emplace(B[m + 1], m + 1, b);

		T.Update(v, N / 2 - Z);
		T.Update(B[m + 1], b - m);
		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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 214 ms 29084 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 230 ms 36532 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 15308 KB Output is correct
2 Correct 69 ms 12232 KB Output is correct
3 Correct 79 ms 13084 KB Output is correct
4 Correct 44 ms 10036 KB Output is correct
5 Correct 66 ms 13000 KB Output is correct
6 Correct 45 ms 10260 KB Output is correct
7 Incorrect 58 ms 11904 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 214 ms 29084 KB Output isn't correct
2 Halted 0 ms 0 KB -