#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 1e5 + 5;
int n, m;
int a[maxn];
struct Seg
{
int tree[4*maxn];
int lazy[4*maxn];
void build(int id, int l, int r)
{
if(l == r){
tree[id] = a[l];
return;
}
int mid = l + r >> 1;
build(id*2, l, mid);
build(id*2+1, mid+1, r);
tree[id] = max(tree[id*2], tree[id*2+1]);
}
void down(int id, int l, int r)
{
if(lazy[id] == 0)
return;
tree[id] += lazy[id];
if(l != r){
lazy[id*2] += lazy[id];
lazy[id*2+1] += lazy[id];
}
lazy[id] = 0;
}
void update(int id, int l, int r, int u, int v, int val)
{
down(id, l, r);
if(r < u || v < l)
return;
if(u <= l && r <= v){
lazy[id] = val;
down(id, l, r);
return;
}
int mid = l + r >> 1;
update(id*2, l, mid, u, v, val);
update(id*2+1, mid+1, r, u, v, val);
tree[id] = max(tree[id*2], tree[id*2+1]);
}
int get_max(int id, int l, int r, int u, int v)
{
down(id, l, r);
if(r < u || v < l){
return -1;
}
if(u <= l && r <= v){
return tree[id];
}
int mid = l + r >> 1;
int val_1 = get_max(id*2, l, mid, u, v);
int val_2 = get_max(id*2+1, mid+1, r, u, v);
return max(val_1, val_2);
}
int Find_min(int id, int l, int r, int val)
{
down(id, l, r);
if(l == r){
if(tree[id] >= val){
return l;
}
return -1;
}
int mid = l + r >> 1;
int id_1 = Find_min(id*2, l, mid, val);
if(id_1 != -1){
return id_1;
}
else{
return Find_min(id*2+1, mid+1, r, val);
}
}
int Find_max(int id, int l, int r, int val)
{
down(id, l, r);
if(l == r){
if(tree[id] <= val){
return l;
}
return -1;
}
int mid = l + r >> 1;
int id_1 = Find_max(id*2+1, mid+1, r, val);
if(id_1 != -1){
return id_1;
}
else{
return Find_max(id*2, l, mid, val);
}
}
}ST;
signed main()
{
// freopen("D.inp", "r", stdin);
// freopen("D.out", "w", stdout);
ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin >> n >> m;
for(int i=1 ; i<=n ; ++i){
cin >> a[i];
}
sort(a+1, a+1+n);
ST.build(1, 1, n);
for(int i=1 ; i<=m ; ++i){
char type;
int l, r;
cin >> type >> l >> r;
if (type == 'F') {
int pos = ST.Find_min(1, 1, n, r);
// cout << pos << endl;
if (pos == -1) continue;
if (pos + l - 1 >= n) {
ST.update(1, 1, n, pos, n, 1);
continue;
}
int val = ST.get_max(1, 1, n, pos, pos + l - 1);
int last = ST.Find_min(1, 1, n, val);
int nxt = ST.Find_max(1, 1, n, val);
int len = last - pos;
// cout << val << ' ' << last << ' ' << nxt << ' ' << len << endl;
ST.update(1, 1, n, pos, last - 1, 1);
ST.update(1, 1, n, nxt - (l - len) + 1, nxt, 1);
}
else {
int pos = ST.Find_min(1, 1, n, l);
int last = ST.Find_max(1, 1, n, r);
if (pos == -1 || last == -1)
cout << 0 << '\n';
else
cout << last - pos + 1 << '\n';
}
}
}
/// code by yourlove ///
Compilation message
grow.cpp: In member function 'void Seg::build(long long int, long long int, long long int)':
grow.cpp:22:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
22 | int mid = l + r >> 1;
| ~~^~~
grow.cpp: In member function 'void Seg::update(long long int, long long int, long long int, long long int, long long int, long long int)':
grow.cpp:52:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
52 | int mid = l + r >> 1;
| ~~^~~
grow.cpp: In member function 'long long int Seg::get_max(long long int, long long int, long long int, long long int, long long int)':
grow.cpp:68:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
68 | int mid = l + r >> 1;
| ~~^~~
grow.cpp: In member function 'long long int Seg::Find_min(long long int, long long int, long long int, long long int)':
grow.cpp:84:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
84 | int mid = l + r >> 1;
| ~~^~~
grow.cpp: In member function 'long long int Seg::Find_max(long long int, long long int, long long int, long long int)':
grow.cpp:103:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
103 | int mid = l + r >> 1;
| ~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1036 ms |
6496 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
2396 KB |
Output is correct |
| 2 |
Correct |
20 ms |
2588 KB |
Output is correct |
| 3 |
Correct |
12 ms |
2396 KB |
Output is correct |
| 4 |
Correct |
8 ms |
2396 KB |
Output is correct |
| 5 |
Execution timed out |
1094 ms |
3280 KB |
Time limit exceeded |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1054 ms |
2976 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
863 ms |
3304 KB |
Output is correct |
| 2 |
Execution timed out |
1080 ms |
3156 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1065 ms |
6440 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1057 ms |
6312 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1026 ms |
6480 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1062 ms |
6484 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1028 ms |
6488 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1045 ms |
6692 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
