#include <bits/stdc++.h>
#define maxn (int)(1e5+51)
#define all(x) x.begin(), x.end()
#define sz(x) (int) x.size()
#define endl '\n'
#define ll long long
#define pb push_back
#define ull unsigned long long
#define ii pair<int,int>
#define iii tuple<int,int,int>
#define inf 2000000001
#define mod 1000000007 //998244353
#define _ ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
using namespace std;
template<typename X, typename Y> bool ckmin(X& x, const Y& y) { return (y < x) ? (x=y,1):0; }
template<typename X, typename Y> bool ckmax(X& x, const Y& y) { return (x < y) ? (x=y,1):0; }
int n,m,bit[maxn];
void insert(int x,int d){
while(x<=n)bit[x]+=d,x+=x&(-x);
}
void add(int l,int r,int d){
insert(l,d);
insert(r+1,-d);
}
int query(int x){
int ans = 0;
while(x){
ans += bit[x];
x -= x&(-x);
}
return ans;
}
int main(){_
cin>>n>>m;
vector<int>v(n);
for(auto& x:v)cin>>x;
sort(all(v));
for(int i=0;i<n;++i)add(i+1,i+1,v[i]);
// for(int i=1;i<=n;++i)cerr<<query(i)<<" \n"[i==n];
while(m--){
char op;cin>>op;
if(op=='F'){
int c,h;cin>>c>>h;
// cerr<<"adding to "<<c<<" smallest elements starting from "<<h<<endl;
int l = 1, r = n, ans = inf;
while(l<=r) {
int md = l + (r-l+1)/2;
if(query(md)>=h)ans = md, r = md-1;
else l = md + 1;
}
if(ans==inf)continue;
int lo = ans, hi = min(n,ans + c - 1);//minelement >= h
int biggest = query(hi);//maxheight of added element
// cerr<<"found "<<lo<<" as min index >=h"<<endl;
// cerr<<"biggest height to be added is "<<biggest<<endl;
if(biggest!=query(lo)){
l = 1, r = n, ans = inf;
while(l<=r){
int md = l + (r-l+1)/2;
if(query(md)<biggest)ans = md, l = md + 1;
else r = md - 1;
}//ans = largest idx whose height is < biggest
add(lo,ans,1);//added everyone in interval [query(lo),biggest-1]
// cerr<<"max index < biggest is"<<ans<<endl;
}else ans = lo-1;
int left = c - (ans-lo+1);
//now add to rightmost biggest
l = 1, r = n, ans = inf;
while(l<=r){
int md = l + (r-l+1)/2;
if(query(md)<=biggest)ans = md, l = md + 1;
else r = md - 1;
}
// cerr<<"now, adding from "<<max(ans-left+1,lo)<<" to "<<ans<<endl;
add(max(ans-left+1,lo),ans,1);
}else{
int le,ri;cin>>le>>ri;
int l = 1, r = n, ans = inf;
while(l<=r){
int md = l + (r-l+1)/2;
if(query(md)>=le)ans = md, r = md - 1;
else l = md + 1;
}
//se lo == infinito, todos os elementos sao menores que le, portanto estou fora do intervalo
//se hi == infinito, todos os elementos sao maiores que ri, portanto estou fora do intervalo
int lo = ans;
l = 1, r = n, ans = inf;
while(l<=r){
int md = l + (r-l+1)/2;
if(query(md)<=ri)ans = md, l = md + 1;
else r = md - 1;
}
int hi = ans;
if(max(lo,hi)==inf)cout<<0<<endl;
else cout<<hi-lo+1<<endl;
}
// for(int i=1;i<=n;++i)cerr<<query(i)<<" \n"[i==n];
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
51 ms |
1100 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
2 ms |
340 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
340 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
42 ms |
608 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
37 ms |
548 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
55 ms |
908 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
68 ms |
960 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
52 ms |
1000 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
126 ms |
1128 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
70 ms |
1156 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
98 ms |
1528 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
