///***LTT***///
/// ->TUYEN QUOC GIA<- ///
#include<bits/stdc++.h>
//#pragma GCC optimize ("O3")
//#pragma GCC optimize ("unroll-loops")
//#pragma GCC target("popcnt")
//#define int long long
#define endl "\n"
#define F first
#define S second
#define pb push_back
#define CHECKBIT(mask,i) ((mask>>(i) )&1) // == 1 la bat, == 0 la tat
#define OFFBIT(mask,i) ((1<<(i))^mask) // tat bit thu i
#define ONBIT(mask,i) ((1<<(i))mask) // bat bit thu i
using namespace std;
const long long oo = 1e9+7;
const int N = 1e5 + 10;
pair <int, int> tree[N * 4];
int lazy[N * 4];
int a[N], n, q;
char type;
void build(int id,int l,int r){
if (l == r){
tree[id].F = a[l];
tree[id].S = a[l];
return;
}
int mid = (l + r)/2;
build(id*2,l,mid);
build(id*2 + 1,mid + 1,r);
tree[id].F = max(tree[id * 2].F, tree[id * 2 + 1].F);
tree[id].S = min(tree[id * 2].S, tree[id * 2 + 1].S);
return;
}
void down(int id,int l,int r){
if (l != r){
tree[id*2].F += lazy[id];
tree[id*2 + 1].F += lazy[id];
tree[id*2 + 1].S += lazy[id];
tree[id*2 ].S += lazy[id];
lazy[id*2] += lazy[id];
lazy[id*2 + 1] += lazy[id];
}
lazy[id] = 0;
}
int cnpl(int id,int l,int r,int k){
if (lazy[id]){
down(id,l,r);
}
if (l == r){
if (tree[id].F < k) return n + 1;
return r;
}
int mid = (l + r)/2;
if (tree[id * 2].F >= k) return cnpl(id * 2,l,mid,k);
return cnpl(id * 2 + 1,mid + 1,r,k);
}
int cnpr(int id,int l,int r,int k){
if (lazy[id]){
down(id,l,r);
}
if (l == r){
if (tree[l].F > k) return 0;
return r;
}
int mid = (l + r)/2;
if (tree[id * 2 + 1].S <= k) return cnpr(id * 2 + 1,mid + 1,r,k);
return cnpr(id * 2 ,l,mid ,k);
}
void update(int id,int l,int r,int u,int v){
if (lazy[id]){
down(id,l,r);
}
if (l > v or r < u) return;
if (l >= u and r <= v){
tree[id].F++;
tree[id].S++;
lazy[id]++;
return;
}
int mid = (l + r)/2;
update(id * 2,l,mid,u,v);
update(id * 2 + 1,mid + 1,r,u,v);
tree[id].F = max(tree[id * 2].F, tree[id * 2 + 1].F);
tree[id].S = min(tree[id * 2].S, tree[id * 2 + 1].S);
return;
}
int get(int id,int l,int r,int u){
if (lazy[id]){
down(id,l,r);
}
if (l > u or r < u) return 0;
if (l == u and r == u){
return tree[id].F;
}
int mid = (l + r)/2;
return max(get(id*2,l,mid,u), get(id*2+1,mid+1,r,u));
}
void inp(){
cin >> n >> q;
for (int i = 1;i <= n;i++){
cin >> a[i];
}
return;
}
void solve(){
sort(a + 1, a + n + 1);
build(1,1,n);
for (int i = 1;i <= q;i++){
cin >> type;
if (type == 'F'){
int h, c;
cin >> c >> h;
int l = cnpl(1,1,n,h);
int nxt = 0;
if (l + c - 1< n){
int val = get(1,1,n,l + c - 1);
nxt = cnpl(1,1,n,val);
if (nxt - 1 >= l)
update(1,1,n,l, nxt - 1);
int sl = (l + c - 1) - nxt + 1;
if (get(1,1,n,l + c) == val){
int r = cnpr(1,1,n,val);
update(1,1,n,r - sl + 1, r);
} else update(1,1,n,nxt,nxt + ((l + c - 1) - nxt));
} else update(1,1,n,l, min(n, l + c - 1));
} else {
int l, r;
cin >> l >> r;
r = cnpr(1,1,n,r);
l = cnpl(1,1,n,l);
cout << r - l + 1 <<"\n";
}
}
return;
}
int main(){
ios_base::sync_with_stdio(NULL);
cin.tie(NULL);
cout.tie(NULL);
if (fopen("file.inp", "r")){
freopen("file.inp", "r", stdin);
freopen("file.out", "w", stdout);
}
//int t;
//cin >> t;
//while(t--){
inp();
solve();
//}
}
Compilation message
grow.cpp: In function 'int main()':
grow.cpp:143:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
143 | freopen("file.inp", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
grow.cpp:144:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
144 | freopen("file.out", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
39 ms |
4696 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2392 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
27 ms |
2816 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
27 ms |
2648 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
50 ms |
4696 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
63 ms |
4944 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
49 ms |
4788 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
91 ms |
4696 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
66 ms |
4696 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
57 ms |
5200 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
