#include "bits/stdc++.h"
using namespace std;
const int maxn = 200005;
int a[maxn], t[maxn], lazy[maxn];
int n, m;
void build(int node, int b, int e){
if(b == e){
t[node] = a[b];
return;
}int mid = (b + e)>>1;
build(2*node, b, mid);
build(2*node + 1, mid + 1, e);
t[node] = t[2*node] + t[2*node + 1];
}
void upd(int node, int b, int e, int i, int j){
if(lazy[node] != 0){
t[node] += (e - b + 1) * lazy[node];
if(b != e){
lazy[2*node] += lazy[node];
lazy[2*node + 1] += lazy[node];
}lazy[node] = 0;
}
if(i > e || j < b)return;
if(b >= i && j >= e){
t[node] += (e - b + 1);
if(b != e){
lazy[2*node]++;
lazy[2*node + 1]++;
}return;
}int mid = (b + e)>>1;
upd(2*node, b, mid, i, j);
upd(2*node + 1, mid + 1, e, i, j);
t[node] = t[2*node] + t[2*node + 1];
}
int query(int node, int b, int e, int i, int j){
if(lazy[node] != 0){
t[node] += (e - b + 1) * lazy[node];
if(b != e){
lazy[2*node] += lazy[node];
lazy[2*node + 1] += lazy[node];
}lazy[node] = 0;
}
if(i > e || j < b)return 0;
if(b >= i && j >= e)return t[node];
int mid = (b + e)>>1;
return query(2*node, b, mid, i, j) + query(2*node + 1, mid + 1, e, i, j);
}
int query(int i, int j){
if(i > j)return 0;
return query(1, 1, n, i, j);
}
void upd(int i, int j){
if(i > j)return;
upd(1, 1, n, i, j);
}
int get_lowest(int h){
int lo = 1, hi = n;
while(lo <= hi){
int mid = (lo + hi)>>1;
if(query(mid, mid) >= h){
hi = mid - 1;
}else {
lo = mid + 1;
}
}
return lo;
}
int get_highest(int h){
int lo = 1, hi = n, pos = n + 1;
while(lo <= hi){
int mid = (lo + hi)>>1;
if(query(mid, mid) <= h){
lo = mid + 1;
}else {
hi = mid - 1;
}
}
return lo - 1;
}
int main(int argc, char const *argv[])
{
// freopen("in.txt", "r", stdin);
scanf("%d %d", &n, &m);
for(int i = 1; i <= n; i++){
scanf("%d", &a[i]);
}
sort(a + 1, a + n + 1);
build(1, 1, n);
while(m--){
char s[2];
scanf("%s", s);
if(s[0] == 'F'){
int c, h;
scanf("%d %d", &c, &h);
if(query(n, n) < h)continue;
int ff = get_lowest(h);
int ss = -1;
if(ff + c - 1 > n){
ss = a[n];
}else {
ss = a[ff + c - 1];
}
int ll = get_highest(ss - 1);
if(ll >= ff){
upd(ff, ll);
c -= (ll - ff + 1);
}
ll = get_highest(ss);
upd(ll - c + 1, ll);
}else {
int lo, hi;
scanf("%d %d", &lo, &hi);
if(lo > query(n, n) || query(1, 1) > hi){
printf("0\n");
continue;
}
lo = get_lowest(lo);
hi = get_highest(hi);
printf("%d\n", hi - lo + 1);
}
}
return 0;
}
Compilation message
grow.cpp: In function 'int get_highest(int)':
grow.cpp:77:25: warning: unused variable 'pos' [-Wunused-variable]
int lo = 1, hi = n, pos = n + 1;
^~~
grow.cpp: In function 'int main(int, const char**)':
grow.cpp:92:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &n, &m);
~~~~~^~~~~~~~~~~~~~~~~
grow.cpp:94:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &a[i]);
~~~~~^~~~~~~~~~~~~
grow.cpp:101:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%s", s);
~~~~~^~~~~~~~~
grow.cpp:104:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &c, &h);
~~~~~^~~~~~~~~~~~~~~~~
grow.cpp:122:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &lo, &hi);
~~~~~^~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
135 ms |
2424 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
117 ms |
632 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
54 ms |
632 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
121 ms |
1656 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
186 ms |
2268 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
63 ms |
2088 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
835 ms |
2600 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
242 ms |
2400 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
646 ms |
3008 KB |
Output isn't correct |
