oj.uz

Submission #391940

# Submission time Handle Problem Language Result Execution time Memory
391940 2021-04-20T08:16:55 Z Kevin_Zhang_TW Cake (CEOI14_cake) C++17
35 / 100
 2000 ms 2924 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;
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;
//			DE(b);
//			debug(rk+1, rk+1+n);
			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:65:17: warning: unused variable 'mx' [-Wunused-variable]
   65 |    int res = 0, mx = 0;
      |                 ^~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 10 ms 332 KB Output is correct
5 Correct 126 ms 412 KB Output is correct

Subtask #2
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2071 ms 332 KB Time limit exceeded
2 Execution timed out 2084 ms 332 KB Time limit exceeded
3 Execution timed out 2084 ms 332 KB Time limit exceeded
4 Execution timed out 2072 ms 332 KB Time limit exceeded
5 Execution timed out 2075 ms 460 KB Time limit exceeded
6 Execution timed out 2066 ms 460 KB Time limit exceeded
7 Execution timed out 2077 ms 460 KB Time limit exceeded
8 Execution timed out 2088 ms 428 KB Time limit exceeded

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 1868 KB Output is correct
2 Correct 55 ms 1456 KB Output is correct
3 Correct 52 ms 1424 KB Output is correct
4 Correct 1 ms 216 KB Output is correct
5 Correct 91 ms 2804 KB Output is correct
6 Correct 121 ms 2924 KB Output is correct
7 Correct 95 ms 2628 KB Output is correct

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 189 ms 360 KB Output is correct
2 Correct 318 ms 696 KB Output is correct
3 Execution timed out 2085 ms 848 KB Time limit exceeded
4 Execution timed out 2081 ms 872 KB Time limit exceeded
5 Correct 421 ms 712 KB Output is correct
6 Execution timed out 2071 ms 964 KB Time limit exceeded
7 Execution timed out 2083 ms 992 KB Time limit exceeded
8 Execution timed out 2094 ms 1100 KB Time limit exceeded
9 Execution timed out 2072 ms 2372 KB Time limit exceeded
10 Correct 1303 ms 1536 KB Output is correct
11 Execution timed out 2085 ms 772 KB Time limit exceeded
12 Execution timed out 2073 ms 2000 KB Time limit exceeded
13 Execution timed out 2074 ms 2264 KB Time limit exceeded