Submission #949052

#	Time	Username	Problem	Language	Result	Execution time	Memory
949052		TAhmed33	Abracadabra (CEOI22_abracadabra)	C++98	100 / 100	769 ms	51408 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define mid ((l + r) >> 1)
#define tl (node + 1)
#define tr (node + 2 * (mid - l + 1))
const int MAXN = 2e5 + 25;
array <int, 3> v[MAXN << 2];
const int MAXQ = 1e6 + 25;
int n, q;
array <int, 3> queries[MAXQ];
int a[MAXN], nxt[MAXN];	
int cnt = 0;
int ans[MAXQ];
int get (array <int, 3> z) {
	return lower_bound(v + 1, v + cnt + 1, z) - v;
}
struct SegmentTree {
	int tree[MAXN << 3];
	void update (int l, int r, int a, int b, int node) {
		if (l > a || r < a) return;
		if (l == r) {
			tree[node] += b;
			return;
		}
		update(l, mid, a, b, tl); update(mid + 1, r, a, b, tr);
		tree[node] = tree[tl] + tree[tr];
	}
	int get (int l, int r, int a, int node) {
		if (l == r) return l;
		if (tree[tl] >= a) return get(l, mid, a, tl);
		return get(mid + 1, r, a - tree[tl], tr);
	}
	int query (int l, int r, int a, int b, int node) {
		if (a > b) return 0;
		if (l > b || r < a) return 0;
		if (l >= a && r <= b) return tree[node];
		return query(l, mid, a, b, tl) + query(mid + 1, r, a, b, tr);
	}
} cur;
void ins (array <int, 3> x) {
	int z = get(x);
	cur.update(1, cnt, z, x[2] - x[1] + 1, 1);
}
void rem (array <int, 3> x) {
	int z = get(x);
	cur.update(1, cnt, z, -(x[2] - x[1] + 1), 1);
}
int main () {
	ios::sync_with_stdio(0); cin.tie(0);
	cin >> n >> q;
	for (int i = 1; i <= n; i++) cin >> a[i];
	stack <int> cur2;
	for (int i = 1; i <= n; i++) {
		while (!cur2.empty() && a[cur2.top()] < a[i]) {
			nxt[cur2.top()] = i;
			cur2.pop();
		}
		cur2.push(i);
	}
	for (int i = 1; i <= q; i++) {
		cin >> queries[i][0] >> queries[i][1]; queries[i][2] = i;
		queries[i][0] = min(queries[i][0], n);
	}
	sort(queries + 1, queries + q + 1);
	int sum = 0;
	priority_queue <array <int, 3>> pq;
	for (int i = 1; i != 0; i = nxt[i]) {
		if (nxt[i] == 0) pq.push({a[i], i, n}), v[++cnt] = {a[i], i, n};
		else pq.push({a[i], i, nxt[i] - 1}), v[++cnt] = {a[i], i, nxt[i] - 1};
	}
	while (!pq.empty()) {
		if (sum == n / 2) break;
		auto z = pq.top(); pq.pop();
		if (sum + z[2] - z[1] + 1 <= n / 2) {
			sum += z[2] - z[1] + 1; continue;
		}
		int s = n / 2 - sum, l = z[2] - z[1] + 1;
		int dd = l - s;
		pq.push({a[z[1]], z[1], z[1] + dd - 1}); v[++cnt] = {a[z[1]], z[1], z[1] + dd - 1};
		z[1] += dd;
		for (int i = z[1]; i && i <= z[2]; i = nxt[i]) {
			if (nxt[i]) {
				pq.push({a[i], i, min(nxt[i] - 1, z[2])}); v[++cnt] = {a[i], i, min(nxt[i] - 1, z[2])};
			} else {
				pq.push({a[i], i, z[2]}); v[++cnt] = {a[i], i, z[2]};
			}
		}
	}
	sort(v + 1, v + cnt + 1);
	while (!pq.empty()) pq.pop();
	sum = 0;
	for (int i = 1; i != 0; i = nxt[i]) {
		if (nxt[i] == 0) pq.push({a[i], i, n}), ins({a[i], i, n});
		else pq.push({a[i], i, nxt[i] - 1}), ins({a[i], i, nxt[i] - 1});
	}
	int ptr = 1;
	while (ptr <= q && queries[ptr][0] == 0) {
		int u = cur.get(1, cnt, queries[ptr][1], 1);
		int g = queries[ptr][1] - cur.query(1, cnt, 1, u - 1, 1);
		ans[queries[ptr][2]] = v[u][1] + g - 1;
		ptr++;
	}
	for (int i = 1; i <= n; i++) {
		while (!pq.empty()) {
			if (sum == n / 2) break;
			auto z = pq.top(); pq.pop();
			if (sum + z[2] - z[1] + 1 <= n / 2) {
				sum += z[2] - z[1] + 1; continue;
			}
			rem(z);
			int s = n / 2 - sum, l = z[2] - z[1] + 1;
			int dd = l - s;
			pq.push({a[z[1]], z[1], z[1] + dd - 1}); ins({a[z[1]], z[1], z[1] + dd - 1});
			z[1] += dd;
			for (int i = z[1]; i && i <= z[2]; i = nxt[i]) {
				if (nxt[i]) {
					pq.push({a[i], i, min(nxt[i] - 1, z[2])}); ins({a[i], i, min(nxt[i] - 1, z[2])});
				} else {
					pq.push({a[i], i, z[2]}); ins({a[i], i, z[2]});
				}
			}
			break;
		}
		while (ptr <= q && queries[ptr][0] == i) {
			int u = cur.get(1, cnt, queries[ptr][1], 1);
			int g = queries[ptr][1] - cur.query(1, cnt, 1, u - 1, 1);
			ans[queries[ptr][2]] = v[u][1] + g - 1;
			ptr++;
		}
	}
	for (int i = 1; i <= q; i++) cout << a[ans[i]] << '\n';
}

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