#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
typedef pair<int, int> ii;
const int N = 250005;
ii it[2][4 * N];
int n, q, a[N], x, cnt, p[15];
vector<ii> vec;
ii compare(ii b, ii c, int type) {
if(b.fi > c.fi) swap(b, c);
if(type == 1) {
if(b.fi == c.fi)
return {b.fi, max(b.se, c.se)};
else
return c;
}
else {
if(b.fi == c.fi)
return {b.fi, min(b.se, c.se)};
else
return c;
}
}
void build_tree(int type, int k, int l, int r) {
if(l == r) {
it[type][k] = {a[l], l};
return ;
}
int mid = (l + r) / 2;
build_tree(type, k << 1, l, mid);
build_tree(type, k << 1 | 1, mid + 1, r);
if(type == 0)
it[type][k] = compare(it[type][k << 1], it[type][k << 1 | 1], 1);
else
it[type][k] = compare(it[type][k << 1], it[type][k << 1 | 1], 2);
}
void update(int k, int l, int r, int pos, int val, int type) {
if(r < pos || pos < l) return ;
if(pos <= l && r <= pos) {
it[type][k] = {val, l};
return ;
}
int mid = (l + r) >> 1;
update(k << 1, l, mid, pos, val, type);
update(k << 1 | 1, mid + 1, r, pos, val, type);
if(pos < x)
it[type][k] = compare(it[type][k << 1], it[type][k << 1 | 1], 1);
else
it[type][k] = compare(it[type][k << 1], it[type][k << 1 | 1], 2);
}
int get(int k, int l, int r, int L, int R, int type) {
if(r < L || R < l || L > R) return 0;
if(L <= l && r <= R)
return it[type][k].fi;
int mid = (l + r) >> 1;
return max(get(k << 1, l, mid, L, R, type), get(k << 1 | 1, mid + 1, r, L, R, type));
}
int climb(int k, int l, int r, int L, int R, int type, int val) {
if(r < L || R < l || L > R) return -1;
if(l == r)
return it[type][k].se;
int mid = (l + r) >> 1;
if(type == 0) {
if(it[type][k << 1 | 1].fi >= val)
return climb(k << 1 | 1, mid + 1, r, L, R, type, val);
return climb(k << 1, l, mid, L, R, type, val);
}
else {
if(it[type][k << 1].fi >= val)
return climb(k << 1, l, mid, L, R, type, val);
return climb(k << 1 | 1, mid + 1, r, L, R, type, val);
}
}
void getpos(int pos) {
int val, po;
if(pos < x) {
val = get(1, 1, x - 1, pos, x - 1, 0);
if(x + 1 <= n) {
po = climb(1, x + 1, n, x + 1, n, 1, val);
if(get(1, x + 1, n, x + 1, po, 1) > val)
cout << abs(po - 1 - pos) << "\n";
else
cout << abs(po - pos) << "\n";
return ;
}
else {
cout << n - pos << "\n";
return ;
}
}
else {
val = get(1, x + 1, n, x + 1, pos, 1);
if(x - 1 >= 1) {
po = climb(1, 1, x - 1, 1, x - 1, 0, val);
if(get(1, 1, x - 1, po, x - 1, 0) > val)
cout << abs(pos - po - 1) << "\n";
else
cout << abs(po - pos) << "\n";
return ;
}
else {
cout << pos - 1 << "\n";
return ;
}
}
//cout << val << " " << po << " " << pos << "\n";
}
int main() {
cin.tie(0), ios::sync_with_stdio(0);
//freopen("test.inp", "r", stdin);
cin >> n >> x;
for(int i = 1; i <= n; i++) {
cin >> a[i];
vec.pb({a[i], i});
}
if(x - 1 >= 1)
build_tree(0, 1, 1, x - 1);
if(x + 1 <= n)
build_tree(1, 1, x + 1, n);
sort(vec.begin(), vec.end());
for(int i = n - 1; i >= max(0, n - 11); i--)
p[n - i] = vec[i].se;
cnt = n;
cin >> q;
while(q--) {
char c;
int pos, e;
cin >> c;
if(c == 'F') {
cin >> pos;
if(pos == x) cout << "0\n";
else getpos(pos);
}
else {
cin >> pos >> e;
int lim = min(n, 10);
for(int i = lim; i >= e + 1; i--) {
if(p[i] == pos) {
lim = i;
break;
}
}
for(int i = lim; i >= e + 1; i--)
p[i] = p[i - 1];
p[e] = pos;
for(int i = e; i >= 1; i--) {
if(p[i] == x) {++cnt; continue;}
if(p[i] < x)
update(1, 1, x - 1, p[i], ++cnt, 0);
else
update(1, x + 1, n, p[i], ++cnt, 1);
}
}
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
380 KB |
Output is correct |
| 3 |
Correct |
2 ms |
584 KB |
Output is correct |
| 4 |
Correct |
5 ms |
584 KB |
Output is correct |
| 5 |
Correct |
11 ms |
1156 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
277 ms |
1176 KB |
Output is correct |
| 2 |
Correct |
130 ms |
1280 KB |
Output is correct |
| 3 |
Correct |
205 ms |
1280 KB |
Output is correct |
| 4 |
Correct |
128 ms |
1280 KB |
Output is correct |
| 5 |
Correct |
308 ms |
1648 KB |
Output is correct |
| 6 |
Correct |
245 ms |
1664 KB |
Output is correct |
| 7 |
Correct |
228 ms |
1664 KB |
Output is correct |
| 8 |
Correct |
141 ms |
1664 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
73 ms |
4728 KB |
Output is correct |
| 2 |
Correct |
68 ms |
4728 KB |
Output is correct |
| 3 |
Correct |
62 ms |
4728 KB |
Output is correct |
| 4 |
Correct |
2 ms |
4728 KB |
Output is correct |
| 5 |
Correct |
116 ms |
8596 KB |
Output is correct |
| 6 |
Correct |
107 ms |
8660 KB |
Output is correct |
| 7 |
Correct |
94 ms |
8660 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
33 ms |
8660 KB |
Output is correct |
| 2 |
Correct |
26 ms |
8660 KB |
Output is correct |
| 3 |
Correct |
56 ms |
8660 KB |
Output is correct |
| 4 |
Correct |
71 ms |
8660 KB |
Output is correct |
| 5 |
Correct |
90 ms |
8660 KB |
Output is correct |
| 6 |
Correct |
102 ms |
8660 KB |
Output is correct |
| 7 |
Correct |
98 ms |
8660 KB |
Output is correct |
| 8 |
Correct |
126 ms |
8660 KB |
Output is correct |
| 9 |
Correct |
540 ms |
9528 KB |
Output is correct |
| 10 |
Correct |
300 ms |
9528 KB |
Output is correct |
| 11 |
Correct |
369 ms |
9528 KB |
Output is correct |
| 12 |
Correct |
541 ms |
9528 KB |
Output is correct |
| 13 |
Correct |
442 ms |
11696 KB |
Output is correct |
