| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 226237 | 2020-04-23T07:28:01 Z | PeppaPig | 케이크 (CEOI14_cake) | C++14 | 597 ms | 15084 KB |
#include <bits/stdc++.h>
using namespace std;
const int N = 2.5e5;
struct SegmentTree {
int t[N << 1];
void update(int x, int k) {
for(t[x += N] = k; x != 1; x >>= 1)
t[x >> 1] = max(t[x], t[x ^ 1]);
}
int query(int l, int r) {
int ret = 0;
for(l += N, r += N + 1; l < r; l >>= 1, r >>= 1) {
if(l & 1) ret = max(ret, t[l++]);
if(r & 1) ret = max(ret, t[--r]);
}
return ret;
}
int pos(int x) {
int l = 0, r = N - 1;
while(l < r) {
int mid = (l + r + 1) >> 1;
if(query(1, mid) < x) l = mid;
else r = mid - 1;
}
return l;
}
} L, R;
int n, q, s, A[N];
vector<int> top10;
void add(int i, int x) {
A[i] = x;
if(i < s) L.update(s - i, x);
else R.update(i - s, x);
}
int main() {
scanf("%d %d", &n, &s);
for(int i = 1; i <= n; i++) {
scanf("%d", A + i);
add(i, A[i]);
top10.emplace_back(i);
}
sort(top10.begin(), top10.end(), [&](int a, int b) {
return A[a] > A[b];
});
while(top10.size() > 10) top10.pop_back();
L.update(s, 1e9), R.update(n - s + 1, 1e9);
scanf("%d", &q);
for(int i = 1, a, b, ptr = n; i <= q; i++) {
char c;
scanf(" %c %d", &c, &a);
if(c == 'E') {
scanf("%d", &b), --b;
auto it = find(top10.begin(), top10.end(), a);
if(it != top10.end()) top10.erase(it);
top10.insert(top10.begin() + b, a);
for(int j = b; ~j; j--) add(top10[j], ++ptr);
while(top10.size() > 10) top10.pop_back();
} else {
if(a == s) printf("0\n");
else if(a < s) printf("%d\n", (s - a) + R.pos(L.query(1, s - a)));
else printf("%d\n", (a - s) + L.pos(R.query(1, a - s)));
}
}
return 0;
}
Compilation message
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 5 ms | 384 KB | Output is correct |
| 2 | Correct | 5 ms | 384 KB | Output is correct |
| 3 | Correct | 5 ms | 384 KB | Output is correct |
| 4 | Correct | 8 ms | 512 KB | Output is correct |
| 5 | Correct | 15 ms | 768 KB | Output is correct |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 252 ms | 5132 KB | Output is correct |
| 2 | Correct | 198 ms | 5112 KB | Output is correct |
| 3 | Correct | 202 ms | 5112 KB | Output is correct |
| 4 | Correct | 172 ms | 5112 KB | Output is correct |
| 5 | Correct | 250 ms | 5624 KB | Output is correct |
| 6 | Correct | 237 ms | 5880 KB | Output is correct |
| 7 | Correct | 214 ms | 5880 KB | Output is correct |
| 8 | Correct | 181 ms | 6008 KB | Output is correct |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 140 ms | 4080 KB | Output is correct |
| 2 | Correct | 115 ms | 3952 KB | Output is correct |
| 3 | Correct | 112 ms | 3952 KB | Output is correct |
| 4 | Correct | 5 ms | 384 KB | Output is correct |
| 5 | Incorrect | 180 ms | 7632 KB | Output isn't correct |
| 6 | Incorrect | 185 ms | 7672 KB | Output isn't correct |
| 7 | Incorrect | 127 ms | 7656 KB | Output isn't correct |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 42 ms | 1016 KB | Output is correct |
| 2 | Correct | 40 ms | 1152 KB | Output is correct |
| 3 | Correct | 83 ms | 2548 KB | Output is correct |
| 4 | Correct | 95 ms | 2548 KB | Output is correct |
| 5 | Correct | 114 ms | 1912 KB | Output is correct |
| 6 | Correct | 131 ms | 3700 KB | Output is correct |
| 7 | Correct | 141 ms | 2680 KB | Output is correct |
| 8 | Correct | 119 ms | 4592 KB | Output is correct |
| 9 | Runtime error | 297 ms | 15084 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
| 10 | Correct | 364 ms | 5240 KB | Output is correct |
| 11 | Correct | 385 ms | 6520 KB | Output is correct |
| 12 | Correct | 597 ms | 11376 KB | Output is correct |
| 13 | Incorrect | 508 ms | 13036 KB | Output isn't correct |