#ifndef Local
#pragma GCC optimize("O3,unroll-loops")
const int lim=2e5+100;
#else
const int lim=3e3+100;
#endif
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pb push_back
const int mod=998244353;
using pii=pair<int,int>;
struct BIT{
int n,tree[lim];
BIT();
BIT(int n):n(n){
memset(tree,0,sizeof(int)*(n+1));
}
BIT(int n,int*ref){
memset(tree,0,sizeof(int)*(n+1));
for(int i=1;i<=n;i++){
tree[i]+=ref[i];
if(i+(i&-i)<=n)tree[i+(i&-i)]+=tree[i];
}
}
inline void update(int p,int val){
while(p<=n){
tree[p]+=val;
p+=p&-p;
}
}
inline int query(int p){
int res=0;
while(p){
res+=tree[p];
p-=p&-p;
}
return res;
}
};
struct RangeBIT{
BIT a,b;
RangeBIT(int n):a(n),b(n){}
inline void update(int l,int r,int x){
a.update(l,x);
a.update(r+1,-x);
b.update(l,x*(l-1));
b.update(r+1,-x*r);
}
inline void update(int p,int x){
update(p,p,x);
}
inline int sumy(int p){
return p * a.query(p) - b.query(p);
}
inline int query(int l,int r){
return sumy(r)-sumy(l-1);
}
inline int query(int p){
return query(p,p);
}
};
void solve(){
int n,q;
cin>>n>>q;
int a[n+1];
for(int i=1;i<=n;i++){
cin>>a[i];
}
sort(a+1,a+n+1);
RangeBIT bit(n);
for(int i=1;i<=n;i++){
bit.update(i,a[i]);
}
while(q--){
char t;
cin>>t;
if(t=='F'){
int c,h;
cin>>c>>h;
int l=1,r=n,resind=-1;
while(l<=r){
int mid=(l+r)>>1;
if(h<=bit.query(mid)){
resind=mid;
r=mid-1;
}else{
l=mid+1;
}
}
//cerr<<resind<<"\n";
if(resind==-1)continue;
int endval=bit.query(min(n,resind+c-1));
//cerr<<endval<<"\n";
l=resind,r=n;
int firstind=-1;
while(l<=r){
int mid=(l+r)>>1;
if(endval<bit.query(mid)){
r=mid-1;
}
else if(endval==bit.query(mid)){
firstind=mid;
r=mid-1;
}
else{
l=mid+1;
}
}
//cerr<<firstind<<"\n";
bit.update(resind,firstind-1,1);
l=firstind,r=n;
int lastind=-1;
while(l<=r){
int mid=(l+r)>>1;
//cerr<<l<<" "<<r<<" "<<mid<<" "<<bit.query(mid)<<" "<<endval<<"\n";
if(endval<bit.query(mid)){
r=mid-1;
}
else if(endval==bit.query(mid)){
lastind=mid;
l=mid+1;
}
else{
l=mid+1;
}
}
//cerr<<(c-(firstind-resind))<<"\n";
bit.update(max(firstind,lastind-(c-(firstind-resind))+1),lastind,1);
/*
for(int i=1;i<=n;i++){
cerr<<bit.query(i)<<" ";
}cerr<<"\n";
*/
}else{
int L,R;
cin>>L>>R;
int l=1,r=n,begind=-1;
while(l<=r){
int mid=(l+r)>>1;
if(L<=bit.query(mid)){
begind=mid;
r=mid-1;
}else{
l=mid+1;
}
}
if(begind==-1){
cout<<"0\n";
continue;
}
l=1,r=n;
int endind=-1;
while(l<=r){
int mid=(l+r)>>1;
if(bit.query(mid)<=R){
endind=mid;
l=mid+1;
}else{
r=mid-1;
}
}
if(endind==-1){
cout<<"0\n";
return;
}
//cerr<<endind<<" "<<begind<<"\n";
cout<<endind-begind+1<<"\n";
}
//cerr<<"ok\n";
}
}
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);cout.tie(NULL);
#ifdef Local
freopen(".in","r",stdin);
freopen(".out","w",stdout);
#else
//freopen("optmilk.in","r",stdin);
//freopen("optmilk.out","w",stdout);
#endif
int t=1;
//cin>>t;
while (t--)
{
solve();
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
19 ms |
4184 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
3420 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
3420 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
3420 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
3420 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
14 ms |
3932 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
142 ms |
4180 KB |
Output is correct |
| 2 |
Incorrect |
43 ms |
4808 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
4188 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
173 ms |
4384 KB |
Output is correct |
| 2 |
Incorrect |
43 ms |
4688 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
17 ms |
4188 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
142 ms |
4848 KB |
Output is correct |
