oj.uz

답안 #58046

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
58046 2018-07-16T16:16:02 Z fredbr 케이크 (CEOI14_cake) C++17
50 / 100
 2000 ms 6596 KB 
#include <bits/stdc++.h>
 
using namespace std;
 
const int maxn = 250001;
 
int n, a;
int v[maxn];
int d[maxn];
 
vector<int> ans;
 
inline void f()
{
	ans = {a};
 
	int l = a-1, r = a+1;
	d[a] = 0;
 
	for (int i = 1; i < n; i++) {
 
		if (l > 0 and r <= n) {
			if (v[l] < v[r])
				d[l] = i, l--, ans.push_back(l+1);
			else 
				d[r] = i, r++, ans.push_back(r-1);
		}
		else if (l == 0)
			d[r] = i, r++, ans.push_back(r-1);
		else d[l] = i, l--, ans.push_back(l+1);
	}
}
 
inline void fix(int pos, int x, int old)
{
	for (int i = 1; i <= n; i++) {
 
		if (i == pos) continue;
		if (v[i] <= x and v[i] > old)
			v[i]--;
	}
	v[pos] = x;
}

int inv[maxn];
int mrk[maxn];
deque<int> q;

void fix2()
{
	memset(mrk, 0, sizeof(mrk));

	deque<int> qq;
	int num = n;
	while (num > 0) {

		if (mrk[q.front()]) {
			q.pop_front();
			continue;
		}
		v[q.front()] = num--;
		mrk[q.front()] = 1;
		qq.push_back(q.front());
		q.pop_front();
	}
	f();
	q = qq;
}

int main()
{
	ios_base::sync_with_stdio(false), cin.tie(0);
 
	cin >> n >> a;
 
	for (int i = 1; i <= n; i++)
		cin >> v[i], inv[v[i]] = i;

	if (n > 25000) f();

	for (int i = 1; i <= n; i++)
		q.push_front(inv[i]);
 
	int Q;
	cin >> Q;
 
	while (Q--) {
 
		char op;
		cin >> op;
 
		if (op == 'E') {
 
			int pos, x;
			cin >> pos >> x;

			if (n > 25000)
				fix(pos, n-x+1, v[pos]), f();
			else {

				set<int> st;
				stack<int> qq;

				while (st.size() <= min(n,10)) {

					if (st.count(q.front())) q.pop_front();
					else {
						qq.push(q.front());
						st.insert(q.front());
						q.pop_front();
					}
				}
				while (!qq.empty())
					q.push_front(qq.top()), qq.pop();

				while (--x) {
					qq.push(q.front()), q.pop_front();
				}
				q.push_front(pos);
				while (!qq.empty())
					q.push_front(qq.top()), qq.pop();
			}
		}
		else {
 
			int pos;
			cin >> pos;
 	
 			if (n > 25000)
				cout <<d[pos] << "\n";
			else {

				fix2();
				cout << d[pos] << "\n";

			}
		}
	}
}

Compilation message

cake.cpp: In function 'int main()':
cake.cpp:104:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while (st.size() <= min(n,10)) {
            ~~~~~~~~~~^~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 1272 KB Output is correct
2 Correct 17 ms 1384 KB Output is correct
3 Correct 19 ms 1460 KB Output is correct
4 Correct 170 ms 1516 KB Output is correct
5 Correct 1157 ms 2124 KB Output is correct

Subtask #2
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 714 ms 2124 KB Output is correct
2 Correct 694 ms 2124 KB Output is correct
3 Correct 813 ms 2152 KB Output is correct
4 Correct 713 ms 2152 KB Output is correct
5 Correct 936 ms 2472 KB Output is correct
6 Correct 860 ms 2472 KB Output is correct
7 Correct 882 ms 2472 KB Output is correct
8 Correct 771 ms 2472 KB Output is correct

Subtask #3
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 115 ms 3364 KB Output is correct
2 Correct 80 ms 3364 KB Output is correct
3 Correct 98 ms 3364 KB Output is correct
4 Correct 6 ms 3364 KB Output is correct
5 Correct 281 ms 6596 KB Output is correct
6 Correct 226 ms 6596 KB Output is correct
7 Correct 199 ms 6596 KB Output is correct

Subtask #4
0.0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2069 ms 6596 KB Time limit exceeded
2 Execution timed out 2069 ms 6596 KB Time limit exceeded
3 Execution timed out 2054 ms 6596 KB Time limit exceeded
4 Execution timed out 2053 ms 6596 KB Time limit exceeded
5 Execution timed out 2079 ms 6596 KB Time limit exceeded
6 Execution timed out 2060 ms 6596 KB Time limit exceeded
7 Execution timed out 2049 ms 6596 KB Time limit exceeded
8 Execution timed out 2063 ms 6596 KB Time limit exceeded
9 Execution timed out 2067 ms 6596 KB Time limit exceeded
10 Execution timed out 2060 ms 6596 KB Time limit exceeded
11 Execution timed out 2067 ms 6596 KB Time limit exceeded
12 Execution timed out 2056 ms 6596 KB Time limit exceeded
13 Execution timed out 2074 ms 6596 KB Time limit exceeded