#include<bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set tree<long long, null_type,greater<long long>, rb_tree_tag,tree_order_statistics_node_update>
const int mxN = 250001;
int n, A;
long long a[mxN];
struct IT {
struct Nds {
int L, H, pos;
long long x;
} nds[mxN << 2];
int leaf[mxN];
Nds merge(Nds a, Nds b) {
Nds c;
c.L = a.L; c.H = b.H;
if (a.x >= b.x + (a.L < A)) {
c.x = a.x; c.pos = a.pos;
}
else {
c.x = b.x; c.pos = b.pos;
}
return c;
}
void build(int x, int lo, int hi) {
nds[x].L = lo, nds[x].H = hi;
if (lo == hi) {
leaf[hi] = x;
nds[x].x = a[hi];
nds[x].pos = hi;
return ;
}
int mid = (lo + hi) >> 1;
build(x << 1, lo, mid);
build(x << 1 | 1, mid + 1, hi);
nds[x] = merge(nds[x << 1], nds[x << 1 | 1]);
}
void upd(int pos, long long val) {
int x = leaf[pos];
for (nds[x].x = val, x >>= 1; x; x >>= 1) {
nds[x] = merge(nds[x << 1], nds[x << 1 | 1]);
}
}
long long get_mx(int l, int r, int x = 1) {
if (nds[x].L > r || nds[x].H < l) {
return -1;
}
if (nds[x].L >= l && nds[x].H <= r) {
return nds[x].x;
}
return max(get_mx(l, r, x << 1), get_mx(l, r, x << 1 | 1));
}
int get_pos1(int l, int r, long long val, int x = 1) {
if (nds[x].L > r || nds[x].H < l) {
return -1;
}
if (nds[x].x < val) {
return -1;
}
if (nds[x].L == nds[x].H) {
return nds[x].pos;
}
/*if (nds[x].L >= l && nds[x].H <= r) {
return nds[x].pos;
}*/
int res = get_pos1(l, r, val, x << 1 | 1);
if (res >= 0) {
return res;
}
return get_pos1(l, r, val, x << 1);
}
int get_pos2(int l, int r, long long val, int x = 1) {
if (nds[x].L > r || nds[x].H < l) {
return n;
}
if (nds[x].x < val) {
return n;
}
if (nds[x].L == nds[x].H) {
return nds[x].pos;
}
int res = get_pos2(l, r, val, x << 1);
if (res < n) {
return res;
}
return get_pos2(l, r, val, x << 1 | 1);
}
} its;
long long cur[mxN];
int pos[mxN];
map<int, int> lst;
vector< array<int, 2> > top;
int main() {
cin.tie(0)->sync_with_stdio(0);
cin >> n >> A; A--;
for (int i = 0; i < n; i++) {
cin >> a[i]; a[i]--;
pos[a[i]] = i;
}
for (int i = 0; i < n; i++) {
top.push_back({i, pos[i]});
}
int q; cin >> q;
q++;
its.build(1, 0, n - 1);
char type; int e, x;
while (--q) {
cin >> type >> x; x--;
if (type == 'E') {
cin >> e; e--;
deque< array<int, 2> > deq;
lst.clear();
lst[x] = 1;
while (deq.size() < e) {
if (lst.find(top.back()[1]) == lst.end()) {
lst[top.back()[1]] = 1;
deq.push_front(top.back());
}
top.pop_back();
}
its.upd(x, top.back()[0] + 1);
top.push_back({top.back()[0] + 1, x});
while (!deq.empty()) {
its.upd(deq.front()[1], top.back()[0] + 1);
top.push_back({top.back()[1] + 1, deq.front()[1]});
deq.pop_front();
}
}
else {
if (x == A) {
cout << "0\n";
}
else {
if (A == 0 || A == n - 1) {
cout << abs(x - A) << "\n";
}
else {
if (x > A) {
cout << x - 1 - its.get_pos1(0, A - 1, its.get_mx(A + 1, x)) << "\n";
}
else {
cout << its.get_pos2(A + 1, n - 1, its.get_mx(x, A - 1)) - x - 1 << "\n";
}
}
}
}
}
return 0;
}
Compilation message
cake.cpp: In function 'int main()':
cake.cpp:136:22: warning: comparison of integer expressions of different signedness: 'std::deque<std::array<int, 2> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
136 | while (deq.size() < e) {
| ~~~~~~~~~~~^~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
0 ms |
332 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
352 ms |
3436 KB |
Output isn't correct |
2 |
Incorrect |
201 ms |
5560 KB |
Output isn't correct |
3 |
Incorrect |
222 ms |
5448 KB |
Output isn't correct |
4 |
Correct |
129 ms |
5456 KB |
Output is correct |
5 |
Incorrect |
358 ms |
6648 KB |
Output isn't correct |
6 |
Incorrect |
298 ms |
4468 KB |
Output isn't correct |
7 |
Incorrect |
234 ms |
10712 KB |
Output isn't correct |
8 |
Correct |
138 ms |
10668 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
70 ms |
9512 KB |
Output isn't correct |
2 |
Incorrect |
50 ms |
9284 KB |
Output isn't correct |
3 |
Incorrect |
44 ms |
9124 KB |
Output isn't correct |
4 |
Correct |
0 ms |
332 KB |
Output is correct |
5 |
Incorrect |
91 ms |
19176 KB |
Output isn't correct |
6 |
Incorrect |
88 ms |
19292 KB |
Output isn't correct |
7 |
Incorrect |
63 ms |
18752 KB |
Output isn't correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
41 ms |
964 KB |
Output isn't correct |
2 |
Incorrect |
25 ms |
1236 KB |
Output isn't correct |
3 |
Incorrect |
55 ms |
5452 KB |
Output isn't correct |
4 |
Incorrect |
76 ms |
5404 KB |
Output isn't correct |
5 |
Incorrect |
108 ms |
1836 KB |
Output isn't correct |
6 |
Incorrect |
105 ms |
7000 KB |
Output isn't correct |
7 |
Incorrect |
104 ms |
2624 KB |
Output isn't correct |
8 |
Incorrect |
121 ms |
12216 KB |
Output isn't correct |
9 |
Incorrect |
627 ms |
22268 KB |
Output isn't correct |
10 |
Incorrect |
361 ms |
3700 KB |
Output isn't correct |
11 |
Incorrect |
434 ms |
7772 KB |
Output isn't correct |
12 |
Incorrect |
601 ms |
21168 KB |
Output isn't correct |
13 |
Incorrect |
462 ms |
21884 KB |
Output isn't correct |