| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 71459 | 2018-08-24T18:23:17 Z | kingpig9 | Cake (CEOI14_cake) | C++11 | 211 ms | 12632 KB |
#include <bits/stdc++.h>
using namespace std;
#define debug(...) fprintf(stderr, __VA_ARGS__)
//#define debug(...)
#define all(v) (v).begin(), (v).end()
#define fi first
#define se second
#define fillchar(a, s) memset((a), (s), sizeof(a))
const int MAXN = 1 << 18;
void setmax (int &a, int b) {
if (a < b) {
a = b;
}
}
struct fenwick {
int bit[MAXN];
int query (int x) {
int res = 0;
for (; x; x &= x - 1) {
setmax(res, bit[x]);
}
return res;
}
void update (int x, int v) {
for (; x < MAXN; x += (x & -x)) {
setmax(bit[x], v);
}
}
int find (int q) {
//last query that's < q
int pos = 0;
for (int i = 17; i >= 0; i--) {
int npos = pos + (1 << i);
if (bit[npos] < q) {
pos = npos;
}
}
return pos;
}
};
int N, S;
int A[MAXN];
vector<int> top10;
fenwick lfen, rfen;
int curv;
bool cmp10 (int x, int y) {
return A[x] > A[y];
}
void adjust_top10() {
sort(all(top10), cmp10);
top10.resize(min(N, 10));
}
void upda (int x, int v) {
A[x] = v;
if (x < S) {
lfen.update(S - x, v);
} else if (x > S) {
rfen.update(x - S, v);
}
}
int main() {
scanf("%d %d", &N, &S);
for (int i = 1; i <= N; i++) {
scanf("%d", &A[i]);
upda(i, A[i]);
top10.push_back(i);
}
lfen.update(S, 2e9);
rfen.update(N - S + 1, 2e9);
adjust_top10();
assert(is_sorted(all(top10), cmp10));
curv = N;
int nq, x, e;
char qtype;
for (scanf("%d", &nq); nq--; ) {
scanf(" %c", &qtype);
if (qtype == 'E') {
scanf("%d %d", &x, &e);
e--;
auto it = find(all(top10), x);
if (it != top10.begin()) {
top10.erase(it);
}
top10.insert(top10.begin() + e, x);
for (int i = e; i >= 0; i--) {
upda(top10[i], ++curv);
}
top10.resize(min(N, 10));
//debug("assert\n");
assert(is_sorted(all(top10), cmp10));
//adjust_top10();
} else {
scanf("%d", &x);
if (x == S) {
puts("0");
continue;
}
int cntx = abs(x - S);
int mx, cnto;
if (x < S) {
mx = lfen.query(cntx);
cnto = rfen.find(mx + 1);
} else {
mx = rfen.query(cntx);
cnto = lfen.find(mx + 1);
}
printf("%d\n", cntx + cnto);
}
}
}
Compilation message
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 2 ms | 376 KB | Output is correct |
| 2 | Runtime error | 3 ms | 744 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
| 3 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Runtime error | 8 ms | 1328 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 | Runtime error | 8 ms | 1692 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
| 3 | Runtime error | 8 ms | 1924 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
| 4 | Correct | 188 ms | 6296 KB | Output is correct |
| 5 | Runtime error | 11 ms | 6572 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
| 6 | Runtime error | 14 ms | 6976 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
| 7 | Runtime error | 12 ms | 6976 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
| 8 | Correct | 211 ms | 6976 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Runtime error | 39 ms | 8744 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 | Runtime error | 41 ms | 8744 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
| 3 | Runtime error | 39 ms | 8748 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
| 4 | Correct | 3 ms | 8748 KB | Output is correct |
| 5 | Runtime error | 101 ms | 12120 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
| 6 | Runtime error | 107 ms | 12324 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
| 7 | Correct | 148 ms | 12632 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Runtime error | 4 ms | 12632 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 | Runtime error | 7 ms | 12632 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
| 3 | Runtime error | 21 ms | 12632 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
| 4 | Runtime error | 25 ms | 12632 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
| 5 | Runtime error | 4 ms | 12632 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
| 6 | Runtime error | 26 ms | 12632 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
| 7 | Runtime error | 7 ms | 12632 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
| 8 | Runtime error | 40 ms | 12632 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
| 9 | Runtime error | 106 ms | 12632 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
| 10 | Runtime error | 5 ms | 12632 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
| 11 | Runtime error | 13 ms | 12632 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
| 12 | Runtime error | 105 ms | 12632 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
| 13 | Runtime error | 116 ms | 12632 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |