#include <bits/stdc++.h>
#define ll long long
#define ld long double
using namespace std;
const int N = 1e5+10;
const int INF = INT_MAX;
const int mod = 1e9+7;
int n,q,a[N];
int tree[4*N],lazy[4*N];
void build(int id = 1, int l = 1, int r = n) {
if(l == r) {
tree[id] = a[l];
return;
}
int mid = l + r >> 1;
build(id << 1,l,mid);
build(id << 1 | 1,mid+1,r);
tree[id] = max(tree[id << 1],tree[id << 1 | 1]);
}
void down(int id, int l, int r) {
int t = lazy[id];
tree[id] += t;
if(l < r) {
lazy[id << 1] += t;
lazy[id << 1 | 1] += t;
}
lazy[id] = 0;
}
void update(int u, int v, int val, int id = 1, int l = 1, int r = n) {
down(id,l,r);
if(l > r || u > v || r < u || v < l) {
return;
}
if(u <= l && r <= v) {
lazy[id] = val;
down(id,l,r);
return;
}
int mid = l + r >> 1;
update(u,v,val,id << 1,l,mid);
update(u,v,val,id << 1 | 1,mid+1,r);
tree[id] = max(tree[id << 1],tree[id << 1 | 1]);
}
int get(int u, int v, int id = 1, int l = 1, int r = n) {
down(id,l,r);
if(l > r || u > v || r < u || v < l) {
return 0;
}
if(u <= l && r <= v) {
return tree[id];
}
int mid = l + r >> 1;
return max(get(u,v,id << 1,l,mid),get(u,v,id << 1 | 1,mid+1,r));
}
int LOW(int x, int id = 1, int l = 1, int r = n) {
down(id,l,r);
if(tree[1] < x) {
return n+1;
}
if(l == r) {
return l;
}
int mid = l + r >> 1;
if(tree[id << 1] >= x) {
return LOW(x,id << 1,l,mid);
}
return LOW(x,id << 1 | 1,mid+1,r);
}
int UP(int x, int id = 1, int l = 1, int r = n) {
down(id,l,r);
if(tree[1] <= x) {
return n+1;
}
if(l == r) {
return l;
}
int mid = l + r >> 1;
if(tree[id << 1] > x) {
return UP(x,id << 1,l,mid);
}
return UP(x,id << 1 | 1,mid+1,r);
}
signed main()
{
if (fopen("solve.inp", "r")) {
freopen("solve.inp", "r", stdin);
freopen("solve.out", "w", stdout);
}
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n >> q;
for(int i = 1 ; i <= n ; i++) {
cin >> a[i];
}
sort(a+1,a+n+1);
build();
// for(int i = 1 ; i <= n ; i++) {
// cout << a[i] << " ";
// }
// cout << '\n';
while(q--) {
char c; cin >> c;
int x,y; cin >> x >> y;
if(c == 'F') {
int l = LOW(y);
if(l+x-1 >= n) {
update(l,n,1);
continue;
}
int tmp = get(l+x-1,l+x-1);
int r = UP(tmp)-1;
tmp = LOW(tmp);
x -= tmp-l;
update(l,tmp-1,1);
update(r-x+1,r,1);
}
else {
cout << UP(y) - LOW(x) << '\n';
}
}
return 0;
}
Compilation message
grow.cpp: In function 'void build(int, int, int)':
grow.cpp:19:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
19 | int mid = l + r >> 1;
| ~~^~~
grow.cpp: In function 'void update(int, int, int, int, int, int)':
grow.cpp:45:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
45 | int mid = l + r >> 1;
| ~~^~~
grow.cpp: In function 'int get(int, int, int, int, int)':
grow.cpp:59:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
59 | int mid = l + r >> 1;
| ~~^~~
grow.cpp: In function 'int LOW(int, int, int, int)':
grow.cpp:71:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
71 | int mid = l + r >> 1;
| ~~^~~
grow.cpp: In function 'int UP(int, int, int, int)':
grow.cpp:86:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
86 | int mid = l + r >> 1;
| ~~^~~
grow.cpp: In function 'int main()':
grow.cpp:96:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
96 | freopen("solve.inp", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
grow.cpp:97:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
97 | freopen("solve.out", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
26 ms |
3420 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 |
29 ms |
2648 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
21 ms |
2712 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
23 ms |
2972 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
51 ms |
3388 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
49 ms |
3428 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
81 ms |
3488 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
30 ms |
3496 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
50 ms |
3812 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
