Submission #791674

#	Time	Username	Problem	Language	Result	Execution time	Memory
791674		khshg	Abracadabra (CEOI22_abracadabra)	C++14	Compilation error	0 ms	0 KiB

Main

#include<bits/stdc++.h>
using namespace std;
typedef tree<array<int, 3>, null_type, less<array<int, 3>>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

int N, Q;
int cur;
vector<int> A, nxtg, subans;
vector<pair<int, int>> q;
ordered_set S;// original segment {L, R};
template<typename T>
struct fenwick_tree {
	int N;
	T E;
	vector<T> bit;
	fenwick_tree(int n, T e = 0) { // empty!?
		swap(n, N);
		swap(e, E);
		bit.resize(N + 1, E);
	}
	void add(int ind, T val) {
		++ind;
		while(ind <= N) {
			bit[ind] += val;
			ind += ind & -ind;
		}
	}
	T pref_sum(int ind) {
		T total = E;
		++ind;
		while(ind > 0) {
			total += bit[ind];
			ind -= ind & -ind;
		}
		return total;
	}
	T query(int L, int R) {
		return pref_sum(R) - pref_sum(L - 1);
	}
};

fenwick_tree<int> bit(400200, 0);

void shuffle_go() {
	if(cur == N / 2) {
		return;
	}
	auto x = end(S); --x;
	while(x != begin(S) && cur - ((*x)[2] - (*x)[1] + 1) >= N / 2) {
		--R;
		cur -= ((*x)[2] - (*x)[1] + 1);
		for(int i = (*x)[2]; i >= (*x)[1]; --i) {
			subans.push_back(A[i]);
		}
		x = S.erase(x); --x;
	}
	if(cur == N / 2) {
		return;
	}
	array<int, 3> mv = *x;
	S.erase(x);
	--R;
	int trsh = cur - N / 2;
	--L;
	bit.add(L, mv[2] - trsh - mv[1] + 1);
	S.insert({mv[0], mv[1], mv[2] - trsh});
	int L = mv[2] - trsh + 1;
	int R = mv[2];
	for(int i = L; i <= R; ++i) {
		int j = min(R, nxtg[i] - 1);
		--L;
		bit.add(L, j - i + 1);
		S.insert({A[i], i, j});
		i = j;
	}
}

int32_t main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cin >> N >> Q;
	cur = N;
	A.resize(N); for(int& u : A) cin >> u;
	q.resize(Q); for(auto& u : q) { cin >> u.first >> u.second; u.first = min(u.first, N); }
	vector<int> ind(Q); iota(begin(ind), end(ind), 0);
	sort(begin(ind), end(ind), [&](const int& u, const int& v) { return q[u].first < q[v].first; });
	{
		nxtg.resize(N, N);
		vector<int> st;
		for(int i = N - 1; i >= 0; --i) {
			while(!st.empty() && A[st.back()] < A[i]) st.pop_back();
			if(!st.empty()) nxtg[i] = st.back();
			st.push_back(i);
		}
	}
	int K = 0;
	while(K < Q && q[ind[K]].first == 0) {
		cout << A[q[ind[K]].second - 1] << '\n';
		++K;
	}
	//first change manually
	for(int i = 0; i < N / 2; ++i) {
		int j = min(nxtg[i] - 1, N / 2 - 1);
		S.insert({A[i], i, j});
		i = j;
	}
	for(int i = N / 2; i < N; ++i) {
		int j = nxtg[i] - 1;
		S.insert({A[i], i, j});
		i = j;
	}
	L = R = 400200 - 3;
	++L;
	for(auto& u : S) {
		--L;
		bit.add(L, u[2] - u[1] + 1);
	}
	for(int i = 1; i <= N + 2; ++i) {
		while(K < Q && q[ind[K]].first == i) {
			int sd = q[ind[K]].second - 1;
			if(sd >= cur) {
				cout << subans[sd - cur] << '\n'; // whut
			} else {
				int tl = L, tr = R + 1;
				while(tl < tr) {
					int tm = (tl + tr) / 2;
					if(bit.query(L, tm) <= sd + 1) {
						tl = tm + 1;
					} else tr = tm;
				}
				--tl;
				tl -= L;
				auto x = S.find_by_order(tl);
				cout << A[(*x)[1] + (sd + 1) - bit.query(L, tl)] << '\n'; // sus
			}
			++K;
		}
		shuffle_go();
	}
	return 0;
}

Compilation message (stderr)

Main.cpp:3:9: error: 'tree' does not name a type; did you mean 'free'?
    3 | typedef tree<array<int, 3>, null_type, less<array<int, 3>>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
      |         ^~~~
      |         free
Main.cpp:9:1: error: 'ordered_set' does not name a type
    9 | ordered_set S;// original segment {L, R};
      | ^~~~~~~~~~~
Main.cpp: In function 'void shuffle_go()':
Main.cpp:47:15: error: 'S' was not declared in this scope
   47 |  auto x = end(S); --x;
      |               ^
Main.cpp:49:5: error: 'R' was not declared in this scope
   49 |   --R;
      |     ^
Main.cpp:61:4: error: 'R' was not declared in this scope
   61 |  --R;
      |    ^
Main.cpp:63:4: error: 'L' was not declared in this scope
   63 |  --L;
      |    ^
Main.cpp: In function 'int32_t main()':
Main.cpp:103:3: error: 'S' was not declared in this scope
  103 |   S.insert({A[i], i, j});
      |   ^
Main.cpp:108:3: error: 'S' was not declared in this scope
  108 |   S.insert({A[i], i, j});
      |   ^
Main.cpp:111:2: error: 'L' was not declared in this scope
  111 |  L = R = 400200 - 3;
      |  ^
Main.cpp:111:6: error: 'R' was not declared in this scope
  111 |  L = R = 400200 - 3;
      |      ^
Main.cpp:113:16: error: 'S' was not declared in this scope
  113 |  for(auto& u : S) {
      |                ^
Main.cpp:132:14: error: 'S' was not declared in this scope
  132 |     auto x = S.find_by_order(tl);
      |              ^