Submission #954438

#	Time	Username	Problem	Language	Result	Execution time	Memory
954438		islingr	Abracadabra (CEOI22_abracadabra)	C++17	100 / 100	651 ms	47188 KiB

Main

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

#define rep(i, a, b) for (auto i{a}; i < (b); ++i)
#define per(i, a, b) for (auto i{b}; i-- > (a); )
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()

template <class T> bool uin(T& a, const T& b) { return a > b ? a = b, true : false; }
template <class T> bool uax(T& a, const T& b) { return a < b ? a = b, true : false; }

using ll = long long;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

constexpr int N = 2e5 + 10;
int a[N], nxt[N];

struct Node {
	Node *l = 0, *r = 0;
	int idx, len, c; int y;
	Node(int idx, int len) : idx{idx}, len{len}, c{len}, y(rng()) {}
	void pull();
};

int cnt(Node* n) { return n ? n->c : 0; }
void Node::pull() { c = cnt(l) + cnt(r) + len; }

template<class F> void each(Node* n, F f) {
	if (n) { each(n->l, f); f(n); each(n->r, f); }
}

pair<Node*, int> find_idx(Node* n, int k) {
	if (k < cnt(n->l)) return find_idx(n->l, k);
	k -= cnt(n->l);
	if (k < n->len) return {n, k};
	return find_idx(n->r, k - n->len);
}

array<Node*, 3> split_idx(Node* n, int k) {
	if (k < cnt(n->l)) {
		auto L = split_idx(n->l, k);
		n->l = L[2];
		n->pull();
		return {L[0], L[1], n};
	}
	k -= cnt(n->l);
	if (k < n->len) {
		const auto L = n->l, R = n->r;
		n->l = n->r = nullptr;
		n->pull();
		return {L, n, R};
	}
	k -= n->len;
	auto R = split_idx(n->r, k);
	n->r = R[0];
	n->pull();
	return {n, R[1], R[2]};
}

array<Node*, 2> split_val(Node *n, int k) {
	if (!n) return {};
	if (a[n->idx] >= k) {
		auto pa = split_val(n->l, k);
		n->l = pa[1];
		n->pull();
		return {pa[0], n};
	} else {
		auto pa = split_val(n->r, k);
		n->r = pa[0];
		n->pull();
		return {n, pa[1]};
	}
}

/*
   pair<Node*, Node*> split(Node* n, int k) {
   if (!n) return {};
   if (cnt(n->l) >= k) { // "n->val >= k" for lower_bound(k)
   auto pa = split(n->l, k);
   n->l = pa.second;
   n->pull();
   return {pa.first, n};
   } else {
   auto pa = split(n->r, k - cnt(n->l) - 1); // and just "k"
   n->r = pa.first;
   n->pull();
   return {n, pa.second};
   }
   }
   */

Node* merge(Node* l, Node* r) {
	if (!l) return r;
	if (!r) return l;
	if (l->y > r->y) {
		l->r = merge(l->r, r);
		l->pull();
		return l;
	} else {
		r->l = merge(l, r->l);
		r->pull();
		return r;
	}
}

signed main() {
	cin.tie(nullptr)->sync_with_stdio(false);

	int n, q;
	cin >> n >> q;

	rep(i, 0, n) cin >> a[i];

	per(i, 0, n) {
		nxt[i] = i + 1;
		while (nxt[i] < n and a[nxt[i]] < a[i])
			nxt[i] = nxt[nxt[i]];
	}

	Node* root = nullptr;
	for (int i = 0; i < n; i = nxt[i]) {
		auto node = new Node(i, nxt[i] - i);
		root = merge(root, node);
	}


	int steps = 0;
	auto do_op = [&]() -> bool {
		++steps;

		const auto [__, s] = find_idx(root, n / 2);
		if (s == 0) return true; // no change happens

		auto [L, X, R] = split_idx(root, n / 2);
		assert(X == __);

		const int r = X->idx + X->len;
		Node* LL = nullptr;

		for (int i = X->idx + s; i < r; i = nxt[i]) {
			const auto len = min(nxt[i], r) - i;
			Node *node = new Node(i, len);
			auto tmp = split_val(L, a[i]);

			LL = merge(LL, merge(tmp[0], node));
			L = tmp[1];
		}

		X->len = s;
		X->pull();
		root = merge(LL, merge(L, merge(X, R)));

		return false;
	};

	/*
	auto f = [&](Node* n) {
		rep(i, n->idx, n->idx + n->len)
			cerr << a[i] << ' ';
	};
	*/

	vector<tuple<int, int, int>> query(q);
	{
		int ctr = 0;
		for (auto &[t, i, idx] : query)
			cin >> t >> i, --i, idx = ctr++;
	}

	sort(all(query));
	vector<int> ans(q, -1);

	bool stable = false;
	for (auto [t, i, idx] : query) {
		while (not stable and steps < t)
			stable = do_op();

		const auto [node, s] = find_idx(root, i);
		ans[idx] = a[node->idx + s];
	}

	for (auto x : ans)
		cout << x << '\n';
}

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