# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
438786 |
2021-06-28T15:22:58 Z |
BeanZ |
Cake (CEOI14_cake) |
C++14 |
|
569 ms |
18116 KB |
// I_Love_LPL 11m
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
const int N = 2e5 + 5;
long long mod = 998244353;
const int lim = 4e5 + 5;
const int lg = 22;
const int base = 311;
const long double eps = 1e-6;
ll a[N], pos[N], stR[N * 4], stL[N * 4];
ll n;
void updR(ll k, ll l, ll r, ll x, ll v){
if (x > r || x < l) return;
ll mid = (l + r) >> 1;
if (l == r){
stR[k] = v;
return;
}
updR(k << 1, l, mid, x, v);
updR(k << 1 | 1, mid + 1, r, x, v);
stR[k] = max(stR[k << 1], stR[k << 1 | 1]);
}
void updL(ll k, ll l, ll r, ll x, ll v){
if (x > r || x < l) return;
ll mid = (l + r) >> 1;
if (l == r){
stL[k] = v;
return;
}
updL(k << 1, l, mid, x, v);
updL(k << 1 | 1, mid + 1, r, x, v);
stL[k] = max(stL[k << 1], stL[k << 1 | 1]);
//cout << stL[k] << endl;
}
ll getR(ll k, ll l, ll r, ll x, ll y){
if (x > r || y < l) return 0;
if (x <= l && y >= r) return stR[k];
ll mid = (l + r) >> 1;
return max(getR(k << 1, l, mid, x, y), getR(k << 1 | 1, mid + 1, r, x, y));
}
ll getL(ll k, ll l, ll r, ll x, ll y){
if (x > r || y < l) return 0;
//cout << "FUCKed" << " " << stL[k] << endl;
if (x <= l && y >= r) return stL[k];
ll mid = (l + r) >> 1;
return max(getL(k << 1, l, mid, x, y), getL(k << 1 | 1, mid + 1, r, x, y));
}
ll getposR(ll k, ll l, ll r, ll v){
ll mid = (l + r) >> 1;
if (stR[k] < v) return n + 1;
if (l == r) return l;
if (stR[k << 1] >= v) return getposR(k << 1, l, mid, v);
else return getposR(k << 1 | 1, mid + 1, r, v);
}
ll getposL(ll k, ll l, ll r, ll v){
ll mid = (l + r) >> 1;
if (stL[k] < v) return 0;
if (l == r) return l;
if (stL[k << 1 | 1] >= v) return getposL(k << 1 | 1, mid + 1, r, v);
else return getposL(k << 1, l, mid, v);
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
if (fopen("tests.inp", "r")){
freopen("tests.inp", "r", stdin);
freopen("tests.out", "w", stdout);
}
ll d;
cin >> n >> d;
for (int i = 1; i <= n; i++){
cin >> a[i];
if (i < d) updL(1, 1, d, i, a[i]);
if (i > d) updR(1, d, n, i, a[i]);
pos[a[i]] = i;
}
ll q;
cin >> q;
ll tt = n;
while (q--){
char task;
cin >> task;
if (task == 'E'){
ll u, e;
cin >> u >> e;
for (int i = min(n, 10ll); i >= (e + 1); i--){
pos[n - i + 1] = pos[n - i + 2];
}
pos[n - e + 1] = u;
tt++;
for (int i = 1; i <= e; i++){
if (pos[n - i + 1] < d) updL(1, 1, d, pos[n - i + 1], tt - i + 1);
if (pos[n - i + 1] > d) updR(1, d, n, pos[n - i + 1], tt - i + 1);
}
}
else {
ll u;
cin >> u;
if (u == d) cout << 0 << endl;
else if (u < d){
ll mx = getL(1, 1, d, u, d);
ll id = getposR(1, d, n, mx);
cout << id - u - 1 << endl;
} else {
ll mx = getR(1, d, n, d, u);
ll id = getposL(1, 1, d, mx);
cout << u - id - 1 << endl;
}
}
}
}
/*
Ans:
Out:
*/
Compilation message
cake.cpp: In function 'int main()':
cake.cpp:68:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
68 | freopen("tests.inp", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
cake.cpp:69:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
69 | freopen("tests.out", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
332 KB |
Output is correct |
2 |
Incorrect |
1 ms |
316 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
281 ms |
4988 KB |
Output isn't correct |
2 |
Correct |
159 ms |
5080 KB |
Output is correct |
3 |
Correct |
217 ms |
5072 KB |
Output is correct |
4 |
Correct |
153 ms |
5188 KB |
Output is correct |
5 |
Incorrect |
319 ms |
6088 KB |
Output isn't correct |
6 |
Incorrect |
239 ms |
6212 KB |
Output isn't correct |
7 |
Correct |
242 ms |
6100 KB |
Output is correct |
8 |
Correct |
170 ms |
6344 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
85 ms |
5820 KB |
Output is correct |
2 |
Incorrect |
74 ms |
5768 KB |
Output isn't correct |
3 |
Correct |
71 ms |
5652 KB |
Output is correct |
4 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
5 |
Runtime error |
72 ms |
15040 KB |
Execution killed with signal 11 |
6 |
Runtime error |
75 ms |
14916 KB |
Execution killed with signal 11 |
7 |
Runtime error |
66 ms |
14884 KB |
Execution killed with signal 11 |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
37 ms |
868 KB |
Output isn't correct |
2 |
Correct |
26 ms |
972 KB |
Output is correct |
3 |
Correct |
65 ms |
3296 KB |
Output is correct |
4 |
Incorrect |
73 ms |
3268 KB |
Output isn't correct |
5 |
Incorrect |
89 ms |
1804 KB |
Output isn't correct |
6 |
Correct |
103 ms |
4932 KB |
Output is correct |
7 |
Correct |
97 ms |
2960 KB |
Output is correct |
8 |
Correct |
141 ms |
6484 KB |
Output is correct |
9 |
Runtime error |
72 ms |
15044 KB |
Execution killed with signal 11 |
10 |
Incorrect |
287 ms |
5144 KB |
Output isn't correct |
11 |
Incorrect |
389 ms |
6740 KB |
Output isn't correct |
12 |
Correct |
569 ms |
15044 KB |
Output is correct |
13 |
Runtime error |
77 ms |
18116 KB |
Execution killed with signal 11 |