#include<bits/stdc++.h>
using namespace std;
const int N = 3e5 + 1;
int n, a, d[N];
int t[N << 2];
int pos[N];
void _upd(int i,int l,int r,int p,int v) {
if (l > p || r < p) return;
if (l == r) {
t[i] = v;
return;
}
int m = (l + r) / 2;
_upd(i << 1 ,l,m,p,v); ++m;
_upd(i << 1 | 1,m,r,p,v);
t[i] = max(t[i << 1],t[i << 1 | 1]);
}
int _get(int i,int l,int r,int L,int R) {
if (l > R || r < L) return -1;
if (L <= l && r <= R) return t[i];
int m = (l + r) / 2;
return max(_get(i << 1,l,m,L,R),_get(i << 1 | 1,m + 1,r,L,R));
}
int _rig(int i,int l,int r,int p,int v) {
if (r < p || t[i] < v) return -1;
if (l == r) return l;
int m = (l + r) / 2;
int res = _rig(i << 1 ,l,m,p,v); ++m;
if (res < 0)
res = _rig(i << 1 | 1,m,r,p,v);
return res;
}
int _lef(int i,int l,int r,int p,int v) {
if (l > p || t[i] < v) return -1;
if (l == r) return l;
int m = (l + r + 2) / 2;
int res = _lef(i << 1 | 1,m,r,p,v); --m;
if (res < 0)
res = _lef(i << 1 ,l,m,p,v);
return res;
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> n >> a;
for(int i = 1 ; i <= n ; ++i) {
cin >> d[i];
_upd(1,1,n,i,d[i]);
pos[n - d[i] + 1] = i;
}
int tot = n;
int q; cin >> q;
while (q--) {
char t;
int x;
cin >> t >> x;
if (t == 'E') {
int y; cin >> y;
for(int i = min(10,n) ; i > y ; --i)
pos[i] = pos[i - 1];
pos[y] = x;
for(int i = y ; i ; --i) {
d[pos[i]] = ++tot;
_upd(1,1,n,pos[i],tot);
}
}
else {
if (x == a || a == 1 || a == n) {
cout << abs(x - a) << "\n";
continue;
}
int res;
if (x < a) {
res = _rig(1,1,n,a + 1,_get(1,1,n,x,a - 1));
if (res < 0) res = n;
else res--;
}
if (x > a) {
res = _lef(1,1,n,a - 1,_get(1,1,n,a + 1,x));
if (res < 0) res = 1;
else res++;
}
cout << abs(res - x) << "\n";
}
}
}
Compilation message
cake.cpp: In function 'int main()':
cake.cpp:95:20: warning: 'res' may be used uninitialized in this function [-Wmaybe-uninitialized]
cout << abs(res - x) << "\n";
~~~~^~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Incorrect |
2 ms |
448 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
248 ms |
800 KB |
Output isn't correct |
2 |
Correct |
163 ms |
828 KB |
Output is correct |
3 |
Correct |
182 ms |
828 KB |
Output is correct |
4 |
Correct |
119 ms |
844 KB |
Output is correct |
5 |
Incorrect |
281 ms |
1108 KB |
Output isn't correct |
6 |
Correct |
234 ms |
1140 KB |
Output is correct |
7 |
Correct |
202 ms |
1140 KB |
Output is correct |
8 |
Correct |
128 ms |
1140 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
79 ms |
2980 KB |
Output is correct |
2 |
Correct |
67 ms |
2996 KB |
Output is correct |
3 |
Correct |
60 ms |
2996 KB |
Output is correct |
4 |
Incorrect |
2 ms |
2996 KB |
Output isn't correct |
5 |
Correct |
120 ms |
5368 KB |
Output is correct |
6 |
Incorrect |
121 ms |
5368 KB |
Output isn't correct |
7 |
Correct |
98 ms |
5368 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
31 ms |
5368 KB |
Output isn't correct |
2 |
Correct |
25 ms |
5368 KB |
Output is correct |
3 |
Correct |
54 ms |
5368 KB |
Output is correct |
4 |
Correct |
64 ms |
5368 KB |
Output is correct |
5 |
Incorrect |
79 ms |
5368 KB |
Output isn't correct |
6 |
Correct |
96 ms |
5368 KB |
Output is correct |
7 |
Correct |
88 ms |
5368 KB |
Output is correct |
8 |
Correct |
118 ms |
5368 KB |
Output is correct |
9 |
Incorrect |
504 ms |
6352 KB |
Output isn't correct |
10 |
Incorrect |
260 ms |
6352 KB |
Output isn't correct |
11 |
Correct |
322 ms |
6352 KB |
Output is correct |
12 |
Correct |
655 ms |
6352 KB |
Output is correct |
13 |
Incorrect |
408 ms |
6372 KB |
Output isn't correct |