#include <bits/stdc++.h>
using namespace std;
template<int sz> struct DS{
int seg[sz * 2];
void upd(int i, int v){
seg[i += sz] = v;
for (i /= 2; i; i /= 2) seg[i] = max(seg[i * 2], seg[i * 2 + 1]);
}
int qry(int l, int r){
int ans = 0;
for (l += sz, r += sz; l <= r; r /= 2, l /= 2){
if (l % 2 == 1) ans = max(ans, seg[l++]);
if (r % 2 == 0) ans = max(seg[r--], ans);
}
return ans;
}
int walk(int v){
int i = 1;
while (i < sz) i = (seg[i * 2] < v) ? i * 2 + 1 : i * 2;
return i - sz - 1;
}
};
const int mN = 2.5e5 + 5, mQ = 5e5 + 5;
int n, a, q; pair<int, int> tmp[mN]; DS<(1 << 19)> L, R;
deque<int> w10; int net = mN;
void ins(int pos, int v){
if (pos < a) L.upd(a - pos, v);
if (pos > a) R.upd(pos - a, v);
}
int main(){
cin >> n >> a;
for (int i = 1; i <= n; i++) cin >> tmp[i].first, tmp[i].second = i;
sort(tmp + 1, tmp + n + 1);
for (int i = 1; i <= n; i++){
int pos = tmp[i].second, r = i;
if (i >= n - 9) r += mQ * 2, w10.push_back(pos);
ins(pos, r);
}
cin >> q; L.upd(a, 1e9); R.upd(n - a + 1, 1e9);
while (q--){
int pos; char type; cin >> type >> pos;
if (type == 'E'){
int e; cin >> e;
auto it = find(w10.begin(), w10.end(), pos);
if (it != w10.end()) w10.erase(it);
w10.insert(w10.end() - e + 1, pos);
if (w10.size() > 10) ins(w10[0], ++net);
for (int i = 0; i < w10.size(); i++) ins(w10[i], mQ * 2 + i);
}
else{
int ans = pos;
if (pos < a) ans = R.walk(L.qry(1, a - pos)) + a;
if (pos > a) ans = a - L.walk(R.qry(1, pos - a));
cout<<abs(pos - ans)<<"\n";
}
}
}
Compilation message
cake.cpp: In function 'int main()':
cake.cpp:54:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::deque<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
54 | for (int i = 0; i < w10.size(); i++) ins(w10[i], mQ * 2 + i);
| ~~^~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
332 KB |
Output is correct |
| 2 |
Correct |
1 ms |
332 KB |
Output is correct |
| 3 |
Correct |
2 ms |
308 KB |
Output is correct |
| 4 |
Correct |
89 ms |
448 KB |
Output is correct |
| 5 |
Correct |
646 ms |
680 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
2091 ms |
532 KB |
Time limit exceeded |
| 2 |
Execution timed out |
2090 ms |
460 KB |
Time limit exceeded |
| 3 |
Execution timed out |
2083 ms |
544 KB |
Time limit exceeded |
| 4 |
Correct |
683 ms |
464 KB |
Output is correct |
| 5 |
Execution timed out |
2083 ms |
784 KB |
Time limit exceeded |
| 6 |
Execution timed out |
2100 ms |
716 KB |
Time limit exceeded |
| 7 |
Execution timed out |
2092 ms |
716 KB |
Time limit exceeded |
| 8 |
Correct |
691 ms |
716 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
208 ms |
2480 KB |
Output is correct |
| 2 |
Correct |
210 ms |
2336 KB |
Output is correct |
| 3 |
Correct |
201 ms |
2348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
332 KB |
Output is correct |
| 5 |
Correct |
272 ms |
4892 KB |
Output is correct |
| 6 |
Correct |
339 ms |
4868 KB |
Output is correct |
| 7 |
Correct |
255 ms |
4708 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
2076 ms |
604 KB |
Time limit exceeded |
| 2 |
Execution timed out |
2074 ms |
648 KB |
Time limit exceeded |
| 3 |
Execution timed out |
2084 ms |
1356 KB |
Time limit exceeded |
| 4 |
Execution timed out |
2080 ms |
1356 KB |
Time limit exceeded |
| 5 |
Execution timed out |
2070 ms |
472 KB |
Time limit exceeded |
| 6 |
Execution timed out |
2075 ms |
1484 KB |
Time limit exceeded |
| 7 |
Execution timed out |
2064 ms |
604 KB |
Time limit exceeded |
| 8 |
Execution timed out |
2078 ms |
1952 KB |
Time limit exceeded |
| 9 |
Execution timed out |
2048 ms |
4344 KB |
Time limit exceeded |
| 10 |
Execution timed out |
2094 ms |
564 KB |
Time limit exceeded |
| 11 |
Execution timed out |
2089 ms |
964 KB |
Time limit exceeded |
| 12 |
Execution timed out |
2083 ms |
3736 KB |
Time limit exceeded |
| 13 |
Execution timed out |
2088 ms |
4456 KB |
Time limit exceeded |
