oj.uz

답안 #791591

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
791591 2023-07-24T07:45:49 Z khshg Abracadabra (CEOI22_abracadabra) C++14
0 / 100
 3000 ms 25452 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() {
	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.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 369 ms 11976 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 559 ms 20868 KB Output is correct
2 Correct 551 ms 25452 KB Output is correct
3 Correct 445 ms 20976 KB Output is correct
4 Correct 430 ms 16636 KB Output is correct
5 Correct 481 ms 17832 KB Output is correct
6 Correct 409 ms 15548 KB Output is correct
7 Correct 554 ms 18828 KB Output is correct
8 Correct 511 ms 18436 KB Output is correct
9 Correct 431 ms 17064 KB Output is correct
10 Correct 470 ms 16912 KB Output is correct
11 Correct 388 ms 14540 KB Output is correct
12 Correct 387 ms 14528 KB Output is correct
13 Correct 456 ms 16844 KB Output is correct
14 Correct 404 ms 14800 KB Output is correct
15 Correct 488 ms 17348 KB Output is correct
16 Correct 44 ms 3372 KB Output is correct
17 Correct 416 ms 15624 KB Output is correct
18 Correct 359 ms 13608 KB Output is correct
19 Correct 118 ms 4556 KB Output is correct
20 Execution timed out 3080 ms 3932 KB Time limit exceeded
21 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 83 ms 3756 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 369 ms 11976 KB Output isn't correct
2 Halted 0 ms 0 KB -