#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));
}
}
int rightmost(int v, int L, int R, int x) {
// randa desiniausia 'i' is [L; R], kad min(L; a[i]) >= x
// cout << "esu node [" << l[v] << "; " << r[v] << "]\n";
if(L <= l[v] && r[v] <= R) {
if(l[v] == r[v]) {
if(val[v] >= x) return l[v];
else return -inf;
}
if(val[v*2] >= x) {
return max(r[v*2], rightmost(v*2+1, L, R, x));
}else {
return rightmost(v*2, L, R, x);
}
}else if(R < l[v] || r[v] < L) {
return -inf;
}else {
if(r[v*2] < L) return rightmost(v*2+1, L, R, x);
int kaireje = rightmost(v*2, L, R, x);
if(kaireje != r[v*2]) {
return kaireje;
}else {
return max(r[v*2], rightmost(v*2+1, L, R, x));
}
}
}
int leftmost(int v, int L, int R, int x) {
// randa kairiausia 'i' is [L; R], kad min(a[i]; R) >= x
// cout << "esu node [" << l[v] << "; " << r[v] << "]\n";
if(L <= l[v] && r[v] <= R) {
if(l[v] == r[v]) {
if(val[v] >= x) return l[v];
else return inf;
}
if(val[v*2+1] >= x) {
return min(l[v*2+1], leftmost(v*2, L, R, x));
}else {
return leftmost(v*2+1, L, R, x);
}
}else if(R < l[v] || r[v] < L) {
return inf;
}else {
if(l[v*2+1] > R) return leftmost(v*2, L, R, x);
int desineje = leftmost(v*2+1, L, R, x);
if(desineje != l[v*2+1]) {
return desineje;
}else {
return min(l[v*2+1], leftmost(v*2, L, R, x));
}
}
}
};
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;
}
}*/
fd = max(A, eile.rightmost(1, A+1, n-1, maz));
/* cout << "vietos atrodo taip: ";
for(int i = 0; i < n; i++) {
cout << eile.getMin(1, i, i) << " ";
}
cout << ". Ieskosiu intervale [" << A+1 << "; " << n-1 << "] desiniausio, kad priesdelis butu didesnis uz " << maz << endl;
cout << "siaip fd = " << fd << ", bet man siulo " << siulo << endl << endl;
*/
// 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;
}
}*/
fd = min(A, eile.leftmost(1, 0, A-1, maz));
// 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
*/
Compilation message
cake.cpp: In function 'int find(int)':
cake.cpp:153:7: warning: unused variable 'l' [-Wunused-variable]
153 | int l = A+1; int r = n-1; int mid, fd = A;
| ^
cake.cpp:153:20: warning: unused variable 'r' [-Wunused-variable]
153 | int l = A+1; int r = n-1; int mid, fd = A;
| ^
cake.cpp:153:33: warning: unused variable 'mid' [-Wunused-variable]
153 | int l = A+1; int r = n-1; int mid, fd = A;
| ^~~
cake.cpp:177:7: warning: unused variable 'l' [-Wunused-variable]
177 | int l = 0; int r = A-1; int mid, fd = A;
| ^
cake.cpp:177:18: warning: unused variable 'r' [-Wunused-variable]
177 | int l = 0; int r = A-1; int mid, fd = A;
| ^
cake.cpp:177:31: warning: unused variable 'mid' [-Wunused-variable]
177 | int l = 0; int r = A-1; int mid, fd = A;
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
6100 KB |
Output is correct |
| 2 |
Correct |
5 ms |
6100 KB |
Output is correct |
| 3 |
Correct |
6 ms |
6212 KB |
Output is correct |
| 4 |
Correct |
12 ms |
6304 KB |
Output is correct |
| 5 |
Correct |
27 ms |
6728 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
746 ms |
6744 KB |
Output is correct |
| 2 |
Correct |
419 ms |
6788 KB |
Output is correct |
| 3 |
Correct |
526 ms |
6792 KB |
Output is correct |
| 4 |
Correct |
280 ms |
6792 KB |
Output is correct |
| 5 |
Correct |
815 ms |
7468 KB |
Output is correct |
| 6 |
Correct |
678 ms |
7508 KB |
Output is correct |
| 7 |
Correct |
540 ms |
7488 KB |
Output is correct |
| 8 |
Correct |
338 ms |
7508 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
162 ms |
11600 KB |
Output is correct |
| 2 |
Correct |
130 ms |
11468 KB |
Output is correct |
| 3 |
Correct |
110 ms |
11556 KB |
Output is correct |
| 4 |
Correct |
4 ms |
6100 KB |
Output is correct |
| 5 |
Correct |
299 ms |
18688 KB |
Output is correct |
| 6 |
Correct |
315 ms |
18692 KB |
Output is correct |
| 7 |
Correct |
203 ms |
18540 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
85 ms |
6556 KB |
Output is correct |
| 2 |
Correct |
58 ms |
6612 KB |
Output is correct |
| 3 |
Correct |
157 ms |
8840 KB |
Output is correct |
| 4 |
Correct |
167 ms |
8828 KB |
Output is correct |
| 5 |
Correct |
233 ms |
6868 KB |
Output is correct |
| 6 |
Correct |
296 ms |
9864 KB |
Output is correct |
| 7 |
Correct |
223 ms |
7244 KB |
Output is correct |
| 8 |
Correct |
377 ms |
11036 KB |
Output is correct |
| 9 |
Correct |
1645 ms |
20492 KB |
Output is correct |
| 10 |
Correct |
784 ms |
7720 KB |
Output is correct |
| 11 |
Correct |
960 ms |
8636 KB |
Output is correct |
| 12 |
Correct |
1528 ms |
18248 KB |
Output is correct |
| 13 |
Correct |
1116 ms |
19660 KB |
Output is correct |
