Submission #943649

#	Time	Username	Problem	Language	Result	Execution time	Memory
943649		MinaRagy06	Abracadabra (CEOI22_abracadabra)	C++17	100 / 100	436 ms	48692 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define md ((l + r) >> 1)

const int N = 200'005;
vector<array<int, 2>> ask[N];
int a[N], ans[1'000'005];
struct segtree {
	int seg[1 << 19];
	int n;
	void build(int i, int l, int r) {
		if (l == r) {
			seg[i] = 0;
			return;
		}
		build(i << 1, l, md);
		build(i << 1 | 1, md + 1, r);
		seg[i] = seg[i << 1] + seg[i << 1 | 1];
	}
	void init(int _n) {
		n = _n;
		build(1, 0, n - 1);
	}
	void upd(int i, int l, int r, int p, int x) {
		if (l == r) {
			seg[i] = x;
			return;
		}
		if (p <= md) {
			upd(i << 1, l, md, p, x);
		} else {
			upd(i << 1 | 1, md + 1, r, p, x);
		}
		seg[i] = seg[i << 1] + seg[i << 1 | 1];
	}
	void upd(int i, int x) {
		upd(1, 0, n - 1, i, x);
	}
	array<int, 2> get(int i, int l, int r, int p) {
		if (l == r) {
			return {l, p};
		}
		if (p < seg[i << 1]) {
			return get(i << 1, l, md, p);
		} else {
			return get(i << 1 | 1, md + 1, r, p - seg[i << 1]);
		}
	}
	array<int, 2> get(int p) {
		return get(1, 0, n - 1, p);
	}
	int get2(int i, int l, int r, int p) {
		if (l == r) {
			return seg[i];
		}
		if (p <= md) {
			return get2(i << 1, l, md, p);
		} else {
			return get2(i << 1 | 1, md + 1, r, p);
		}
	}
	int get2(int p) {
		return get2(1, 0, n - 1, p);
	}
} seg;
int main() {
	ios_base::sync_with_stdio(0), cin.tie(0);
	int n, q;
	cin >> n >> q;
	int pos[n + 1];
	for (int i = 0; i < n; i++) {
		cin >> a[i];
		pos[a[i]] = i;
	}
	for (int i = 0; i < q; i++) {
		int t, p;
		cin >> t >> p;
		t = min(t, n);
		ask[t].push_back({p - 1, i});
	}
	int nxt[n]{};
	stack<int> st;
	a[n] = 1e9;
	st.push(n);
	for (int i = n - 1; i >= 0; i--) {
		while (a[i] > a[st.top()]) st.pop();
		nxt[i] = st.top();
		st.push(i);
	}
	seg.init(n + 1);
	for (int i = 0; i < n; i = nxt[i]) {
		seg.upd(a[i], nxt[i] - i);
	}
	bool isover = 0;
	for (int j = 0; j <= n; j++) {
		for (auto [p, idx] : ask[j]) {
			auto [i, v] = seg.get(p);
			ans[idx] = a[pos[i] + v];
		}
		if (isover) continue;
		int cur = n / 2;
		array<int, 2> V = seg.get(cur);
		int i = pos[V[0]];
		cur = V[1];
		if (cur == 0) {
			isover = 1;
			continue;
		}
		int mx = i + seg.get2(a[i]);
		seg.upd(a[i], cur);
		cur = i + cur;
		while (cur < n && seg.get2(a[cur]) == 0) {
			int newcur = min(nxt[cur], mx);
			seg.upd(a[cur], newcur - cur);
			cur = newcur;
		}
	}
	for (int i = 0; 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