| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 536723 | 2022-03-14T00:32:18 Z | LucaDantas | 케이크 (CEOI14_cake) | C++17 | 2000 ms | 17156 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) {
// 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); */
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;
}
}
}
Compilation message
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 5 ms | 8148 KB | Output is correct |
| 2 | Incorrect | 5 ms | 8148 KB | Output isn't correct |
| 3 | Halted | 0 ms | 0 KB | - |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Execution timed out | 2095 ms | 16164 KB | Time limit exceeded |
| 2 | Execution timed out | 2081 ms | 16188 KB | Time limit exceeded |
| 3 | Execution timed out | 2096 ms | 16208 KB | Time limit exceeded |
| 4 | Execution timed out | 2089 ms | 16124 KB | Time limit exceeded |
| 5 | Execution timed out | 2088 ms | 16304 KB | Time limit exceeded |
| 6 | Execution timed out | 2099 ms | 16376 KB | Time limit exceeded |
| 7 | Execution timed out | 2096 ms | 16376 KB | Time limit exceeded |
| 8 | Execution timed out | 2076 ms | 16444 KB | Time limit exceeded |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 109 ms | 10848 KB | Output is correct |
| 2 | Correct | 79 ms | 10796 KB | Output is correct |
| 3 | Incorrect | 78 ms | 10656 KB | Output isn't correct |
| 4 | Incorrect | 5 ms | 8148 KB | Output isn't correct |
| 5 | Correct | 177 ms | 12680 KB | Output is correct |
| 6 | Incorrect | 198 ms | 12636 KB | Output isn't correct |
| 7 | Correct | 149 ms | 12432 KB | Output is correct |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Incorrect | 272 ms | 9000 KB | Output isn't correct |
| 2 | Correct | 408 ms | 9016 KB | Output is correct |
| 3 | Execution timed out | 2078 ms | 9996 KB | Time limit exceeded |
| 4 | Execution timed out | 2089 ms | 9976 KB | Time limit exceeded |
| 5 | Incorrect | 496 ms | 10392 KB | Output isn't correct |
| 6 | Execution timed out | 2079 ms | 11036 KB | Time limit exceeded |
| 7 | Execution timed out | 2099 ms | 11104 KB | Time limit exceeded |
| 8 | Execution timed out | 2093 ms | 12608 KB | Time limit exceeded |
| 9 | Execution timed out | 2069 ms | 17148 KB | Time limit exceeded |
| 10 | Incorrect | 1707 ms | 15336 KB | Output isn't correct |
| 11 | Execution timed out | 2065 ms | 14560 KB | Time limit exceeded |
| 12 | Execution timed out | 2061 ms | 16568 KB | Time limit exceeded |
| 13 | Execution timed out | 2083 ms | 17156 KB | Time limit exceeded |