#include<bits/stdc++.h>
#define ll long long
#define ff first
#define ss second
#define pb push_back
using namespace std;
int st[400005];
vector <int> v;
int n, m, ans, llidx, lridx, rlidx, rridx, L, R;
int cons(int pos, int l, int r){
if(l==r){
st[pos]=v[l]-v[l-1];
return st[pos];
}
int mid=(l+r)/2;
st[pos]=cons(pos*2, l, mid)+cons(pos*2+1, mid+1, r);
return st[pos];
}
int find(int pos, int l, int r, int mn, int nw){
if(l==r){
return r;
}
int mid=(l+r)/2;
if(nw+st[pos*2]>=mn){
return find(pos*2, l, mid, mn, nw);
}
return find(pos*2+1, mid+1, r, mn, nw+st[pos*2]);
}
int fun(int pos, int l, int r, int k){
if(l==r and l==k){
return ans+st[pos];
}
int mid=(l+r)/2;
if(k<=mid){
return fun(pos*2, l, mid, k);
}
else{
ans+=st[pos*2];
return fun(pos*2+1, mid+1, r, k);
}
}
int upd(int pos, int l, int r, int q, int diff){
if(q==l and l==r){
st[pos]+=diff;
return st[pos];
}
else if(q<l or q>r){
return st[pos];
}
int mid=(l+r)/2;
st[pos]=upd(pos*2, l, mid, q, diff)+
upd(pos*2+1, mid+1, r, q, diff);
return st[pos];
}
int main(){
cin>>n>>m;
v.push_back(0);
v.push_back(INT_MAX);
for(int i=1; i<=n; i++){
int a;
cin>>a;
v.push_back(a);
}
sort(v.begin(), v.end());
cons(1, 1, n);
for(int i=1; i<=m; i++){
int a, b;
char c;
cin>>c>>a>>b;
if(c=='F'){
llidx=find(1, 1, n, b, 0);
ans=0;
L=fun(1, 1, n, llidx);
ans=0;
R=fun(1, 1, n, llidx+a-1);
rridx=find(1, 1, n, R+1, 0)-1;
if(L==R){
//cout<<llidx<<" "<<rridx<<endl;
upd(1, 1, n, llidx, 1);
upd(1, 1, n, rridx+1, -1);
}
else if(llidx+a>=n){
//cout<<llidx<<endl;
upd(1, 1, n, llidx, 1);
}
else{
lridx=find(1, 1, n, R, 0)-1;
rlidx=rridx-(a-(lridx-llidx+1)-1);-
//cout<<llidx<<" "<<lridx<<" "<<rlidx<<" "<<rridx<<endl;
upd(1, 1, n, llidx, 1);
upd(1, 1, n, lridx+1, -1);
upd(1, 1, n, rlidx, 1);
upd(1, 1, n, rridx+1, -1);
}
/*for(int i=1; i<n*2; i++){
cout<<st[i]<<" ";
}
cout<<endl;*/
}
else{
if(a>st[1]){
cout<<0<<endl;
}
else {
cout<<find(1, 1, n, b+1, 0)-find(1, 1, n, a, 0)+1<<endl;
}
}
}
}
Compilation message
grow.cpp: In function 'int main()':
grow.cpp:88:39: warning: value computed is not used [-Wunused-value]
88 | rlidx=rridx-(a-(lridx-llidx+1)-1);-
| ^
89 | //cout<<llidx<<" "<<lridx<<" "<<rlidx<<" "<<rridx<<endl;
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
90 | upd(1, 1, n, llidx, 1);
| ~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
121 ms |
1968 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
147 ms |
696 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
202 ms |
696 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
98 ms |
1396 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
17 ms |
3280 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
111 ms |
1948 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
27 ms |
3528 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
25 ms |
3540 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
32 ms |
3580 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
