# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
555713 |
2022-05-01T11:42:52 Z |
alextodoran |
Cake (CEOI14_cake) |
C++17 |
|
65 ms |
2584 KB |
/**
____ ____ ____ ____ ____
||a |||t |||o |||d |||o ||
||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|
**/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N_MAX = 10000;
const int Q_MAX = 10000;
const int D_MAX = N_MAX + Q_MAX * 10;
int N, start;
int d[N_MAX + 2];
int Q;
set <int> newmax;
set <int> :: iterator getMax (int i) {
return (i < start ? newmax.lower_bound(i) : prev(newmax.upper_bound(i)));
}
int D;
map <int, int> where;
int Fen[D_MAX + 2];
void update (int pos, int val) {
for (int i = pos; i <= D_MAX; i += i & -i) {
Fen[i] += val;
}
}
int query (int pos) {
int val = 0;
for (int i = pos; i >= 1; i -= i & -i){
val += Fen[i];
}
return val;
}
void makeMax (int i) {
D++;
where.erase(d[i]);
if (i < start) {
set <int> :: iterator it = prev(newmax.upper_bound(i));
if (*it < i) {
set <int> :: iterator neit = next(it);
update(d[*neit], -(i - *it));
}
while (*it > 0) {
set <int> :: iterator prit = prev(it);
update(d[*it], -(*it - *prit));
newmax.erase(it); it = prit;
}
newmax.insert(i);
update(D, +(i - 0));
} else if (i > start) {
set <int> :: iterator it = newmax.lower_bound(i);
if (i < *it) {
set <int> :: iterator prit = prev(it);
update(d[*prit], -(*it - i));
}
while (*it < (N + 1)) {
set <int> :: iterator neit = next(it);
update(d[*it], -(*neit - *it));
newmax.erase(it); it = neit;
}
newmax.insert(i);
update(D, +((N + 1) - i));
}
d[i] = D;
where[D] = i;
}
int main () {
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> N >> start;
for (int i = 1; i <= N; i++) {
cin >> d[i];
}
D = N;
for (int i = start - 1, curr = 0; i >= 1; i--) {
if (d[i] > curr) {
newmax.insert(i);
curr = d[i];
}
}
newmax.insert(0);
for (int i = start + 1, curr = 0; i <= N; i++) {
if (d[i] > curr) {
newmax.insert(i);
curr = d[i];
}
}
newmax.insert(N + 1);
for (int i = 1; i <= N; i++) {
if (i != start) {
update(d[*getMax(i)], +1);
}
where[d[i]] = i;
}
cin >> Q;
while (Q--) {
char type; cin >> type;
if (type == 'F') {
int i; cin >> i;
if (i == start) {
cout << 0 << "\n";
} else {
set <int> :: iterator it = getMax(i);
cout << 1 + query(d[*it] - 1) + abs(*it - i) << "\n";
}
} else {
int i, e; cin >> i >> e; e--;
makeMax(i);
if (e > 0) {
map <int, int> :: iterator it = prev(where.end()), prit = prev(it);
for (int k = 1; k <= e; k++) {
it = prit;
if (k < e) {
prit = prev(it);
}
makeMax(it->second);
}
}
}
}
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
48 ms |
2220 KB |
Execution killed with signal 11 |
2 |
Runtime error |
43 ms |
2228 KB |
Execution killed with signal 11 |
3 |
Runtime error |
42 ms |
2312 KB |
Execution killed with signal 11 |
4 |
Runtime error |
46 ms |
2172 KB |
Execution killed with signal 11 |
5 |
Runtime error |
2 ms |
512 KB |
Execution killed with signal 11 |
6 |
Runtime error |
2 ms |
468 KB |
Execution killed with signal 11 |
7 |
Runtime error |
2 ms |
468 KB |
Execution killed with signal 11 |
8 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 11 |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 11 |
2 |
Runtime error |
2 ms |
468 KB |
Execution killed with signal 11 |
3 |
Runtime error |
2 ms |
468 KB |
Execution killed with signal 11 |
4 |
Correct |
0 ms |
340 KB |
Output is correct |
5 |
Runtime error |
2 ms |
468 KB |
Execution killed with signal 11 |
6 |
Runtime error |
2 ms |
468 KB |
Execution killed with signal 11 |
7 |
Runtime error |
2 ms |
468 KB |
Execution killed with signal 11 |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
58 ms |
1640 KB |
Execution killed with signal 11 |
2 |
Incorrect |
35 ms |
908 KB |
Output isn't correct |
3 |
Runtime error |
2 ms |
468 KB |
Execution killed with signal 11 |
4 |
Runtime error |
2 ms |
468 KB |
Execution killed with signal 11 |
5 |
Runtime error |
47 ms |
1632 KB |
Execution killed with signal 11 |
6 |
Runtime error |
2 ms |
468 KB |
Execution killed with signal 11 |
7 |
Runtime error |
65 ms |
2584 KB |
Execution killed with signal 11 |
8 |
Runtime error |
2 ms |
468 KB |
Execution killed with signal 11 |
9 |
Runtime error |
2 ms |
468 KB |
Execution killed with signal 11 |
10 |
Runtime error |
46 ms |
1548 KB |
Execution killed with signal 11 |
11 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 11 |
12 |
Runtime error |
2 ms |
468 KB |
Execution killed with signal 11 |
13 |
Runtime error |
2 ms |
468 KB |
Execution killed with signal 11 |