oj.uz

답안 #58013

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
58013 2018-07-16T15:42:29 Z fredbr 케이크 (CEOI14_cake) C++17
0 / 100
 2000 ms 20064 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--;


	
	f();

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


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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1314 ms 1160 KB Output isn't correct
2 Correct 987 ms 1248 KB Output is correct
3 Incorrect 1268 ms 1248 KB Output isn't correct
4 Correct 1206 ms 1316 KB Output is correct
5 Execution timed out 2017 ms 2528 KB Time limit exceeded
6 Execution timed out 2041 ms 2708 KB Time limit exceeded
7 Execution timed out 2024 ms 2708 KB Time limit exceeded
8 Execution timed out 2068 ms 2708 KB Time limit exceeded

Subtask #3
0.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 268 ms 8700 KB Output isn't correct
2 Incorrect 147 ms 8812 KB Output isn't correct
3 Incorrect 121 ms 8812 KB Output isn't correct
4 Incorrect 2 ms 8812 KB Output isn't correct
5 Incorrect 489 ms 20056 KB Output isn't correct
6 Incorrect 500 ms 20064 KB Output isn't correct
7 Incorrect 348 ms 20064 KB Output isn't correct

Subtask #4
0.0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2009 ms 20064 KB Time limit exceeded
2 Execution timed out 2040 ms 20064 KB Time limit exceeded
3 Execution timed out 2041 ms 20064 KB Time limit exceeded
4 Execution timed out 2056 ms 20064 KB Time limit exceeded
5 Execution timed out 2065 ms 20064 KB Time limit exceeded
6 Execution timed out 2028 ms 20064 KB Time limit exceeded
7 Execution timed out 2066 ms 20064 KB Time limit exceeded
8 Execution timed out 2060 ms 20064 KB Time limit exceeded
9 Execution timed out 2051 ms 20064 KB Time limit exceeded
10 Execution timed out 2064 ms 20064 KB Time limit exceeded
11 Execution timed out 2070 ms 20064 KB Time limit exceeded
12 Execution timed out 2072 ms 20064 KB Time limit exceeded
13 Execution timed out 2057 ms 20064 KB Time limit exceeded