| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 681670 |
2023-01-13T16:01:05 Z |
stevancv |
Cake (CEOI14_cake) |
C++14 |
|
2000 ms |
8560 KB |
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define sp ' '
#define en '\n'
#define smin(a, b) a = min(a, b)
#define smax(a, b) a = max(a, b)
using namespace std;
const int N = 2e5 + 5e4 + 2;
const int M = 5e5 + 2;
const ll linf = 9e18;
int a[N], inv[N + M];
struct Segtree {
int st[4 * N];
void Set(int node, int l, int r, int x, int y) {
smax(st[node], y);
if (l == r) return;
int mid = l + r >> 1;
if (x <= mid) Set(2 * node, l, mid, x, y);
else Set(2 * node + 1, mid + 1, r, x, y);
}
int Get(int node, int l, int r, int ql, int qr) {
if (r < ql || qr < l) return 0;
if (ql <= l && r <= qr) return st[node];
int mid = l + r >> 1;
return max(Get(2 * node, l, mid, ql, qr), Get(2 * node + 1, mid + 1, r, ql, qr));
}
int Find(int node, int l, int r, int val) {
if (l == r) return l;
int mid = l + r >> 1;
if (st[2 * node] > val) return Find(2 * node, l, mid, val);
return Find(2 * node + 1, mid + 1, r, val);
}
}stx, sty;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n, pos;
cin >> n >> pos;
for (int i = 1; i <= n; i++) {
cin >> a[i];
inv[a[i]] = i;
}
int kk = min(n, 10);
vector<int> x, y;
for (int i = 1; i < pos; i++) x.push_back(i);
reverse(x.begin(), x.end());
for (int i = pos + 1; i <= n; i++) y.push_back(i);
int X = x.size(); int Y = y.size();
for (int i = 0; i < X; i++) stx.Set(1, 0, X - 1, i, a[x[i]]);
for (int i = 0; i < Y; i++) sty.Set(1, 0, Y - 1, i, a[y[i]]);
int val = n;
int q; cin >> q;
while (q--) {
char ch; cin >> ch;
if (ch == 'E') {
int p, e;
cin >> p >> e;
val += 1;
for (int i = 1; i < e; i++) {
int pp = inv[val - i];
a[pp] = val - i + 1;
inv[val - i + 1] = pp;
if (pp < pos) stx.Set(1, 0, X - 1, pos - pp - 1, a[pp]);
else if (pp > pos) sty.Set(1, 0, Y - 1, pp - pos - 1, a[pp]);
}
int wh = a[p];
a[p] = val - e + 1;
inv[val - e + 1] = p;
if (p < pos) stx.Set(1, 0, X - 1, pos - p - 1, a[p]);
else if (p > pos) sty.Set(1, 0, Y - 1, p - pos - 1, a[p]);
if (wh < val - kk) continue;
for (int i = val - wh; i <= val - kk; i++) {
int pp = inv[val - i];
a[pp] = val - i + 1;
inv[val - i + 1] = pp;
if (pp < pos) stx.Set(1, 0, X - 1, pos - pp - 1, a[pp]);
else if (pp > pos) sty.Set(1, 0, Y - 1, pp - pos - 1, a[pp]);
}
continue;
}
int p; cin >> p;
if (p == pos) {
cout << 0 << en;
continue;
}
if (p < pos) {
int o = stx.Get(1, 0, X - 1, 0, pos - p - 1);
int oo = sty.Find(1, 0, Y - 1, o);
if (sty.st[1] < o) oo = Y;
cout << pos - p + oo << en;
}
else {
int o = sty.Get(1, 0, Y - 1, 0, p - pos - 1);
int oo = stx.Find(1, 0, X - 1, o);
if (sty.st[1] < o) oo = X;
cout << p - pos + oo << en;
}
}
return 0;
}
Compilation message
cake.cpp: In member function 'void Segtree::Set(int, int, int, int, int)':
cake.cpp:18:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
18 | int mid = l + r >> 1;
| ~~^~~
cake.cpp: In member function 'int Segtree::Get(int, int, int, int, int)':
cake.cpp:25:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
25 | int mid = l + r >> 1;
| ~~^~~
cake.cpp: In member function 'int Segtree::Find(int, int, int, int)':
cake.cpp:30:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
30 | int mid = l + r >> 1;
| ~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2067 ms |
856 KB |
Time limit exceeded |
| 2 |
Execution timed out |
2078 ms |
928 KB |
Time limit exceeded |
| 3 |
Execution timed out |
2087 ms |
972 KB |
Time limit exceeded |
| 4 |
Execution timed out |
2093 ms |
856 KB |
Time limit exceeded |
| 5 |
Execution timed out |
2083 ms |
1380 KB |
Time limit exceeded |
| 6 |
Execution timed out |
2082 ms |
1112 KB |
Time limit exceeded |
| 7 |
Execution timed out |
2077 ms |
1204 KB |
Time limit exceeded |
| 8 |
Execution timed out |
2079 ms |
1032 KB |
Time limit exceeded |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
52 ms |
3784 KB |
Output is correct |
| 2 |
Incorrect |
124 ms |
3596 KB |
Output isn't correct |
| 3 |
Incorrect |
287 ms |
3680 KB |
Output isn't correct |
| 4 |
Incorrect |
0 ms |
324 KB |
Output isn't correct |
| 5 |
Incorrect |
78 ms |
6616 KB |
Output isn't correct |
| 6 |
Incorrect |
471 ms |
6600 KB |
Output isn't correct |
| 7 |
Incorrect |
1132 ms |
6476 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
81 ms |
972 KB |
Output isn't correct |
| 2 |
Correct |
68 ms |
1056 KB |
Output is correct |
| 3 |
Correct |
60 ms |
2356 KB |
Output is correct |
| 4 |
Incorrect |
87 ms |
2416 KB |
Output isn't correct |
| 5 |
Incorrect |
789 ms |
1536 KB |
Output isn't correct |
| 6 |
Correct |
171 ms |
3144 KB |
Output is correct |
| 7 |
Correct |
409 ms |
2056 KB |
Output is correct |
| 8 |
Execution timed out |
2061 ms |
2944 KB |
Time limit exceeded |
| 9 |
Incorrect |
767 ms |
8560 KB |
Output isn't correct |
| 10 |
Execution timed out |
2033 ms |
1812 KB |
Time limit exceeded |
| 11 |
Incorrect |
1377 ms |
3808 KB |
Output isn't correct |
| 12 |
Incorrect |
643 ms |
8008 KB |
Output isn't correct |
| 13 |
Execution timed out |
2081 ms |
6976 KB |
Time limit exceeded |
