#include <bits/stdc++.h>
#define int long long
//#define double long double
#define pii pair<int,int>
#define all(a) a.begin(),a.end()
#define debug(a) cout << #a << " = " << a << endl;
#define keepUnique(a) sort(all(a));a.erase(unique(all(a)),a.end())
#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;
const int N = 200005;
int n,m,ara[N];
pii tree[N*4+12];
int lazy[N*4+12];
void build(int at,int L,int R){
if(L == R){
tree[at] = {ara[L],ara[R]};
return;
}
int mid = (L+R)>>1;
build(at<<1,L,mid);
build((at<<1)+1,mid+1,R);
tree[at].first = min(tree[at<<1].first,tree[(at<<1)+1].first);
tree[at].second = max(tree[at<<1].second,tree[(at<<1)+1].second);
}
void pushdown(int at,int L,int R){
int lc = at*2;
int rc = at*2+1;
lazy[lc] = lazy[at];
lazy[rc] = lazy[at];
tree[lc].first+=lazy[at];
tree[rc].first+=lazy[at];
tree[lc].second += lazy[at];
tree[rc].second += lazy[at];
lazy[at] = 0;
}
void update(int at,int L,int R,int l,int r){
if(l > r)return;
if(L > r or R < l)return;
if(l <= L and R <= r){
tree[at].first++;
tree[at].second++;
lazy[at]++;
return;
}
if(lazy[at])pushdown(at,L,R);
int mid = (L+R)>>1;
update(at<<1,L,mid,l,r);
update((at<<1)+1,mid+1,R,l,r);
tree[at].first = min(tree[at<<1].first,tree[(at<<1)+1].first);
tree[at].second = max(tree[at<<1].second,tree[(at<<1)+1].second);
}
int lower(int at,int L,int R,int num){
// num er theke boro ba shoman shob theke choto number er index dibe..
if(L == R){
//debug(tree[L].first);
//if(tree[at].first < num)return L+1;
//debug(L);
//debug(num);
return L;
}
if(lazy[at])pushdown(at,L,R);
int mid = (L+R)>>1;
if(tree[at*2].second >= num)lower(at*2,L,mid,num);
else lower(at*2+1,mid+1,R,num);
}
int upper(int at,int L,int R,int num)
{
// num er theke choto ba shoman shob theke boro number er index dibe..
if(L == R){
//if(tree[L].first )
return L;
}
if(lazy[at])pushdown(at,L,R);
int mid = (L+R)>>1;
if(tree[at*2+1].first <= num)return upper(at*2+1,mid+1,R,num);
else return upper(at*2,L,mid,num);
}
int find_kth(int at,int L,int R,int k)
{
if(L == R)return tree[at].first;
if(lazy[at])pushdown(at,L,R);
int mid = (L+R)>>1;
if(k <= mid)return find_kth(at<<1,L,mid,k);
else return find_kth((at<<1)+1,mid+1,R,k);
}
int32_t main()
{
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
scanf("%lld %lld",&n,&m);
for(int i = 1; i <= n;i++){
cin >> ara[i];
}
sort(ara+1,ara+1+n);
//for(int i = 1; i <= n;i++)cout << ara[i] << " ";cout << endl;
build(1,1,n);
char s[10];
//update(1,1,n,1,n);
//cout << tree[2].first << " " << tree[2].second << endl;
//cout << find_kth(1,1,n,3) << endl;
while(m--){
scanf("%s",s);
if(s[0] == 'F'){
int hi,ci;
scanf("%lld %lld",&ci,&hi);
int ll = lower(1,1,n,hi);//exit(0);
if(find_kth(1,1,n,ll) < hi)continue;
int rr = min(n,ll+ci-1);
int kth = find_kth(1,1,n,rr);
int left_expand = lower(1,1,n,kth);
int right_expand = upper(1,1,n,kth);
//debug(ll);
////debug(rr);
//debug(kth);
//debug(left_expand);
//debug(right_expand);
// upd(ll,left_expand-1);
// upd()
//printf("ekta update gese [%d-%d]\n",ll,left_expand-1);
update(1,1,n,ll,left_expand-1);
int baki = left_expand-ll;
baki = (rr-ll+1)-baki;
update(1,1,n,right_expand-baki+1,right_expand);
//printf("ekta update gese [%d-%d]\n",right_expand-baki+1,right_expand);
}
else{
int a,b;
scanf("%lld%lld",&a,&b);
//debug(upper(1,1,n,b));
//debug(lower(1,1,n,a));
int u = upper(1,1,n,b);
int llo = lower(1,1,n,a);
int ans = u-llo+1;
if(u == llo){
int kth = find_kth(1,1,n,u);
//debug(kth);
if(kth < a or kth > b)ans = 0;
}
printf("%lld\n",ans);
}
}
return 0;
}
Compilation message
grow.cpp: In function 'long long int lower(long long int, long long int, long long int, long long int)':
grow.cpp:71:1: warning: control reaches end of non-void function [-Wreturn-type]
}
^
grow.cpp: In function 'int32_t main()':
grow.cpp:97:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld %lld",&n,&m);
~~~~~^~~~~~~~~~~~~~~~~~~
grow.cpp:109:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%s",s);
~~~~~^~~~~~~~
grow.cpp:112:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld %lld",&ci,&hi);
~~~~~^~~~~~~~~~~~~~~~~~~~~
grow.cpp:138:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld%lld",&a,&b);
~~~~~^~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
64 ms |
7292 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
512 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
44 ms |
1172 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
47 ms |
1272 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
69 ms |
4132 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
80 ms |
6720 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
71 ms |
7452 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
131 ms |
7416 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
85 ms |
7448 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
141 ms |
7780 KB |
Output isn't correct |
