#define COPYRIGHT CODE BY TRINH TUAN NGHIA
#include<bits/stdc++.h>
#define Boost ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("popcnt")
#define ll long long
#define endl "\n"
#define st first
#define nd second
#define ii pair <ll,ll>
#define iii pair <ll,ii>
#define iiii pair <ii,ii>
#define pb push_back
#define NAME "growingtrees"
using namespace std;
const ll N = 1e5 + 10;
ll a[N];
ll tree[4 * N];
ll lazy[4 * N];
ll n, m;
void buildTree(ll id, ll l, ll r){
if (l == r){
tree[id] = a[l];
return;
}
ll m = (l + r) >> 1;
buildTree(id * 2 , l, m);
buildTree(id * 2 + 1, m + 1, r);
tree[id] = max(tree[id * 2], tree[id * 2 + 1]);
}
void down(ll id, ll l, ll r){
ll m = (l + r) >> 1;
if (l < r){
tree[id * 2] += lazy[id];
tree[id * 2 + 1] += lazy[id];
lazy[id * 2] += lazy[id];
lazy[id * 2+ 1] += lazy[id];
}
lazy[id] = 0;
}
void update(ll id, ll l, ll r, ll u, ll v, ll val){
if (v < l or r < u)return ;
if (u <= l and r <= v){
tree[id] += val;
lazy[id] += val;
return;
}
down(id , l, r);
ll m = (l + r) >> 1;
update(id * 2, l, m, u, v, val);
update(id * 2 + 1, m + 1, r, u, v, val);
tree[id] = max(tree[id * 2], tree[id * 2 + 1]);
}
ll getmax(ll id, ll l, ll r, ll u, ll v){
if (v < l or r < u)return 0;;
if (u <= l and r <= v){
return tree[id];
}
down(id,l,r);
ll m = (l + r) >> 1;
return max(getmax(id *2 , l ,m, u , v), getmax(id * 2 + 1, m + 1, r, u, v));
}
ll tknp(ll id, ll l, ll r, ll x){
ll m = (l +r ) >> 1;
if (tree[id] < x)return n + 1;
if (l == r)return l;
down(id , l, r);
if (tree[id * 2] >= x)return tknp(id * 2, l ,m, x);
else return tknp(id * 2 + 1, m + 1, r,x);
}
void inp (){
cin >> n >> m;
for (int i = 1; i <= n; ++i){
cin >> a[i];
}
sort(a + 1, a + n + 1);
//a[n + 1] = 1e18;
}
void solve(){
buildTree(1,1,n);
while (m -- ){
char type;
ll c,h, can1, can2;
cin >> type;
if (type == 'F'){
cin >> c >> h;
ll chot1 = tknp(1,1,n,h);
ll cnt = 0;
ll maxx = getmax(1,1,n,chot1 + c - 1, chot1 + c - 1);
ll chot2;
// if (maxx == getmax(1,1,n,n,n)) chot2 = n;
// else chot2 = tknp(1,1,n, maxx + 1) - 1;
chot2 = tknp(1,1,n,maxx + 1) - 1;
ll chotmax = tknp(1,1,n,maxx);
update(1,1,n,chot1, chotmax - 1, 1);
cnt = chotmax - 1 - chot1 + 1;
cnt = c - cnt;
update(1,1,n,chot2 - cnt + 1, chot2, 1);
// cout << chot1<< endl;
// cout << chotmax<< endl;
// cout <<chot2 << endl;
// cout << getmax(1,1,n,10,10);
//cout << "dcm " << getmax(1,1,n,3,3)<< endl;
}
else {
cin >> can1 >> can2;
ll chot1 = tknp(1,1,n,can1);
ll chot2;
chot2 = tknp(1,1,n,can2 + 1) - 1;
//cout << "dcm " << endl;
// for (int i = 1; i <= n; ++i){
// cout << getmax(1,1,n,i,i) << " ";
// }
//cout << endl;
// cout << chot1 << " " << chot2 << " " << chot2 - chot1 + 1 << endl;
cout << chot2 - chot1 + 1 << endl;
}
}
}
signed main (){
if (fopen(NAME".inp", "r")){
freopen(NAME".inp", "r", stdin);
freopen(NAME".out", "w", stdout);
}
Boost;
inp();
solve();
}
/*
input
*/
/*
output
*/
Compilation message
grow.cpp: In function 'void down(long long int, long long int, long long int)':
grow.cpp:33:8: warning: unused variable 'm' [-Wunused-variable]
33 | ll m = (l + r) >> 1;
| ^
grow.cpp: In function 'int main()':
grow.cpp:126:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
126 | freopen(NAME".inp", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
grow.cpp:127:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
127 | freopen(NAME".out", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
33 ms |
7260 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 2 |
Correct |
2 ms |
4612 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
4444 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
27 ms |
4916 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
18 ms |
4700 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
43 ms |
7308 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
34 ms |
7324 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
44 ms |
7256 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
78 ms |
7508 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
54 ms |
7260 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
51 ms |
7764 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
