#include <iostream>
#include <algorithm>
using namespace std;
const long long MAXN = 1e5+5;
long long arr[MAXN];
pair<long long,long long> seg[4*MAXN];
long long lazy[4*MAXN];
void push(long long curr,long long l,long long r){
if(!lazy[curr]){
return;
}
seg[curr].first+=lazy[curr];
seg[curr].second+=lazy[curr];
if(l!=r){
lazy[2*curr]+=lazy[curr];
lazy[2*curr+1]+=lazy[curr];
}
lazy[curr] = 0;
}
void build(long long curr,long long l,long long r){
if(l==r){
seg[curr].first = arr[l];
seg[curr].second = arr[l];
return;
}
long long mid = (l+r)/2;
build(2*curr,l,mid);
build(2*curr+1,mid+1,r);
seg[curr].first = max(seg[2*curr].first,seg[2*curr+1].first);
seg[curr].second = min(seg[2*curr].second,seg[2*curr+1].second);
}
long long atpos(long long curr,long long l,long long r,long long pos){
if(lazy[curr]){
push(curr,l,r);
}
if(l==r){
return seg[curr].first;
}
long long mid = (l+r)/2;
push(2*curr+1,mid+1,r);
push(2*curr,l,mid);
if(pos<=mid){
return atpos(2*curr,l,mid,pos);
}else{
return atpos(2*curr+1,mid+1,r,pos);
}
}
long long firstpos(long long curr,long long l,long long r,long long val){
if(lazy[curr]){
push(curr,l,r);
}
if(l==r){
return l;
}
long long mid = (l+r)/2;
push(2*curr+1,mid+1,r);
push(2*curr,l,mid);
if(seg[2*curr].first>=val){
return firstpos(2*curr,l,mid,val);
}else{
return firstpos(2*curr+1,mid+1,r,val);
}
}
long long lastpos(long long curr,long long l,long long r,long long val){
if(lazy[curr]){
push(curr,l,r);
}
if(l==r){
return l;
}
long long mid =(l+r)/2;
push(2*curr+1,mid+1,r);
push(2*curr,l,mid);
if(seg[2*curr+1].second<=val){
return lastpos(2*curr+1,mid+1,r,val);
}else{
return lastpos(2*curr,l,mid,val);
}
}
void update(long long curr,long long l,long long r,long long tl,long long tr){
if(l>r){
return;
}
if(lazy[curr]){
push(curr,l,r);
}
if(r<tl||l>tr){
return;
}
if(l>=tl && r<=tr){
seg[curr].first++;
seg[curr].second++;
if(l!=r){
lazy[2*curr]++;
lazy[2*curr+1]++;
}
return;
}
long long mid =(l+r)/2;
update(2*curr,l,mid,tl,tr);
update(2*curr+1,mid+1,r,tl,tr);
seg[curr].first = max(seg[2*curr].first,seg[2*curr+1].first);
seg[curr].second = min(seg[2*curr].second,seg[2*curr+1].second);
}
int main(){
long long n,q;
cin>>n>>q;
for(long long i=1;i<=n;i++){
cin>>arr[i];
}
sort(arr+1,arr+n+1);
build(1,1,n);
for(long long i=1;i<=q;i++){
char ty;
cin>>ty;
if(ty == 'F'){
long long c,h;
cin>>c>>h;
long long pos1= firstpos(1,1,n,h);
if(atpos(1,1,n,pos1)<h){
continue;
}
long long x = pos1;
long long y = min(n,x+c-1);
long long val = atpos(1,1,n,y);
long long li = firstpos(1,1,n,val);
long long ri = lastpos(1,1,n,val);
// cout<<ri<<endl;
if(atpos(1,1,n,li) == atpos(1,1,n,pos1)){
update(1,1,n,ri-c+1,ri);
//cout<<ri-c+1<<endl;
continue;
}
update(1,1,n,x,li-1);
update(1,1,n,ri-(li-x)+1,ri);
//cout<<ri-(li-x)+1<<" "<<ri<<endl;
}else{
long long mini,maxi;
cin>>mini>>maxi;
if(firstpos(1,1,n,mini)==n && atpos(1,1,n,n)!=mini){
cout<<0<<endl;
continue;
}
if(lastpos(1,1,n,maxi)==1 && atpos(1,1,n,1)!=maxi){
cout<<0<<endl;
continue;
}
cout<<lastpos(1,1,n,maxi)-firstpos(1,1,n,mini)+1<<endl;
}
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
293 ms |
8440 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
504 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
363 ms |
1908 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
392 ms |
2132 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
280 ms |
5028 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
282 ms |
8164 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
306 ms |
8240 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
437 ms |
8636 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
387 ms |
8664 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
541 ms |
9068 KB |
Output isn't correct |
