| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 71461 | 2018-08-24T18:24:26 Z | kingpig9 | Cake (CEOI14_cake) | C++11 | 224 ms | 7500 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();
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");
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 | 868 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 | 6 ms | 1272 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 | Runtime error | 6 ms | 1412 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
| 3 | Runtime error | 8 ms | 1448 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
| 4 | Correct | 215 ms | 1448 KB | Output is correct |
| 5 | Runtime error | 15 ms | 1780 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
| 6 | Runtime error | 13 ms | 1832 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
| 7 | Runtime error | 16 ms | 1912 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
| 8 | Correct | 224 ms | 1912 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Runtime error | 47 ms | 3636 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 | Runtime error | 46 ms | 3636 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
| 3 | Runtime error | 48 ms | 3652 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
| 4 | Correct | 2 ms | 3652 KB | Output is correct |
| 5 | Runtime error | 120 ms | 7120 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
| 6 | Runtime error | 98 ms | 7200 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
| 7 | Correct | 156 ms | 7500 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Runtime error | 4 ms | 7500 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 | Runtime error | 6 ms | 7500 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
| 3 | Runtime error | 19 ms | 7500 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
| 4 | Runtime error | 21 ms | 7500 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
| 5 | Runtime error | 4 ms | 7500 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
| 6 | Runtime error | 30 ms | 7500 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
| 7 | Runtime error | 7 ms | 7500 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
| 8 | Runtime error | 39 ms | 7500 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
| 9 | Runtime error | 163 ms | 7500 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
| 10 | Runtime error | 4 ms | 7500 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
| 11 | Runtime error | 10 ms | 7500 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
| 12 | Runtime error | 87 ms | 7500 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
| 13 | Runtime error | 99 ms | 7500 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |