#include<bits/stdc++.h>
const int N = 250005;
using namespace std;
int n, st, a[N], q, last[20], it[N << 2], cnt;
void init(int i, int l, int r){
if (l == r){
it[i] = a[l];
return;
}
int mid = (l + r) >> 1;
init(i << 1, l, mid); init(i << 1 | 1, mid+1, r);
it[i] = max(it[i << 1], it[i << 1 | 1]);
}
void update(int i, int l, int r, int pos, int val){
if (l > pos || pos > r) return;
if (l == r){
it[i] = val;
return;
}
int mid = (l + r) >> 1;
update(i << 1, l, mid, pos, val); update(i << 1 | 1, mid+1, r, pos, val);
it[i] = max(it[i << 1], it[i << 1 | 1]);
}
int get(int i, int l, int r, int L, int R){
if (L > r || l > R) return -1;
if (L <= l && r <= R) return it[i];
int mid = (l + r) >> 1;
return max(get(i << 1, l, mid, L, R), get(i << 1 | 1, mid+1, r, L, R));
}
int rig(int i, int l, int r, int pos, int val){
if (r < pos) return -1;
if (it[i] < val) return -1;
if (l == r) return l;
int mid = (l + r) >> 1;
int ans = rig(i << 1, l, mid, pos, val);
if (ans == -1) ans = rig(i << 1 | 1, mid+1, r, pos, val);
return ans;
}
int lef(int i, int l, int r, int pos, int val){
if (l > pos) return -1;
if (it[i] < val) return -1;
if (l == r) return l;
int mid = (l + r) >> 1;
int ans = lef(i << 1 | 1, mid+1, r, pos, val);
if (ans == -1) ans = lef(i << 1, l, mid, pos, val);
return ans;
}
int main(){
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
cin >> n >> st;
for (int i = 1; i <= n; i++) {
cin >> a[i];
if (a[i] > n-10) last[n-a[i]+1] = i;
}
init(1, 1, n); cnt = n;
cin >> q;
while (q--){
char c; int pos, e;
cin >> c;
if (c == 'E'){
cin >> pos >> e;
for (int i = min(10, n); i > e; i--) last[i] = last[i-1];
last[e] = pos;
for (int i = e; i >= 1; i--) {
a[last[i]] = ++cnt;
update(1, 1, n, last[i], a[last[i]]);
}
}
else{
cin >> pos;
if (pos == st) {
cout << 0 << "\n";
continue;
}
int Max, ans;
if (pos < st){
Max = get(1, 1, n, pos, st-1);
ans = rig(1, 1, n, st+1, Max);
if (ans == -1) ans = n;
else ans--;
ans = abs(pos - ans);
}
else{
Max = get(1, 1, n, st+1, pos);
ans = lef(1, 1, n, st-1, Max);
if (ans == -1) ans = 1;
else ans++;
ans = abs(pos - ans);
}
cout << ans << "\n";
}
}
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Incorrect |
2 ms |
452 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
230 ms |
544 KB |
Output isn't correct |
2 |
Correct |
158 ms |
712 KB |
Output is correct |
3 |
Correct |
173 ms |
712 KB |
Output is correct |
4 |
Correct |
117 ms |
712 KB |
Output is correct |
5 |
Incorrect |
265 ms |
872 KB |
Output isn't correct |
6 |
Correct |
227 ms |
888 KB |
Output is correct |
7 |
Correct |
195 ms |
932 KB |
Output is correct |
8 |
Correct |
124 ms |
1068 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
65 ms |
2500 KB |
Output is correct |
2 |
Correct |
51 ms |
2500 KB |
Output is correct |
3 |
Correct |
47 ms |
2500 KB |
Output is correct |
4 |
Incorrect |
2 ms |
2500 KB |
Output isn't correct |
5 |
Correct |
82 ms |
4212 KB |
Output is correct |
6 |
Incorrect |
79 ms |
4380 KB |
Output isn't correct |
7 |
Correct |
62 ms |
4380 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
29 ms |
4380 KB |
Output isn't correct |
2 |
Correct |
25 ms |
4380 KB |
Output is correct |
3 |
Correct |
51 ms |
4380 KB |
Output is correct |
4 |
Correct |
61 ms |
4380 KB |
Output is correct |
5 |
Incorrect |
77 ms |
4380 KB |
Output isn't correct |
6 |
Correct |
89 ms |
4380 KB |
Output is correct |
7 |
Correct |
86 ms |
4380 KB |
Output is correct |
8 |
Correct |
97 ms |
4380 KB |
Output is correct |
9 |
Incorrect |
624 ms |
5420 KB |
Output isn't correct |
10 |
Incorrect |
249 ms |
5420 KB |
Output isn't correct |
11 |
Correct |
318 ms |
5420 KB |
Output is correct |
12 |
Correct |
441 ms |
5420 KB |
Output is correct |
13 |
Incorrect |
366 ms |
5436 KB |
Output isn't correct |