oj.uz

Submission #791592

# Submission time Handle Problem Language Result Execution time Memory
791592 2023-07-24T07:47:15 Z khshg Abracadabra (CEOI22_abracadabra) C++14
0 / 100
 3000 ms 25592 KB 
#include<bits/stdc++.h>
using namespace std;

int N, Q;
int cur;
vector<int> A, nxtg, subans;
vector<pair<int, int>> q;
set<array<int, 3>> S;// original segment {L, R};

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) {
		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);
	int trsh = cur - N / 2;
	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);
		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.second = min(u.second, N + 2); }
	{
		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);
		}
	}
	if(q[0].first == 0) {
		for(auto& u : q) {
			cout << A[u.second - 1] << '\n';
		}
		return 0;
	}
	//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;
	}
	for(int i = 1; i < q[0].first; ++i) {
		shuffle_go();
	}
	vector<int> wtf;
	for(auto& u : S) {
//		cout << u[0] << '\n';
		for(int i = u[1]; i <= u[2]; ++i) {
			wtf.push_back(A[i]);
		}
	}
	reverse(begin(subans), end(subans));
	for(auto& u : subans) {
	//	cout << u << '\n';
		wtf.push_back(u);
	}
	for(auto& u : q) {
//		cout << u << ' ';
		cout << wtf[u.second - 1] << '\n';
	}
	return 0;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 156 ms 12036 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 212 ms 20820 KB Output is correct
2 Correct 237 ms 25592 KB Output is correct
3 Correct 183 ms 21004 KB Output is correct
4 Correct 182 ms 16556 KB Output is correct
5 Correct 172 ms 17856 KB Output is correct
6 Correct 155 ms 15652 KB Output is correct
7 Correct 198 ms 18864 KB Output is correct
8 Correct 192 ms 18444 KB Output is correct
9 Correct 170 ms 17040 KB Output is correct
10 Correct 176 ms 16960 KB Output is correct
11 Correct 157 ms 14576 KB Output is correct
12 Correct 152 ms 14408 KB Output is correct
13 Correct 179 ms 16884 KB Output is correct
14 Correct 150 ms 14860 KB Output is correct
15 Correct 185 ms 17284 KB Output is correct
16 Correct 16 ms 3424 KB Output is correct
17 Correct 164 ms 15636 KB Output is correct
18 Correct 140 ms 13632 KB Output is correct
19 Correct 46 ms 4660 KB Output is correct
20 Execution timed out 3072 ms 6032 KB Time limit exceeded
21 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 30 ms 3672 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 156 ms 12036 KB Output isn't correct
2 Halted 0 ms 0 KB -