Submission #673843

#	Time	Username	Problem	Language	Result	Execution time	Memory
673843		vjudge1	Abracadabra (CEOI22_abracadabra)	C++14	0 / 100	257 ms	54288 KiB

Main

#include<bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define pb push_back
#define pii pair<int,int>
#define mp make_pair

const int maxn = 200500;

int n, q, a[maxn], nxt[maxn], pos[maxn], res[maxn];
stack<int> st;
vector<pii> que[maxn];

struct seg_tree {
	vector<int> t, len;
	seg_tree() {
		t.resize(4 * maxn);
		len.resize(maxn);
	}
	void update(int pos, int val, int v = 1, int l = 1, int r = maxn - 1) {
		if (l == r) {
			len[l] += val;
			t[v] += val;
			return;
		}
		int m = (l + r) / 2;
		if (pos <= m) update(pos, val, 2 * v, l, m);
		else update(pos, val, 2 * v + 1, m + 1, r);
		t[v] = t[2 * v] + t[2 * v + 1];
	}
	pii get(int k, int v = 1, int l = 1, int r = maxn - 1) {
		if (l == r)
			return mp(l, k);
		int m = (l + r) / 2;
		if (t[2 * v] >= k)
			return get(k, 2 * v, l, m);
		k -= t[2 * v];
		return get(k, 2 * v + 1, m + 1, r);
	}
} IT;

int main() 
{
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin >> n >> q;
	for (int i = 1; i <= n; i++) 
		cin >> a[i], pos[a[i]] = i;
	for (int i = 1, time, pos; i <= q; i++) {
		cin >> time >> pos;
		if (!time) {
			res[i] = a[pos];
			continue;
		}
		time = min(time, n + 1);
		que[time].pb({i, pos});
	}
	st.push(n + 1); a[n + 1] = n + 1;
	for (int i = n; i >= 1; i--) {
		while (a[i] > a[st.top()]) st.pop();
		nxt[i] = st.top();
		st.push(i);
	}
	for (int i = 1; i <= n; i = nxt[i])
		IT.update(a[i], nxt[i] - i);
	int lim;
	for (lim = 1; lim <= n; lim++) {
		auto it = IT.get(n / 2 + 1);
		if (it.se == 1) break;
		int x = pos[it.fi] + it.se - 1;
		for (int i = x; i < pos[it.fi] + IT.len[it.fi]; i = nxt[i])
			IT.update(a[i], nxt[i] - i);
		IT.update(it.fi, -IT.len[it.fi] + it.se - 1);
		for (auto it : que[lim]) {
			auto x = IT.get(it.se);
			res[it.fi] = a[pos[x.fi] + x.se - 1];
		}
	}
	for (int i = lim; i <= n + 1; i++)
		for (auto it : que[i]) {
			auto x = IT.get(it.se);
			res[it.fi] = a[pos[x.fi] + x.se - 1];
		}
	for (int i = 1; i <= q; i++)
		cout << res[i] << '\n';
}

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