#include <bits/stdc++.h>
#pragma GCC optimize("O3")
using namespace std;
struct tree {
const int inf = 1e9;
vector<int> l, r;
vector<pair<int, int> > val;
int n, dbInd = 0;
void build(int v){
if(v >= n) {
l[v] = r[v] = dbInd++;
val[v] = {0, l[v]};
}else {
build(v*2);
build(v*2+1);
l[v] = l[v*2];
r[v] = r[v*2+1];
val[v] = min(val[v*2], val[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, l[v]};
}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]);
}
}
pair<int, 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 make_pair(inf, 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).first, 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).first > maz.first) {
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).first > maz.first) {
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
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
8148 KB |
Output is correct |
| 2 |
Correct |
8 ms |
8172 KB |
Output is correct |
| 3 |
Correct |
8 ms |
8176 KB |
Output is correct |
| 4 |
Correct |
19 ms |
8264 KB |
Output is correct |
| 5 |
Correct |
39 ms |
8772 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
840 ms |
12912 KB |
Output is correct |
| 2 |
Correct |
468 ms |
12956 KB |
Output is correct |
| 3 |
Correct |
551 ms |
12960 KB |
Output is correct |
| 4 |
Correct |
319 ms |
13136 KB |
Output is correct |
| 5 |
Correct |
877 ms |
13900 KB |
Output is correct |
| 6 |
Correct |
724 ms |
14304 KB |
Output is correct |
| 7 |
Correct |
598 ms |
14308 KB |
Output is correct |
| 8 |
Correct |
319 ms |
14344 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
402 ms |
14744 KB |
Output is correct |
| 2 |
Correct |
348 ms |
14568 KB |
Output is correct |
| 3 |
Correct |
351 ms |
14540 KB |
Output is correct |
| 4 |
Correct |
7 ms |
8148 KB |
Output is correct |
| 5 |
Correct |
605 ms |
23232 KB |
Output is correct |
| 6 |
Correct |
469 ms |
22936 KB |
Output is correct |
| 7 |
Correct |
433 ms |
22828 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
133 ms |
8812 KB |
Output is correct |
| 2 |
Correct |
111 ms |
8992 KB |
Output is correct |
| 3 |
Correct |
246 ms |
11732 KB |
Output is correct |
| 4 |
Correct |
280 ms |
11720 KB |
Output is correct |
| 5 |
Correct |
352 ms |
9676 KB |
Output is correct |
| 6 |
Correct |
426 ms |
13320 KB |
Output is correct |
| 7 |
Correct |
427 ms |
10944 KB |
Output is correct |
| 8 |
Correct |
330 ms |
15336 KB |
Output is correct |
| 9 |
Execution timed out |
2094 ms |
27280 KB |
Time limit exceeded |
| 10 |
Correct |
1152 ms |
13092 KB |
Output is correct |
| 11 |
Correct |
1468 ms |
14708 KB |
Output is correct |
| 12 |
Execution timed out |
2080 ms |
24884 KB |
Time limit exceeded |
| 13 |
Correct |
1838 ms |
28012 KB |
Output is correct |
