Submission #58046

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
58046	2018-07-16T16:16:02 Z	fredbr	Cake (CEOI14_cake)	C++17	50 / 100	2000 ms	6596 KB

cake

#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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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