#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
typedef long long ll;
typedef pair<long long, long long> pll;
typedef pair<int,int> pii;
typedef vector<long long> vl;
typedef vector<int> vi;
int n, q;
vi arr;
int ma[4 * 100100], mi[4 * 100100], lazy[4 * 100100];
void build(int node, int l, int r){
if(l == r){
ma[node] = mi[node] = arr[l];
}
else{
int mid = (l + r) / 2;
build(node*2, l, mid);
build(node*2+1, mid+1, r);
ma[node] = max(ma[node*2], ma[node*2+1]);
mi[node] = min(mi[node*2], mi[node*2+1]);
}
}
void push_lazy(int node){
ma[node*2] += lazy[node];
ma[node*2+1] += lazy[node];
mi[node*2] += lazy[node];
mi[node*2+1] += lazy[node];
lazy[node*2] += lazy[node];
lazy[node*2+1] += lazy[node];
lazy[node] = 0;
}
void update(int node, int l, int r, int L, int R){
if(l > R || r < L) return;
if(L <= l && r <= R){
ma[node]++;
mi[node]++;
lazy[node]++;
return;
}
push_lazy(node);
int mid = (l + r) / 2;
update(node*2, l, mid, L, R);
update(node*2+1, mid+1, r, L, R);
ma[node] = max(ma[node*2], ma[node*2+1]);
mi[node] = max(mi[node*2], mi[node*2+1]);
}
ll getFirst(int id, int l, int r, int x) {
if (l == r) return ma[id] >= x ? l : l + 1;
int u = id << 1, v = id << 1 | 1, mid = l + r >> 1;
push_lazy(id);
if (ma[u] >= x) return getFirst(u, l, mid, x);
return getFirst(v, mid + 1, r, x);
}
ll getLast(int id, int l, int r, int x) {
if (l == r) return mi[id] <= x ? l : l - 1;
int u = id << 1, v = id << 1 | 1, mid = l + r >> 1;
push_lazy(id);
if (mi[v] <= x) return getLast(v, mid + 1, r, x);
return getLast(u, l, mid, x);
}
ll getPos(int id, int l, int r, int i) {
if (l == r) return ma[id];
push_lazy(id);
int mid = l + r >> 1;
if (mid >= i) return getPos(id << 1, l, mid, i);
return getPos(id << 1 | 1, mid + 1, r, i);
}
void queries(int C = 0, int H = 0) {
if (getPos(1, 0, n-1, n) < H) return;
int L = getFirst(1, 0, n-1, H);
if (L + C - 1 > n) {
update(1, 0, n-1, L, n);
return;
}
int val = getPos(1, 0, n-1, L + C - 1);
int R = getLast(1, 0, n-1, val);
int r = L - 1;
if (getPos(1, 1, n, L) < val) r = getLast(1, 0, n-1, val - 1);
if (r >= L) update(1, 0, n-1, L, r);
int len = r - L + 1;
update(1, 0, n-1, R - (C - len) + 1, R);
}
void answer(int L, int R) {
cout << getLast(1, 1, n, R) - getFirst(1, 1, n, L) + 1 << '\n';
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n>>q;
arr.resize(n);
for(int i = 0; i < n; i++) cin>>arr[i];
memset(lazy, 0, sizeof lazy);
sort(arr.begin(), arr.end());
build(1, 0, n-1);
char t;
int l, r;
for(int i = 0; i < q; i++){
cin>>t>>l>>r;
if(t == 'F') queries(l, r);
else answer(l, r);
}
return 0;
return 0;
}
Compilation message
grow.cpp: In function 'll getFirst(int, int, int, int)':
grow.cpp:51:47: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
51 | int u = id << 1, v = id << 1 | 1, mid = l + r >> 1;
| ~~^~~
grow.cpp: In function 'll getLast(int, int, int, int)':
grow.cpp:61:47: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
61 | int u = id << 1, v = id << 1 | 1, mid = l + r >> 1;
| ~~^~~
grow.cpp: In function 'll getPos(int, int, int, int)':
grow.cpp:72:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
72 | int mid = l + r >> 1;
| ~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
41 ms |
5476 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
1880 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
32 ms |
3276 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
32 ms |
3260 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
49 ms |
4260 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
53 ms |
5268 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
52 ms |
5584 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
101 ms |
6100 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
52 ms |
5580 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
69 ms |
6584 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
