| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 681718 |
2023-01-13T22:20:02 Z |
stevancv |
Cake (CEOI14_cake) |
C++14 |
|
164 ms |
12928 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;
assert(e == 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 <= 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 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
980 KB |
Execution killed with signal 6 |
| 2 |
Runtime error |
2 ms |
1108 KB |
Execution killed with signal 6 |
| 3 |
Runtime error |
2 ms |
1108 KB |
Execution killed with signal 6 |
| 4 |
Incorrect |
152 ms |
2600 KB |
Output isn't correct |
| 5 |
Runtime error |
5 ms |
1748 KB |
Execution killed with signal 6 |
| 6 |
Runtime error |
4 ms |
1748 KB |
Execution killed with signal 6 |
| 7 |
Runtime error |
4 ms |
1748 KB |
Execution killed with signal 6 |
| 8 |
Incorrect |
164 ms |
2836 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
16 ms |
5204 KB |
Execution killed with signal 6 |
| 2 |
Runtime error |
15 ms |
5204 KB |
Execution killed with signal 6 |
| 3 |
Runtime error |
15 ms |
5204 KB |
Execution killed with signal 6 |
| 4 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 6 |
| 5 |
Runtime error |
39 ms |
10888 KB |
Execution killed with signal 6 |
| 6 |
Runtime error |
39 ms |
11008 KB |
Execution killed with signal 6 |
| 7 |
Runtime error |
37 ms |
10832 KB |
Execution killed with signal 6 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
708 KB |
Execution killed with signal 6 |
| 2 |
Runtime error |
1 ms |
724 KB |
Execution killed with signal 6 |
| 3 |
Runtime error |
8 ms |
2984 KB |
Execution killed with signal 6 |
| 4 |
Runtime error |
8 ms |
3028 KB |
Execution killed with signal 6 |
| 5 |
Runtime error |
1 ms |
596 KB |
Execution killed with signal 6 |
| 6 |
Runtime error |
10 ms |
3920 KB |
Execution killed with signal 6 |
| 7 |
Runtime error |
2 ms |
1108 KB |
Execution killed with signal 6 |
| 8 |
Runtime error |
15 ms |
5300 KB |
Execution killed with signal 6 |
| 9 |
Runtime error |
38 ms |
10812 KB |
Execution killed with signal 6 |
| 10 |
Runtime error |
1 ms |
596 KB |
Execution killed with signal 6 |
| 11 |
Runtime error |
5 ms |
1620 KB |
Execution killed with signal 6 |
| 12 |
Runtime error |
31 ms |
9656 KB |
Execution killed with signal 6 |
| 13 |
Runtime error |
40 ms |
12928 KB |
Execution killed with signal 6 |
