oj.uz

Submission #791551

# Submission time Handle Problem Language Result Execution time Memory
791551 2023-07-24T07:20:29 Z khshg Abracadabra (CEOI22_abracadabra) C++14
0 / 100
 592 ms 38956 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});
	S.insert({A[mv[2] - trsh + 1], mv[2] - trsh + 1, mv[2]});
}

int32_t main() {
	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 + 1); }
	{
		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) {
		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 378 ms 11980 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 592 ms 20884 KB Output is correct
2 Correct 583 ms 38956 KB Output is correct
3 Correct 476 ms 31556 KB Output is correct
4 Correct 454 ms 27276 KB Output is correct
5 Correct 445 ms 28788 KB Output is correct
6 Correct 431 ms 26096 KB Output is correct
7 Incorrect 529 ms 31780 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

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

Subtask #4
0 / 25.0

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