| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 536732 | 2022-03-14T00:40:14 Z | LucaDantas | Cake (CEOI14_cake) | C++17 | 2000 ms | 17812 KB |
#include <bits/stdc++.h>
using namespace std;
constexpr int maxn = 2e6+10, logn = 22;
int a[maxn];
struct BIT {
int bit[maxn];
void upd(int x, int v) {
for(; x < maxn; x += x&-x)
bit[x] += v;
}
int query(int x) {
int ans = 1;
for(; x > 0; x -= x&-x)
ans += bit[x];
return ans;
}
int bs(int x) {
// quero achar o x-esimo cara ativo
int pos = 0;
for(int l = logn-1; l >= 0; l--) {
if(pos + (1 << l) >= maxn) continue;
if(bit[pos + (1 << l)] < x)
x -= bit[pos + (1 << l)], pos += 1<<l;
}
return pos+1;
}
void fill() { for(int i = 1; i < maxn; i++) bit[i] = i&-i; } // todo mundo ativado com 1
} bit;
struct Query { int x, e; } qr[maxn];
vector<pair<int,int>> op;
int main() {
int n, st; scanf("%d %d", &n, &st);
for(int i = 1; i <= n; i++)
scanf("%d", a+i), op.push_back({i, n-a[i]+1});
int q; scanf("%d", &q);
for(int i = 1; i <= q; i++) {
char c; scanf(" %c", &c);
if(c == 'E') {
scanf("%d %d", &qr[i].x, &qr[i].e);
op.push_back({n+i, qr[i].e});
} else {
int x; scanf("%d", &x);
qr[i] = {x, -1};
}
}
reverse(op.begin(), op.end());
bit.fill();
int mx = 0;
for(auto [id, e] : op) {
int val = bit.bs(e);
bit.upd(val, -1); // removo esse cara
mx = max(mx, val);
if(id > n) qr[id-n].e = val;
else a[id] = val;
}
for(auto [id, e] : op)
if(id > n) qr[id-n].e = mx-qr[id-n].e+1;
else a[id] = mx-a[id]+1;
vector<int> l, r; // salvo os dois paretos
for(int i = st+1; i <= n; i++)
if(!r.size() || a[i] > a[r.back()])
r.push_back(i);
r.push_back(n+1); a[n+1] = 0x3f3f3f3f;
for(int i = st-1; i >= 1; i--)
if(!l.size() || a[i] > a[l.back()])
l.push_back(i);
l.push_back(0); a[0] = 0x3f3f3f3f;
for(int i = 1; i <= q; i++) {
if(qr[i].e == -1) {
// debug
{
l.clear(), r.clear();
for(int i = st+1; i <= n; i++)
if(!r.size() || a[i] > a[r.back()])
r.push_back(i);
r.push_back(n+1); a[n+1] = 0x3f3f3f3f;
for(int i = st-1; i >= 1; i--)
if(!l.size() || a[i] > a[l.back()])
l.push_back(i);
l.push_back(0); a[0] = 0x3f3f3f3f;
}
// query
int x = qr[i].x;
if(x == st) puts("0");
else if(x > st) {
auto mx = *(--upper_bound(r.begin(), r.end(), x));
int L = 0, R = (int)(l.size())-1, ans = 1;
while(L <= R) {
int M = (L+R) >> 1;
if(a[l[M]] > a[mx])
ans = l[M]+1, R = M-1;
else
L = M+1;
}
printf("%d\n", x - ans); // não inclui x
} else {
auto mx = *lower_bound(l.rbegin(), l.rend(), x);
int L = 0, R = (int)(r.size())-1, ans = n;
while(L <= R) {
int M = (L+R) >> 1;
if(a[r[M]] > a[mx])
ans = r[M]-1, R = M-1;
else
L = M+1;
}
printf("%d\n", ans - x); // não inclui x
}
} else {
// upd
auto [x, val] = qr[i];
a[x] = val;
/* if(x < st) swap(l, r);
vector<int> sv = {x};
while(r.size() && (x > st ? r.back() > x : r.back() < x))
sv.push_back(r.back()), r.pop_back();
for(int x : sv)
if(!r.size() || a[x] > a[r.back()])
r.push_back(x);
if(x < st) swap(l, r); */
}
}
}
Compilation message
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 5 ms | 8148 KB | Output is correct |
| 2 | Incorrect | 7 ms | 8148 KB | Output isn't correct |
| 3 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Incorrect | 230 ms | 16864 KB | Output isn't correct |
| 2 | Correct | 187 ms | 16812 KB | Output is correct |
| 3 | Correct | 190 ms | 16832 KB | Output is correct |
| 4 | Correct | 198 ms | 16764 KB | Output is correct |
| 5 | Incorrect | 207 ms | 17024 KB | Output isn't correct |
| 6 | Correct | 218 ms | 16944 KB | Output is correct |
| 7 | Correct | 208 ms | 17260 KB | Output is correct |
| 8 | Correct | 219 ms | 16928 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Execution timed out | 2056 ms | 10956 KB | Time limit exceeded |
| 2 | Execution timed out | 2079 ms | 10812 KB | Time limit exceeded |
| 3 | Execution timed out | 2078 ms | 10944 KB | Time limit exceeded |
| 4 | Incorrect | 6 ms | 8148 KB | Output isn't correct |
| 5 | Execution timed out | 2064 ms | 12612 KB | Time limit exceeded |
| 6 | Execution timed out | 2084 ms | 12576 KB | Time limit exceeded |
| 7 | Execution timed out | 2069 ms | 12696 KB | Time limit exceeded |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Incorrect | 234 ms | 9232 KB | Output isn't correct |
| 2 | Correct | 385 ms | 9256 KB | Output is correct |
| 3 | Execution timed out | 2084 ms | 10468 KB | Time limit exceeded |
| 4 | Execution timed out | 2062 ms | 10512 KB | Time limit exceeded |
| 5 | Incorrect | 478 ms | 10944 KB | Output isn't correct |
| 6 | Execution timed out | 2055 ms | 11652 KB | Time limit exceeded |
| 7 | Execution timed out | 2058 ms | 11696 KB | Time limit exceeded |
| 8 | Correct | 681 ms | 13268 KB | Output is correct |
| 9 | Execution timed out | 2033 ms | 17812 KB | Time limit exceeded |
| 10 | Incorrect | 1555 ms | 16064 KB | Output isn't correct |
| 11 | Execution timed out | 2070 ms | 15384 KB | Time limit exceeded |
| 12 | Execution timed out | 2072 ms | 17128 KB | Time limit exceeded |
| 13 | Execution timed out | 2067 ms | 17676 KB | Time limit exceeded |