Submission #791589

#	Time	Username	Problem	Language	Result	Execution time	Memory
791589		khshg	Homework (CEOI22_homework)	C++14	0 / 100	1 ms	340 KiB

Main

#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() {
	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; }
	{
		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
• Subtask 2: 0 / 13
• Subtask 3: 0 / 13
• Subtask 4: 0 / 30
• Subtask 5: 0 / 34