#include <bits/stdc++.h>
#pragma GCC optimize("O3")
using namespace std;
struct tree {
const int inf = 1e9;
vector<int> l, r;
vector<int> val;
int n, dbInd = 0;
void build(int v){
if(v >= n) {
l[v] = r[v] = dbInd++;
}else {
build(v*2);
build(v*2+1);
l[v] = l[v*2];
r[v] = r[v*2+1];
}
}
tree(int dd) {
n = dd;
l.resize(2*n);
r.resize(2*n);
val.resize(2*n);
build(1);
}
void change(int v, int L, int R, int x) {
if(L <= l[v] && r[v] <= R) {
val[v] = x;
}else if(R < l[v] || r[v] < L) {
return ;
}else {
change(v*2, L, R, x);
change(v*2+1, L, R, x);
val[v] = min(val[v*2], val[v*2+1]);
}
}
int getMin(int v, int L, int R) {
if(L <= l[v] && r[v] <= R) {
return val[v];
}else if(R < l[v] || r[v] < L) {
return inf;
}else {
return min(getMin(v*2, L, R), getMin(v*2+1, L, R));
}
}
};
const int dydis = 250000 + 100;
const int inf = 1e9;
int n;
tree eile(dydis);
set<pair<int, int> > places;
int minimalPlace = 0;
int A;
void enhance(int ind, int place){
ind--; place--;
places.erase({eile.getMin(1, ind, ind), ind});
if(place == 0) {
eile.change(1, ind, ind, minimalPlace-1);
places.insert({minimalPlace-1, ind});
minimalPlace--;
}else {
auto kur = places.begin();
int nauja = inf;
for(int i = 0; i < place; i++) {
int ind = kur -> second;
int plc = kur -> first;
nauja = plc;
places.erase({plc, ind});
places.insert({plc-1, ind});
eile.change(1, ind, ind, plc-1);
kur++;
}
eile.change(1, ind, ind, nauja);
places.insert({nauja, ind});
minimalPlace--;
}
}
int find(int ind) {
ind--;
// cout << "Findinsiu nuo " << ind << endl;
if(ind == A) {
// cout << "Radau " << 0 << endl;
return 0;
}
if(ind < A) {
// cout << "jis yra kairiau uz A\n";
auto maz = eile.getMin(1, ind, A-1);
// cout << "maziausias yra " << maz.first << ", jo vieta - " << maz.second << endl;
int l = A+1; int r = n-1; int mid, fd = A;
while(l <= r) {
mid = (l + r) / 2;
if(eile.getMin(1, A+1, mid) > maz) {
fd = mid;
l = mid+1;
}else {
r = mid-1;
}
}
// Suvalgysiu viska nuo ind+1 iki fd
return fd - ind;
}else {
auto maz = eile.getMin(1, A+1, ind);
int l = 0; int r = A-1; int mid, fd = A;
while(l <= r) {
mid = (l + r) / 2;
if(eile.getMin(1, mid, A-1) > maz) {
fd = mid;
r = mid-1;
}else {
l = mid+1;
}
}
// Suvalgysiu viska nuo fd iki ind-1
return ind - fd;
}
return 0;
}
int main () {
cin.tie(NULL);
ios_base::sync_with_stdio(false);
cin >> n >> A; A--;
for(int i = 0; i < n; i++) {
int a; cin >> a;
a = n - a;
eile.change(1, i, i, a);
places.insert({a, i});
}
int q; cin >> q;
while(q--) {
char typ;
int a, b; cin >> typ;
if(typ == 'E') {
cin >> a >> b;
enhance(a, b);
}else {
cin >> a;
int ans = find(a);
cout << ans << "\n";
}
}
return 0;
}
/*
5 3
5 1 2 4 3
17
F 1
F 2
F 3
F 4
F 5
E 2 1
F 1
F 2
F 3
F 4
F 5
E 5 2
F 1
F 2
F 3
F 4
F 5
*/
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
10 ms |
6100 KB |
Output is correct |
2 |
Correct |
11 ms |
6196 KB |
Output is correct |
3 |
Correct |
5 ms |
6100 KB |
Output is correct |
4 |
Correct |
20 ms |
6272 KB |
Output is correct |
5 |
Correct |
36 ms |
6740 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
880 ms |
6624 KB |
Output is correct |
2 |
Correct |
442 ms |
6632 KB |
Output is correct |
3 |
Correct |
647 ms |
6660 KB |
Output is correct |
4 |
Correct |
332 ms |
6664 KB |
Output is correct |
5 |
Correct |
824 ms |
7348 KB |
Output is correct |
6 |
Correct |
668 ms |
7380 KB |
Output is correct |
7 |
Correct |
559 ms |
7468 KB |
Output is correct |
8 |
Correct |
365 ms |
7360 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
392 ms |
11404 KB |
Output is correct |
2 |
Correct |
347 ms |
11276 KB |
Output is correct |
3 |
Correct |
336 ms |
11348 KB |
Output is correct |
4 |
Correct |
5 ms |
6100 KB |
Output is correct |
5 |
Correct |
567 ms |
18600 KB |
Output is correct |
6 |
Correct |
443 ms |
18700 KB |
Output is correct |
7 |
Correct |
376 ms |
18416 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
119 ms |
6412 KB |
Output is correct |
2 |
Correct |
107 ms |
6448 KB |
Output is correct |
3 |
Correct |
256 ms |
8672 KB |
Output is correct |
4 |
Correct |
278 ms |
8732 KB |
Output is correct |
5 |
Correct |
361 ms |
6540 KB |
Output is correct |
6 |
Correct |
494 ms |
9820 KB |
Output is correct |
7 |
Correct |
374 ms |
7272 KB |
Output is correct |
8 |
Correct |
390 ms |
11024 KB |
Output is correct |
9 |
Execution timed out |
2063 ms |
19444 KB |
Time limit exceeded |
10 |
Correct |
1118 ms |
7460 KB |
Output is correct |
11 |
Correct |
1526 ms |
8504 KB |
Output is correct |
12 |
Execution timed out |
2053 ms |
16816 KB |
Time limit exceeded |
13 |
Correct |
1787 ms |
19540 KB |
Output is correct |