#include <bits/stdc++.h>
#define va first
#define vb second
#define lb lower_bound
#define ub upper_bound
#define bs binary_search
#define pp push_back
#define ep emplace_back
#define all(v) (v).begin(),(v).end()
#define szz(v) ((int)(v).size())
#define bi_pc __builtin_popcount
#define bi_pcll __builtin_popcountll
#define bi_tz __builtin_ctz
#define bi_tzll __builtin_ctzll
#define fio ios_base::sync_with_stdio(0);cin.tie(0);
#ifdef TAMREF
#define debug(...) fprintf(stderr, __VA_ARGS__)
#else
#define debug(...) 42
#endif
using namespace std;
using ll = long long; using lf = long double;
using pii = pair<int,int>; using ppi = pair<int,pii>;
using pll = pair<ll,ll>; using pff = pair<lf,lf>;
using ti = tuple<int,int,int>;
using base = complex<double>;
const lf PI = 3.14159265358979323846264338L;
template <typename T>
inline T umax(T& u, T v){return u = max(u, v);}
template <typename T>
inline T umin(T& u, T v){return u = min(u, v);}
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
struct seg{
int laz[270005], mn[270005], mx[270005];
void init(int i, int s, int e, int *a){
if(s == e){
mn[i] = mx[i] = a[s];
return;
}
int m = s + e >> 1;
init(2*i, s, m, a);
init(2*i+1, m+1, e, a);
mn[i] = mn[2*i];
mx[i] = mx[2*i+1];
}
void upd(int i, int s, int e, int l, int r, int v){
if(i == 1){
debug("upd %d %d %d\n",l,r,v);
}
if(r < s || l > e) return;
if(l <= s && e <= r){
laz[i] += v;
mn[i] += v;
mx[i] += v;
return;
}
int m = s + e >> 1;
mn[2*i] += laz[i]; mx[2*i] += laz[i]; laz[2*i] += laz[i];
mn[2*i+1] += laz[i]; mx[2*i+1] += laz[i]; laz[2*i+1] += laz[i];
laz[i] = 0;
upd(2*i, s, m, l, r, v);
upd(2*i+1, m+1, e, l, r, v);
mn[i] = mn[2*i];
mx[i] = mx[2*i+1];
}
int lowerbound(int i, int s, int e, int x){
if(s == e){
if(mn[i] >= x) return s;
else return s + 1;
}
int m = s + e >> 1;
if(mx[2*i] >= x) return lowerbound(2*i, s, m, x);
else return lowerbound(2*i+1, m+1, e, x);
}
int get(int i, int s, int e, int j){
if(s == e) return mn[i];
int m = s + e >> 1;
int v = -1;
if(j <= m) v = get(2*i, s, m, j);
else v = get(2*i+1, m+1, e, j);
return v + laz[i];
}
int stat(int i, int s, int e, int l, int r){
if(mx[i] < l || mn[i] > r) return 0;
if(l <= mn[i] && mx[i] <= r){
return e - s + 1;
}
int m = s + e >> 1;
int lv = stat(2*i, s, m, l - laz[i], r - laz[i]);
int rv = stat(2*i+1, m+1, e, l - laz[i], r - laz[i]);
return lv + rv;
}
} S;
int n, q, a[100005];
int main(){
#ifndef TAMREF
fio;
#endif
cin >> n >> q;
for(int i = 1; i <= n; i++) cin >> a[i];
sort(a + 1, a + n + 1);
S.init(1, 1, n, a);
debug("init\n");
char ty;
for(int l, r, c, h; q--;){
debug("query %d\n",q);
cin >> ty;
assert(ty == 'F' || ty == 'C');
if(ty == 'F'){
cin >> c >> h;
int u = S.lowerbound(1, 1, n, h);
debug("u = %d\n",u);
if(u + c > n){
S.upd(1, 1, n, u, n, 1);
continue;
}
int w = S.get(1, 1, n, u + c - 1);
debug("w = %d\n",w);
int x = S.lowerbound(1, 1, n, w),
y = S.lowerbound(1, 1, n, w+1);
debug("x = %d, y = %d\n",x,y);
int d = c - (x - u);
S.upd(1, 1, n, u, x-1, 1);
S.upd(1, 1, n, y-d, y-1, 1);
}else{
cin >> l >> r;
cout << S.stat(1, 1, n, l, r) << '\n';
}
for(int i = 1; i <= n; i++) debug("%d ",S.get(1, 1, n, i)); debug("\n");
}
}
Compilation message
grow.cpp: In member function 'void seg::init(int, int, int, int*)':
grow.cpp:41:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
41 | int m = s + e >> 1;
| ~~^~~
grow.cpp: In member function 'void seg::upd(int, int, int, int, int, int)':
grow.cpp:19:20: warning: statement has no effect [-Wunused-value]
19 | #define debug(...) 42
| ^~
grow.cpp:49:13: note: in expansion of macro 'debug'
49 | debug("upd %d %d %d\n",l,r,v);
| ^~~~~
grow.cpp:58:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
58 | int m = s + e >> 1;
| ~~^~~
grow.cpp: In member function 'int seg::lowerbound(int, int, int, int)':
grow.cpp:72:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
72 | int m = s + e >> 1;
| ~~^~~
grow.cpp: In member function 'int seg::get(int, int, int, int)':
grow.cpp:78:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
78 | int m = s + e >> 1;
| ~~^~~
grow.cpp: In member function 'int seg::stat(int, int, int, int, int)':
grow.cpp:89:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
89 | int m = s + e >> 1;
| ~~^~~
grow.cpp: In function 'int main()':
grow.cpp:19:20: warning: statement has no effect [-Wunused-value]
19 | #define debug(...) 42
| ^~
grow.cpp:106:5: note: in expansion of macro 'debug'
106 | debug("init\n");
| ^~~~~
grow.cpp:19:20: warning: statement has no effect [-Wunused-value]
19 | #define debug(...) 42
| ^~
grow.cpp:109:9: note: in expansion of macro 'debug'
109 | debug("query %d\n",q);
| ^~~~~
grow.cpp:19:20: warning: statement has no effect [-Wunused-value]
19 | #define debug(...) 42
| ^~
grow.cpp:115:13: note: in expansion of macro 'debug'
115 | debug("u = %d\n",u);
| ^~~~~
grow.cpp:19:20: warning: statement has no effect [-Wunused-value]
19 | #define debug(...) 42
| ^~
grow.cpp:121:13: note: in expansion of macro 'debug'
121 | debug("w = %d\n",w);
| ^~~~~
grow.cpp:19:20: warning: statement has no effect [-Wunused-value]
19 | #define debug(...) 42
| ^~
grow.cpp:124:13: note: in expansion of macro 'debug'
124 | debug("x = %d, y = %d\n",x,y);
| ^~~~~
grow.cpp:19:20: warning: statement has no effect [-Wunused-value]
19 | #define debug(...) 42
| ^~
grow.cpp:132:37: note: in expansion of macro 'debug'
132 | for(int i = 1; i <= n; i++) debug("%d ",S.get(1, 1, n, i)); debug("\n");
| ^~~~~
grow.cpp:19:20: warning: statement has no effect [-Wunused-value]
19 | #define debug(...) 42
| ^~
grow.cpp:132:69: note: in expansion of macro 'debug'
132 | for(int i = 1; i <= n; i++) debug("%d ",S.get(1, 1, n, i)); debug("\n");
| ^~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
41 ms |
3948 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
492 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
35 ms |
1124 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
30 ms |
1132 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
59 ms |
2668 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
60 ms |
3948 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
40 ms |
3692 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
100 ms |
4196 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
52 ms |
4196 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
92 ms |
4708 KB |
Output isn't correct |
