Submission #912821

#	Time	Username	Problem	Language	Result	Execution time	Memory
912821		NK_	Abracadabra (CEOI22_abracadabra)	C++17	100 / 100	636 ms	40632 KiB

Main

// Success consists of going from failure to failure without loss of enthusiasm
#include <bits/stdc++.h>

using namespace std;

#define nl '\n'
#define pb push_back

#define f first
#define s second
#define mp make_pair
#define sz(x) int(x.size())

template<class T> using V = vector<T>;
template<class T, size_t SZ> using AR = array<T, SZ>;
using vi = V<int>;

const int INF = 1e9;

struct BIT {
	vi A; int N; void init(int n) { N = n; A = vi(N, 0); }
	void upd(int p, int x) { for(++p;p<=N;p+=p&-p) A[p - 1] += x; }
	int sum(int r) { int s = 0; for(;r;r-=r&-r) s += A[r - 1]; return s; }
	int sum(int l, int r) { return sum(r + 1) - sum(l); }
};

int main() {
	cin.tie(0)->sync_with_stdio(0);
		
	int N, Q; cin >> N >> Q;
	
	vi A(N); for(auto& x : A) { cin >> x; --x; }

	vi pos(N), nxt(N), mx(N), stk = {N};
	for(int i = 0; i < N; i++) pos[A[i]] = i;

	for(int i = 0; i < N / 2; i++) mx[i] = max(A[i], i != 0 ? mx[i - 1] : -INF); // first half
	for(int i = N / 2; i < N; i++) mx[i] = max(A[i], i != N / 2 ? mx[i - 1] : -INF); // second half

	for(int i = N - 1; i >= 0; i--) {
		while(stk.back() != N && A[stk.back()] < A[i]) stk.pop_back();
		nxt[i] = stk.back();
		stk.pb(i);
	}

	V<AR<int, 3>> qry; vi ans(Q);
	for(int q = 0; q < Q; q++) {
		int t, i; cin >> t >> i; --i;
		if (t) qry.pb(AR<int, 3>{t, i, q});
		else ans[q] = A[i] + 1;
	}

	Q = sz(qry);

	BIT B; B.init(N);
	for(int i = 0; i < N; i++) B.upd(mx[i], 1);


	auto find = [&](int x) {
		int lo = 0, hi = N - 1; 
		while(lo < hi) {
			int mid = (lo + hi) / 2;
			if (B.sum(0, mid) >= x) hi = mid;
			else lo = mid + 1;
		}
		return lo;
	};

	auto answer = [&](int x, int i) {
		int rep = find(x + 1);
		int idx = pos[rep] + (x - B.sum(0, rep - 1));
		ans[i] = A[idx] + 1;
	};

	sort(begin(qry), end(qry));

	int t = 1, q = 0;
	while(q < Q) {

		// cout << t << endl;
		// for(int i = 0; i < N; i++) cout << i << " => " << B.sum(i, i) << endl;
		// cout << endl;

		while(q < Q && qry[q][0] <= t) {
			answer(qry[q][1], qry[q][2]); q++;
		} 

		int mid = find(N / 2); 
		int ex = B.sum(0, mid) - N / 2, bnd = pos[mid] + B.sum(mid, mid); B.upd(mid, -ex);

		if (ex == 0) {
			t = INF; continue;
		}

		int x = pos[mid] + B.sum(mid, mid); 
		while(x < bnd) {
			int nxtx = min(nxt[x], bnd);
			int amt = nxtx - x; B.upd(A[x], amt);
			x = nxtx;
		}

		++t;
	}

	for(auto& x : ans) cout << x << nl;

	exit(0-0);
}

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