#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#define ll long long
#define pb push_back
#define eb emplace_back
#define pu push
#define ins insert
#define bruh ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define fu(x,a,b) for (auto x=a;x<=b;x++)
#define fd(x,a,b) for (auto x=a;x>=b;x--)
#define int ll
using namespace std;
//mt19937 mt(chrono::steady_clock::now().time_since_epoch().count());
typedef pair<int, int> ii;
const int N = 1e5+5;
const int mod = 1e9+7;
const int inf = 1e18;
using cd = complex<double>;
const long double PI = acos(-1);
int power(int a,int b) {ll x = 1;if (a >= mod) a%=mod; while (b) {if (b & 1) x = x*a % mod;a = a*a % mod;b>>=1;}return x;}
int n,m, st[4*N], lazy[4*N];
vector<int> h;
void push(int id)
{
st[id*2] += lazy[id], st[id*2+1] += lazy[id];
lazy[id*2] += lazy[id], lazy[id*2+1] += lazy[id];
lazy[id] = 0;
}
void update(int id,int l,int r,int u,int v,int val)
{
if (l>v || r<u) return;
if (u<=l && r<=v) {st[id] += val, lazy[id] += val; return;}
push(id);
int mid = l+r>>1;
update(id*2,l,mid,u,v,val); update(id*2+1,mid+1,r,u,v,val);
st[id] = max(st[id*2],st[id*2+1]);
}
int lb(int u)
{
int l = 0, r = n-1, id = 1;
if (st[1] < u) return n;
while (l<r)
{
push(id);
int mid = l+r>>1;
if (st[id*2] >= u) id *=2, r = mid;
else id = id*2+1, l = mid+1;
}
return l;
}
int get(int i)
{
int l = 0, r = n-1, id = 1;
while (l<r)
{
push(id);
int mid = l+r>>1;
if (i>mid) l = mid+1, id = id*2+1;
else r = mid, id = id*2;
}
return st[id];
}
void solve()
{
cin>>n>>m;
h.resize(n);
for (int i=0;i<n;i++) cin>>h[i];
sort(h.begin(),h.end());
for (int i=0;i<n;i++) update(1,0,n-1,i,i,h[i]);
while (m--)
{
char type; cin>>type;
if (type=='F')
{
int c, x; cin>>c>>x;
int pos = lb(x);
//cout<<pos<<endl;
if (x != n)
{
int num = min(c,n-pos+1);
int nxtval = get(pos+num-1);
int tmp = lb(nxtval)-1;
//cout<<pos<<" "<<lb(nxtval)-1<<endl;
update(1,0,n-1,pos,tmp,1);
int nxt = lb(nxtval+1)-1;
//cout<<nxt<<endl;
update(1,0,n-1,nxt-(c-(tmp-pos+1))+1,nxt,1);
}
} else
{
int l,r; cin>>l>>r;
cout<<lb(r+1)-lb(l)<<endl;
}
// for (int i=0;i<n;i++) cout<<get(i)<<" ";
// cout<<endl;
}
}
signed main()
{
bruh
//freopen("input.inp","r",stdin);
//freopen("output.inp","w",stdout);
int t = 1;
//cin>>t;
while (t--)
{
solve();
cout<<"\n";
}
}
Compilation message
grow.cpp: In function 'void update(long long int, long long int, long long int, long long int, long long int, long long int)':
grow.cpp:40:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
40 | int mid = l+r>>1;
| ~^~
grow.cpp: In function 'long long int lb(long long int)':
grow.cpp:52:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
52 | int mid = l+r>>1;
| ~^~
grow.cpp: In function 'long long int get(long long int)':
grow.cpp:65:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
65 | int mid = l+r>>1;
| ~^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
100 ms |
6484 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
348 KB |
Output is correct |
| 2 |
Correct |
4 ms |
348 KB |
Output is correct |
| 3 |
Incorrect |
5 ms |
604 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
110 ms |
1828 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
112 ms |
1876 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
89 ms |
3924 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
87 ms |
6172 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
97 ms |
6136 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
130 ms |
6776 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
119 ms |
6488 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
153 ms |
7508 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
