#include <bits/stdc++.h>
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
using namespace std;
const int Nmax = 1e5 + 10;
int n, q;
int a[Nmax];
struct node {
int minval, maxval;
int lazy;
} st[Nmax * 4];
void push(int id, int lazy) {
st[id].lazy += lazy;
st[id].minval += lazy;
st[id].maxval += lazy;
}
void add(int id, int L, int R, int u, int v, int val) {
if (u > R || L > v) return;
if (u <= L && R <= v) {
push(id, val);
return;
}
push(id * 2, st[id].lazy);
push(id * 2 + 1, st[id].lazy);
st[id].lazy = 0;
int mid = L + R >> 1;
add(id * 2, L, mid, u, v, val);
add(id * 2 + 1, mid + 1, R, u, v, val);
st[id].maxval = max(st[id * 2].maxval, st[id * 2 + 1].maxval);
st[id].minval = min(st[id * 2].minval, st[id * 2 + 1].minval);
}
int get_prf(int id, int L, int R, int val) {
if (st[id].maxval < val) return n + 1;
if (L == R) return L;
int mid = L + R >> 1;
push(id * 2, st[id].lazy);
push(id * 2 + 1, st[id].lazy);
st[id].lazy = 0;
if (st[id * 2].maxval < val) return get_prf(id * 2 + 1, mid + 1, R, val);
else return get_prf(id * 2, L, mid, val);
}
int get_suf(int id, int L, int R, int val) {
if (st[id].minval > val) return 0;
if (L == R) return L;
int mid = L + R >> 1;
push(id * 2, st[id].lazy);
push(id * 2 + 1, st[id].lazy);
st[id].lazy = 0;
if (st[id * 2 + 1].maxval <= val) return get_suf(id * 2 + 1, mid + 1, R, val);
else return get_suf(id * 2, L, mid, val);
}
int get(int id, int L, int R, int i) {
if (L == R) return st[id].minval;
int mid = L + R >> 1;
push(id * 2, st[id].lazy);
push(id * 2 + 1, st[id].lazy);
st[id].lazy = 0;
if (i <= mid) return get(id * 2, L, mid, i);
else return get(id * 2 + 1, mid + 1, R, i);
}
int main() {
ios :: 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);
for (int i = 1; i <= n; ++i) add(1, 1, n, i, i, a[i]);
while (q--) {
char type;
cin >> type;
if (type == 'C') {
int L, R;
cin >> L >> R;
L = get_prf(1, 1, n, L);
R = get_suf(1, 1, n, R);
cout << R - L + 1 << '\n';
} else {
int c, h;
cin >> c >> h;
if (h > st[1].maxval) continue;
int L = get_prf(1, 1, n, h);
c = min(c, n - L + 1);
int val = get(1, 1, n, L + c - 1);
int R = get_suf(1, 1, n, val);
int smaller = get_prf(1, 1, n, val) - 1;
int nequal = L + c - 1 - smaller;
add(1, 1, n, L, smaller, 1);
add(1, 1, n, R - nequal + 1, R, 1);
}
}
}
Compilation message
grow.cpp:3: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
3 | #pragma GCC optimization ("O3")
|
grow.cpp:4: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
4 | #pragma GCC optimization ("unroll-loops")
|
grow.cpp: In function 'void add(int, int, int, int, int, int)':
grow.cpp:33:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
33 | int mid = L + R >> 1;
| ~~^~~
grow.cpp: In function 'int get_prf(int, int, int, int)':
grow.cpp:43:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
43 | int mid = L + R >> 1;
| ~~^~~
grow.cpp: In function 'int get_suf(int, int, int, int)':
grow.cpp:54:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
54 | int mid = L + R >> 1;
| ~~^~~
grow.cpp: In function 'int get(int, int, int, int)':
grow.cpp:64:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
64 | int mid = L + R >> 1;
| ~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
48 ms |
4932 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
32 ms |
1852 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
26 ms |
1804 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
62 ms |
3296 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
64 ms |
4840 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
75 ms |
4888 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
102 ms |
5572 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
62 ms |
5172 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
83 ms |
6028 KB |
Output isn't correct |
