#include<bits/stdc++.h>
#define TASKNAME "codeforce"
#define pb push_back
#define pli pair<int,int>
#define fi first
#define se second
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL);
using namespace std;
using ll=long long;
const ll maxN=2e5;
const ll inf=1e18;
const ll mod=1e9+7;
ll n,c[maxN],st[4*maxN],mn[4*maxN];
void build(ll id=1,ll l=1,ll r=n)
{
if(l==r)
{
st[id]=c[l];
mn[id]=c[l];
return;
}
ll mid=l+r>>1;
build(id*2,l,mid);
build(id*2+1,mid+1,r);
st[id]=max(st[id],st[id*2+1]);
mn[id]=min(mn[id*2],mn[id*2+1]);
}
ll lazy[4*maxN];
void down(ll id)
{
ll &x=lazy[id];
st[id*2]+=x;
mn[id*2]+=x;
lazy[id*2]+=x;
st[id*2+1]+=x;
mn[id*2+1]+=x;
lazy[id*2+1]+=x;
x=0;
}
void update(ll i,ll j,ll val,ll id=1,ll l=1,ll r=n)
{
if(j<l||r<i) return;
if(i<=l&&r<=j)
{
st[id]+=val;
mn[id]+=val;
lazy[id]+=val;
return;
}
down(id);
ll mid=l+r>>1;
update(i,j,val,id*2,l,mid);
update(i,j,val,id*2+1,mid+1,r);
st[id]=max(st[id*2],st[id*2+1]);
mn[id]=min(mn[id*2],mn[id*2+1]);
}
ll get(ll pos,ll id=1,ll l=1,ll r=n)
{
if(l==r)
{
return st[id];
}
down(id);
ll mid=l+r>>1;
if(pos<=mid) return get(pos,id*2,l,mid);
return get(pos,id*2+1,mid+1,r);
}
ll bs1(ll val,ll id=1,ll l=1,ll r=n)
{
if(st[id]<val) return r+1;
if(l==r) return l;
down(id);
ll mid=l+r>>1;
ll pos=bs1(val,id*2,l,mid);
if(pos==mid+1) return bs1(val,id*2+1,mid+1,r);
return pos;
}
ll bs2(ll val,ll id=1,ll l=1,ll r=n)
{
if(mn[id]>val) return l-1;
if(l==r) return l;
down(id);
ll mid=l+r>>1;
ll pos=bs2(val,id*2+1,mid+1,r);
if(pos==mid) return bs2(val,id*2,l,mid);
return pos;
}
ll m;
void solve()
{
cin >> n >> m;
for(int i=1;i<=n;i++) cin >> c[i];
sort(c+1,c+n+1);
build();
for(int i=1;i<=m;i++)
{
char t;
cin >> t;
if(t=='F')
{
ll c,h;
cin >> c >> h;
ll l=bs1(h);
if(l>n) continue;
ll r=l+c-1;
r=min(r,n);
ll x=get(r);
ll fi=bs1(x);
ll se=bs2(x);
ll num=r-fi+1;
update(l,fi-1,1);
update(se-num+1,se,1);
}
else
{
ll l,r;
cin >> l>> r;
cout << bs2(r)-bs1(l)+1<<'\n';
}
}
}
int main()
{
fastio
freopen(TASKNAME".INP","r",stdin);
freopen(TASKNAME".OUT","w",stdout);
solve();
}
Compilation message
grow.cpp: In function 'void build(ll, ll, ll)':
grow.cpp:22:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
22 | ll mid=l+r>>1;
| ~^~
grow.cpp: In function 'void update(ll, ll, ll, ll, ll, ll)':
grow.cpp:51:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
51 | ll mid=l+r>>1;
| ~^~
grow.cpp: In function 'll get(ll, ll, ll, ll)':
grow.cpp:64:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
64 | ll mid=l+r>>1;
| ~^~
grow.cpp: In function 'll bs1(ll, ll, ll, ll)':
grow.cpp:73:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
73 | ll mid=l+r>>1;
| ~^~
grow.cpp: In function 'll bs2(ll, ll, ll, ll)':
grow.cpp:83:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
83 | ll mid=l+r>>1;
| ~^~
grow.cpp: In function 'int main()':
grow.cpp:126:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
126 | freopen(TASKNAME".INP","r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
grow.cpp:127:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
127 | freopen(TASKNAME".OUT","w",stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
60 ms |
131072 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
72 ms |
131072 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
60 ms |
131072 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
61 ms |
131072 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
58 ms |
131072 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
60 ms |
131072 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
64 ms |
131072 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
61 ms |
131072 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
65 ms |
131072 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
68 ms |
131072 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
