oj.uz

Submission #58010

# Submission time Handle Problem Language Result Execution time Memory
58010 2018-07-16T15:39:56 Z fredbr Cake (CEOI14_cake) C++17
0 / 100
 2000 ms 20060 KB 
#include <bits/stdc++.h>

#define ff first
#define ss second

using namespace std;

typedef pair<int, int> ii;
typedef pair<int, ii> pii;

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";
}

set<pii> st;
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;

	// cout << "\n";
	// for (int i = 1; i <= n; i++)
	// 	cout << v[i] << " ";
	// cout << "\n\n";
}

int tmd[maxn];

inline void fix2()
{
	int at= n;
	for (pii x : st)
		v[x.ss.ss] = at--;

	st.clear();

	for (int i = 1; i <= n; i++) {

		st.insert({n-v[i]+1,{tmd[i], i}});
	}
	f();
	// cout << "\n";
	// for (int i = 1; i <= n; i++)
	// 	cout << v[i] << " ";
	// cout << "\n";
	
	for (int i = 1; i <= n; i++)
		v[i] = n-v[i]+1;
	
}


int main()
{
	ios_base::sync_with_stdio(false), cin.tie(0);

	cin >> n >> a;


	for (int i = 1; i <= n; i++)
		cin >> v[i], st.insert({n-v[i]+1,{0, i}}), v[i] = n-v[i]+1;

	int q;
	cin >> q;

	int tim = -1;
	while (q--) {

		char op;
		cin >> op;

		if (op == 'E') {

			if (n > 25000) {

				int pos, x;
				cin >> pos >> x;
				fix(pos, n-x+1, v[pos]);
				f();
			}
			else {

				int pos, x;
				cin >> pos >> x;

				st.erase(pii(v[pos], ii(tmd[pos], pos)));
				st.insert(pii(x, ii(tim, pos)));
				tmd[pos] = tim;
				v[pos] = x;

				// fix2();
			}
		}
		else {

			int pos;
			cin >> pos;

			if (n > 25000)
				cout <<d[pos] << "\n";
			else {

				fix2();
				// f();
				cout <<d[pos] << "\n";
			}
		}
		tim--;
	}
}

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Incorrect 3 ms 376 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 1022 ms 1324 KB Output isn't correct
2 Correct 1000 ms 1452 KB Output is correct
3 Incorrect 1455 ms 1452 KB Output isn't correct
4 Correct 1106 ms 1452 KB Output is correct
5 Execution timed out 2070 ms 2576 KB Time limit exceeded
6 Execution timed out 2070 ms 2652 KB Time limit exceeded
7 Execution timed out 2077 ms 2652 KB Time limit exceeded
8 Execution timed out 2082 ms 2652 KB Time limit exceeded

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 203 ms 8748 KB Output isn't correct
2 Incorrect 126 ms 8748 KB Output isn't correct
3 Incorrect 132 ms 8748 KB Output isn't correct
4 Incorrect 4 ms 8748 KB Output isn't correct
5 Incorrect 621 ms 20060 KB Output isn't correct
6 Incorrect 446 ms 20060 KB Output isn't correct
7 Incorrect 282 ms 20060 KB Output isn't correct

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2078 ms 20060 KB Time limit exceeded
2 Execution timed out 2050 ms 20060 KB Time limit exceeded
3 Execution timed out 2067 ms 20060 KB Time limit exceeded
4 Execution timed out 2044 ms 20060 KB Time limit exceeded
5 Execution timed out 2025 ms 20060 KB Time limit exceeded
6 Execution timed out 2050 ms 20060 KB Time limit exceeded
7 Execution timed out 2017 ms 20060 KB Time limit exceeded
8 Execution timed out 2019 ms 20060 KB Time limit exceeded
9 Execution timed out 2055 ms 20060 KB Time limit exceeded
10 Execution timed out 2051 ms 20060 KB Time limit exceeded
11 Execution timed out 2071 ms 20060 KB Time limit exceeded
12 Execution timed out 2080 ms 20060 KB Time limit exceeded
13 Execution timed out 2054 ms 20060 KB Time limit exceeded