Submission #943648

#	Time	Username	Problem	Language	Result	Execution time	Memory
943648		MinaRagy06	Abracadabra (CEOI22_abracadabra)	C++17	10 / 100	3073 ms	25844 KiB

Main

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

const int N = 200'005;
vector<array<int, 2>> ask[N];
int a[N], ans[1'000'005];
struct segtree {
	int leaf[N];
	int n;
	void init(int _n) {
		n = _n;
		for (int i = 0; i < n; i++) {
			leaf[i] = 0;
		}
	}
	void upd(int i, int x) {
		leaf[i] = x;
	}
	array<int, 2> get(int p) {
		for (int i = 0; i < n; i++) {
			if (p < leaf[i]) {
				return {i, p};
			} else {
				p -= leaf[i];
			}
		}
	}
	int get2(int p) {
		return leaf[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);
	}
	set<array<int, 2>> s;
	seg.init(n + 1);
	for (int i = 0; i < n; i = nxt[i]) {
		seg.upd(a[i], nxt[i] - i);
		s.insert({a[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;
}

Compilation message (stderr)

Main.cpp: In member function 'std::array<int, 2> segtree::get(int)':
Main.cpp:28:2: warning: control reaches end of non-void function [-Wreturn-type]
   28 |  }
      |  ^

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