#include<cstdio>
#include<functional>
#include<cstdlib>
#include<algorithm>
#include<vector>
#include<map>
using namespace std;
const int inf = 1000000000;
int N, A, Q;
int values[250010];
int seg[2][1000010];
map <int,int,greater <int>> indexes;
vector <int> hold;
void buildSeg(int d, int v, int tl, int tr){
if(tl > tr) return;
if(tl == tr){
seg[d][v] = values[tl];
return;
}
int tm = (tl + tr) / 2;
buildSeg(d, v * 2, tl, tm);
buildSeg(d, v * 2 + 1, tm + 1, tr);
seg[d][v] = max(seg[d][v * 2], seg[d][v * 2 + 1]);
}
void updSeg(int d, int p, int x, int v, int tl, int tr){
if(p == A){
indexes.erase(values[p]);
values[p] = x;
indexes[x] = p;
return;
}
if(p < tl || p > tr) return;
if(tl == tr){
indexes.erase(values[p]);
values[p] = x;
seg[d][v] = x;
indexes[x] = p;
return;
}
int tm = (tl + tr) / 2;
updSeg(d, p, x, v * 2, tl, tm);
updSeg(d, p, x, v * 2 + 1, tm + 1, tr);
seg[d][v] = max(seg[d][v * 2], seg[d][v * 2 + 1]);
}
int qrySeg(int d, int l, int r, int v, int tl, int tr){
if(l > r) return 0;
if(l == tl && r == tr) return seg[d][v];
int tm = (tl + tr) / 2;
return max(qrySeg(d, l, min(r, tm), v * 2, tl, tm), qrySeg(d, max(l, tm + 1), r, v * 2 + 1, tm + 1, tr));
}
int walkSeg(int d, int l, int r, int x, int v, int tl, int tr){
if(l > r) return -1;
if(l == tl && r == tr && seg[d][v] < x) return -1;
if(tl == tr) return tl;
int tm = (tl + tr) / 2;
int both[2][7] = {{d, max(l, tm + 1), r, x, v * 2 + 1, tm + 1, tr}, {d, l, min(r, tm), x, v * 2, tl, tm}};
int first = walkSeg(both[d][0], both[d][1], both[d][2], both[d][3], both[d][4], both[d][5], both[d][6]);
if(first == -1) first = walkSeg(both[!d][0], both[!d][1], both[!d][2], both[!d][3], both[!d][4], both[!d][5], both[!d][6]);
return first;
}
int main(){
scanf("%d%d",&N,&A);
values[0] = inf;
values[N + 1] = inf;
for(int i = 1;i < N + 1;i++){
scanf("%d",&values[i]);
indexes[values[i]] = i;
}
scanf("%d\n",&Q);
int rans[2][2] = {{0, A - 1}, {A + 1, N + 1}};
buildSeg(0, 1, rans[0][0], rans[0][1]);
buildSeg(1, 1, rans[1][0], rans[1][1]);
for(int i = 0;i < Q;i++){
char t;
scanf("%c ",&t);
if(t == 'E'){
int k, e;
scanf("%d%d\n",&k,&e);
int cnt = 1;
int num;
for(auto j : indexes){
if(cnt == e){
num = j.first + 1;
break;
}
hold.push_back(j.second);
cnt++;
}
for(int j : hold){
updSeg(j > A, j, values[j] + 1, 1, rans[j > A][0], rans[j > A][1]);
}
updSeg(k > A, k, num, 1, rans[k > A][0], rans[k > A][1]);
hold.clear();
}
else{
int b;
scanf("%d\n",&b);
if(b == A){
printf("0\n");
continue;
}
int val;
if(b < A) val = qrySeg(0, b, A - 1, 1, 0, A - 1);
else val = qrySeg(1, A + 1, b, 1, A + 1, N + 1);
printf("%d\n",abs(b - walkSeg(b < A, rans[b < A][0], rans[b < A][1], val, 1, rans[b < A][0], rans[b < A][1])) - 1);
}
}
}
Compilation message
cake.cpp: In function 'int main()':
cake.cpp:62:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
62 | scanf("%d%d",&N,&A);
| ~~~~~^~~~~~~~~~~~~~
cake.cpp:66:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
66 | scanf("%d",&values[i]);
| ~~~~~^~~~~~~~~~~~~~~~~
cake.cpp:69:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
69 | scanf("%d\n",&Q);
| ~~~~~^~~~~~~~~~~
cake.cpp:75:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
75 | scanf("%c ",&t);
| ~~~~~^~~~~~~~~~
cake.cpp:78:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
78 | scanf("%d%d\n",&k,&e);
| ~~~~~^~~~~~~~~~~~~~~~
cake.cpp:97:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
97 | scanf("%d\n",&b);
| ~~~~~^~~~~~~~~~~
cake.cpp:92:19: warning: 'num' may be used uninitialized in this function [-Wmaybe-uninitialized]
92 | updSeg(k > A, k, num, 1, rans[k > A][0], rans[k > A][1]);
| ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
292 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| 4 |
Correct |
6 ms |
340 KB |
Output is correct |
| 5 |
Correct |
17 ms |
1072 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
651 ms |
5440 KB |
Output is correct |
| 2 |
Correct |
283 ms |
5276 KB |
Output is correct |
| 3 |
Correct |
438 ms |
5268 KB |
Output is correct |
| 4 |
Correct |
244 ms |
5264 KB |
Output is correct |
| 5 |
Correct |
705 ms |
6388 KB |
Output is correct |
| 6 |
Correct |
525 ms |
6936 KB |
Output is correct |
| 7 |
Correct |
462 ms |
6796 KB |
Output is correct |
| 8 |
Correct |
274 ms |
6860 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
100 ms |
8288 KB |
Output is correct |
| 2 |
Correct |
85 ms |
8168 KB |
Output is correct |
| 3 |
Correct |
83 ms |
8076 KB |
Output is correct |
| 4 |
Correct |
0 ms |
212 KB |
Output is correct |
| 5 |
Correct |
217 ms |
18228 KB |
Output is correct |
| 6 |
Correct |
199 ms |
18120 KB |
Output is correct |
| 7 |
Correct |
126 ms |
17940 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
64 ms |
1044 KB |
Output is correct |
| 2 |
Correct |
44 ms |
1120 KB |
Output is correct |
| 3 |
Correct |
99 ms |
4432 KB |
Output is correct |
| 4 |
Correct |
130 ms |
4428 KB |
Output is correct |
| 5 |
Correct |
176 ms |
1760 KB |
Output is correct |
| 6 |
Correct |
182 ms |
6568 KB |
Output is correct |
| 7 |
Correct |
168 ms |
3012 KB |
Output is correct |
| 8 |
Correct |
262 ms |
8908 KB |
Output is correct |
| 9 |
Correct |
1168 ms |
22992 KB |
Output is correct |
| 10 |
Correct |
573 ms |
5188 KB |
Output is correct |
| 11 |
Correct |
741 ms |
7224 KB |
Output is correct |
| 12 |
Correct |
1126 ms |
20032 KB |
Output is correct |
| 13 |
Correct |
862 ms |
24064 KB |
Output is correct |
