oj.uz

Submission #58044

# Submission time Handle Problem Language Result Execution time Memory
58044 2018-07-16T16:05:36 Z fredbr Cake (CEOI14_cake) C++17
20 / 100
 2000 ms 6288 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);
	}
 
	// for (int i : ans)
	// 	cout << i << " ";
	// cout << "\n";
}
 
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 (!q.empty()) {

		if (mrk[q.front()]) {
			q.pop_front();
			continue;
		}
		v[q.front()] = num--;
		mrk[q.front()] = 1;
		qq.push_back(q.front());
		q.pop_front();
	}
	// for (int i = 1; i <= n; i++)
	// 	cout << v[i] << " ";
	// cout << "\n";
	f();
	q = qq;
	// cerr << q.size() << "\n";
}

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 {

				stack<int> qq;
				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";

			}
		}
	}
}

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1272 KB Output is correct
2 Incorrect 15 ms 1384 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 233 ms 1708 KB Output isn't correct
2 Correct 240 ms 1708 KB Output is correct
3 Correct 294 ms 1740 KB Output is correct
4 Correct 238 ms 1756 KB Output is correct
5 Incorrect 346 ms 2020 KB Output isn't correct
6 Correct 388 ms 2148 KB Output is correct
7 Correct 391 ms 2180 KB Output is correct
8 Correct 422 ms 2180 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 141 ms 3040 KB Output is correct
2 Correct 93 ms 3088 KB Output is correct
3 Correct 95 ms 3096 KB Output is correct
4 Correct 5 ms 3096 KB Output is correct
5 Correct 225 ms 6288 KB Output is correct
6 Correct 237 ms 6288 KB Output is correct
7 Correct 197 ms 6288 KB Output is correct

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2086 ms 6288 KB Time limit exceeded
2 Execution timed out 2072 ms 6288 KB Time limit exceeded
3 Execution timed out 2085 ms 6288 KB Time limit exceeded
4 Execution timed out 2064 ms 6288 KB Time limit exceeded
5 Execution timed out 2073 ms 6288 KB Time limit exceeded
6 Execution timed out 2051 ms 6288 KB Time limit exceeded
7 Execution timed out 2077 ms 6288 KB Time limit exceeded
8 Execution timed out 2059 ms 6288 KB Time limit exceeded
9 Execution timed out 2045 ms 6288 KB Time limit exceeded
10 Execution timed out 2068 ms 6288 KB Time limit exceeded
11 Execution timed out 2050 ms 6288 KB Time limit exceeded
12 Execution timed out 2062 ms 6288 KB Time limit exceeded
13 Execution timed out 2080 ms 6288 KB Time limit exceeded