/**
____ ____ ____ ____ ____
||a |||t |||o |||d |||o ||
||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|
**/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N_MAX = 250000;
const int Q_MAX = 500000;
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;
}
int 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 {
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;
newmax.insert(start);
for (int i = start - 1, curr = d[start]; i >= 1; i--) {
if (d[i] > curr) {
newmax.insert(i);
curr = d[i];
}
}
newmax.insert(0);
for (int i = start + 1, curr = d[start]; i <= N; i++) {
if (d[i] > curr) {
newmax.insert(i);
curr = d[i];
}
}
newmax.insert(N + 1);
for (int i = 1; i <= N; i++) {
update(d[*getMax(i)], +1);
where[d[i]] = i;
}
cin >> Q;
while (Q--) {
char type; cin >> type;
if (type == 'F') {
int i; cin >> i;
set <int> :: iterator it = getMax(i);
cout << query(d[*it] - 1) + abs(*it - i) << "\n";
} else {
int i, e; cin >> i >> e; e--;
makeMax(i);
map <int, int> :: iterator it = prev(where.end());
for (int k = 1; k <= e; k++) {
it = prev(it);
makeMax(it->second);
}
}
}
return 0;
}
Compilation message
cake.cpp: In function 'int makeMax(int)':
cake.cpp:78:1: warning: no return statement in function returning non-void [-Wreturn-type]
78 | }
| ^
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
3 ms |
724 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
6 ms |
1884 KB |
Execution killed with signal 11 |
2 |
Runtime error |
6 ms |
2012 KB |
Execution killed with signal 11 |
3 |
Runtime error |
6 ms |
1984 KB |
Execution killed with signal 11 |
4 |
Runtime error |
6 ms |
2016 KB |
Execution killed with signal 11 |
5 |
Runtime error |
12 ms |
3668 KB |
Execution killed with signal 11 |
6 |
Runtime error |
11 ms |
3664 KB |
Execution killed with signal 11 |
7 |
Runtime error |
14 ms |
3660 KB |
Execution killed with signal 11 |
8 |
Runtime error |
11 ms |
3668 KB |
Execution killed with signal 11 |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
46 ms |
11852 KB |
Execution killed with signal 11 |
2 |
Runtime error |
32 ms |
11764 KB |
Execution killed with signal 11 |
3 |
Runtime error |
33 ms |
11760 KB |
Execution killed with signal 11 |
4 |
Runtime error |
3 ms |
724 KB |
Execution killed with signal 11 |
5 |
Runtime error |
145 ms |
28468 KB |
Execution killed with signal 11 |
6 |
Runtime error |
177 ms |
28340 KB |
Execution killed with signal 11 |
7 |
Runtime error |
78 ms |
28248 KB |
Execution killed with signal 11 |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
4 ms |
1108 KB |
Execution killed with signal 11 |
2 |
Runtime error |
5 ms |
1364 KB |
Execution killed with signal 11 |
3 |
Runtime error |
22 ms |
6384 KB |
Execution killed with signal 11 |
4 |
Runtime error |
19 ms |
6356 KB |
Execution killed with signal 11 |
5 |
Runtime error |
4 ms |
980 KB |
Execution killed with signal 11 |
6 |
Runtime error |
30 ms |
8072 KB |
Execution killed with signal 11 |
7 |
Runtime error |
7 ms |
2004 KB |
Execution killed with signal 11 |
8 |
Runtime error |
58 ms |
11852 KB |
Execution killed with signal 11 |
9 |
Runtime error |
134 ms |
28364 KB |
Execution killed with signal 11 |
10 |
Runtime error |
4 ms |
1000 KB |
Execution killed with signal 11 |
11 |
Runtime error |
10 ms |
3144 KB |
Execution killed with signal 11 |
12 |
Runtime error |
107 ms |
23116 KB |
Execution killed with signal 11 |
13 |
Runtime error |
135 ms |
28404 KB |
Execution killed with signal 11 |