oj.uz

Submission #391969

# Submission time Handle Problem Language Result Execution time Memory
391969 2021-04-20T09:07:31 Z Kevin_Zhang_TW Cake (CEOI14_cake) C++17
35 / 100
 2000 ms 4808 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
using namespace std;
using ll = long long;
#define pb emplace_back
#define AI(i) begin(i), end(i)
template<class T> bool chmin(T &a, T b) { return b < a && (a = b, true); }
template<class T> bool chmax(T &a, T b) { return a < b && (a = b, true); }
#ifdef KEV
#define DE(args...) kout("[ " + string(#args) + " ] = ", args)
void kout() { cerr << endl; }
template<class T, class ...U> void kout(T a, U ...b) { cerr << a << ' ', kout(b...); }
template<class T> void debug(T l, T r) { while (l != r) cerr << *l << " \n"[next(l)==r], ++l; }
#else
#define DE(...) 0
#define debug(...) 0
#endif
 
const int MAX_N = 250005, MAX_Q = 500005, inf = 1e9;

#define int int_fast32_t

int n, sep;
 
int val[MAX_N], rk[MAX_N];
 
int32_t main() {
	ios_base::sync_with_stdio(0), cin.tie(0);
	cin >> n >> sep;
	for (int i = 1;i <= n;++i)
		cin >> val[i];//, rk[i] = n - val[i] + 1;

	rk[sep] = 0;

	for (int i = sep+1;i <= n;++i)
		rk[i] = max(rk[i-1], val[i]);
	for (int i = sep-1;i >= 1;--i)
		rk[i] = max(rk[i+1], val[i]);

	vector<int> topten;
 
	int q;
	cin >> q;
	while (q--) {
		char op;
		cin >> op;
		if (op == 'E') {
			int ind, e;
			cin >> ind >> e;
			int nv = n - e + 1;
			for (int i = 1;i <= n;++i)
				val[i] -= val[i] > val[ind] && val[i] <= nv;
			val[ind] = nv;

			rk[sep] = 0;

			for (int i = sep+1;i <= n;++i)
				rk[i] = max(rk[i-1], val[i]);
			for (int i = sep-1;i >= 1;--i)
				rk[i] = max(rk[i+1], val[i]);

		}
		else {
			int b;
			cin >> b;
			int res = 0, mx = 0;
			if (b < sep) {
				res = upper_bound(rk+sep, rk+n+1, rk[b]) - rk - b - 1;
//				for (int i = b;i < sep;++i) chmax(mx, val[i]), ++res;
//				for (int i = sep+1;i <= n && val[i] < mx;++i) ++res;
			}
			if (b > sep) {
				res = rk + b - upper_bound(rk+1, rk+sep, rk[b], greater<>());
//				for (int i = sep+1;i <= b;++i) chmax(mx, val[i]), ++res;
//				for (int i = sep-1;i >= 1 && val[i] < mx;--i) ++res;
			}
			cout << res << '\n';
		}
	}
}

Compilation message

cake.cpp: In function 'int32_t main()':
cake.cpp:66:17: warning: unused variable 'mx' [-Wunused-variable]
   66 |    int res = 0, mx = 0;
      |                 ^~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 8 ms 448 KB Output is correct
5 Correct 122 ms 500 KB Output is correct

Subtask #2
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2082 ms 460 KB Time limit exceeded
2 Execution timed out 2088 ms 460 KB Time limit exceeded
3 Execution timed out 2092 ms 460 KB Time limit exceeded
4 Execution timed out 2082 ms 464 KB Time limit exceeded
5 Execution timed out 2086 ms 716 KB Time limit exceeded
6 Execution timed out 2091 ms 716 KB Time limit exceeded
7 Execution timed out 2090 ms 716 KB Time limit exceeded
8 Execution timed out 2075 ms 716 KB Time limit exceeded

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 2364 KB Output is correct
2 Correct 53 ms 2356 KB Output is correct
3 Correct 55 ms 2288 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 94 ms 4788 KB Output is correct
6 Correct 98 ms 4808 KB Output is correct
7 Correct 94 ms 4540 KB Output is correct

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 192 ms 500 KB Output is correct
2 Correct 309 ms 672 KB Output is correct
3 Execution timed out 2081 ms 1440 KB Time limit exceeded
4 Execution timed out 2035 ms 1376 KB Time limit exceeded
5 Correct 389 ms 628 KB Output is correct
6 Execution timed out 2086 ms 1516 KB Time limit exceeded
7 Execution timed out 2078 ms 1100 KB Time limit exceeded
8 Execution timed out 2082 ms 1868 KB Time limit exceeded
9 Execution timed out 2078 ms 4340 KB Time limit exceeded
10 Correct 1302 ms 1512 KB Output is correct
11 Execution timed out 2084 ms 940 KB Time limit exceeded
12 Execution timed out 2071 ms 3548 KB Time limit exceeded
13 Execution timed out 2092 ms 4288 KB Time limit exceeded