| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 681723 |
2023-01-13T22:53:22 Z |
stevancv |
Cake (CEOI14_cake) |
C++14 |
|
309 ms |
10264 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 + 1; 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 |
Incorrect |
1 ms |
324 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
218 ms |
3576 KB |
Output is correct |
| 2 |
Incorrect |
168 ms |
3628 KB |
Output isn't correct |
| 3 |
Correct |
192 ms |
3600 KB |
Output is correct |
| 4 |
Incorrect |
155 ms |
3496 KB |
Output isn't correct |
| 5 |
Correct |
248 ms |
3960 KB |
Output is correct |
| 6 |
Incorrect |
213 ms |
4000 KB |
Output isn't correct |
| 7 |
Correct |
210 ms |
3744 KB |
Output is correct |
| 8 |
Incorrect |
169 ms |
3952 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
51 ms |
3552 KB |
Output is correct |
| 2 |
Incorrect |
48 ms |
3912 KB |
Output isn't correct |
| 3 |
Incorrect |
39 ms |
3796 KB |
Output isn't correct |
| 4 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 5 |
Incorrect |
69 ms |
6472 KB |
Output isn't correct |
| 6 |
Correct |
72 ms |
6860 KB |
Output is correct |
| 7 |
Incorrect |
61 ms |
6584 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
20 ms |
972 KB |
Output isn't correct |
| 2 |
Correct |
21 ms |
1100 KB |
Output is correct |
| 3 |
Correct |
33 ms |
2240 KB |
Output is correct |
| 4 |
Incorrect |
41 ms |
2600 KB |
Output isn't correct |
| 5 |
Incorrect |
52 ms |
1392 KB |
Output isn't correct |
| 6 |
Correct |
57 ms |
3580 KB |
Output is correct |
| 7 |
Correct |
64 ms |
2036 KB |
Output is correct |
| 8 |
Incorrect |
122 ms |
4172 KB |
Output isn't correct |
| 9 |
Incorrect |
288 ms |
9276 KB |
Output isn't correct |
| 10 |
Incorrect |
184 ms |
2992 KB |
Output isn't correct |
| 11 |
Correct |
214 ms |
4352 KB |
Output is correct |
| 12 |
Correct |
309 ms |
8560 KB |
Output is correct |
| 13 |
Incorrect |
246 ms |
10264 KB |
Output isn't correct |
