#include <iostream>
#include <algorithm>
#include <vector>
#include <deque>
#include <stdio.h>
#define MAX_N 100000
#define INF 2000000000
using namespace std;
int N, M;
struct S{
int s, e;
int l, r;
int min, max, lazy;
};
vector<S> seg;
int arr[MAX_N+1];
deque<int> dq;
void init(){
dq.push_back(0);
int now=0;
while(!dq.empty()){
now=dq.front(); dq.pop_front();
if(seg[now].s!=seg[now].e){
seg[now].l=(int)seg.size(); seg.push_back({seg[now].s, (seg[now].s+seg[now].e)/2, -1, -1, 0, 0, 0}); dq.push_back(seg[now].l);
seg[now].r=(int)seg.size(); seg.push_back({(seg[now].s+seg[now].e)/2+1, seg[now].e, -1, -1, 0, 0, 0}); dq.push_back(seg[now].r);
}
}
}
void init(int idx, int x, int y){
if(seg[idx].s==seg[idx].e){
seg[idx].min=y; seg[idx].max=y; return;
}
if(seg[seg[idx].l].e>=x){
init(seg[idx].l, x, y);
}else init(seg[idx].r, x, y);
seg[idx].max=max(seg[seg[idx].l].max, seg[seg[idx].r].max);
seg[idx].min=min(seg[seg[idx].l].min, seg[seg[idx].r].min);
}
void calc(int idx){
if(seg[idx].lazy>0){
if(seg[idx].s!=seg[idx].e){
seg[seg[idx].l].max+=seg[idx].lazy; seg[seg[idx].l].min+=seg[idx].lazy; seg[seg[idx].l].lazy+=seg[idx].lazy;
seg[seg[idx].r].max+=seg[idx].lazy; seg[seg[idx].r].min+=seg[idx].lazy; seg[seg[idx].r].lazy+=seg[idx].lazy;
}
seg[idx].lazy=0;
}
}
void update(int idx, int x, int y){
if(seg[idx].lazy>0){
if(seg[idx].s!=seg[idx].e){
seg[seg[idx].l].max+=seg[idx].lazy; seg[seg[idx].l].min+=seg[idx].lazy; seg[seg[idx].l].lazy+=seg[idx].lazy;
seg[seg[idx].r].max+=seg[idx].lazy; seg[seg[idx].r].min+=seg[idx].lazy; seg[seg[idx].r].lazy+=seg[idx].lazy;
}
seg[idx].lazy=0;
}
if(seg[idx].s>y || seg[idx].e<x) return;
if(x<=seg[idx].s && seg[idx].e<=y){
seg[idx].lazy++; seg[idx].min++; seg[idx].max++; return;
}
update(seg[idx].l, x, y); update(seg[idx].r, x, y);
seg[idx].max=max(seg[seg[idx].l].max, seg[seg[idx].r].max);
seg[idx].min=min(seg[seg[idx].l].min, seg[seg[idx].r].min);
}
int min(int idx, int x, int y){
if(seg[idx].lazy>0){
if(seg[idx].s!=seg[idx].e){
seg[seg[idx].l].max+=seg[idx].lazy; seg[seg[idx].l].min+=seg[idx].lazy; seg[seg[idx].l].lazy+=seg[idx].lazy;
seg[seg[idx].r].max+=seg[idx].lazy; seg[seg[idx].r].min+=seg[idx].lazy; seg[seg[idx].r].lazy+=seg[idx].lazy;
}
seg[idx].lazy=0;
}
if(seg[idx].s>y || seg[idx].e<x) return INF;
if(x<=seg[idx].s && seg[idx].e<=y){
return seg[idx].min;
}
return min(min(seg[idx].l, x, y), min(seg[idx].r, x, y));
}
int max(int idx, int x, int y){
if(seg[idx].lazy>0){
if(seg[idx].s!=seg[idx].e){
seg[seg[idx].l].max+=seg[idx].lazy; seg[seg[idx].l].min+=seg[idx].lazy; seg[seg[idx].l].lazy+=seg[idx].lazy;
seg[seg[idx].r].max+=seg[idx].lazy; seg[seg[idx].r].min+=seg[idx].lazy; seg[seg[idx].r].lazy+=seg[idx].lazy;
}
seg[idx].lazy=0;
}
if(seg[idx].s>y || seg[idx].e<x) return -1;
if(x<=seg[idx].s && seg[idx].e<=y){
return seg[idx].max;
}
return max(max(seg[idx].l, x, y), max(seg[idx].r, x, y));
}
int find(int idx, int x){
if(seg[idx].lazy>0){
if(seg[idx].s!=seg[idx].e){
seg[seg[idx].l].max+=seg[idx].lazy; seg[seg[idx].l].min+=seg[idx].lazy; seg[seg[idx].l].lazy+=seg[idx].lazy;
seg[seg[idx].r].max+=seg[idx].lazy; seg[seg[idx].r].min+=seg[idx].lazy; seg[seg[idx].r].lazy+=seg[idx].lazy;
}
seg[idx].lazy=0;
}
if(seg[idx].s==seg[idx].e) return seg[idx].max;
if(x<=seg[seg[idx].l].e){
return find(seg[idx].l, x);
}
return find(seg[idx].r, x);
}
int findl(int x, int y ,int z){
int s=x, e=y, m=0;
while(s<e){
m=(s+e)/2;
if(find(0, m)!=z) s=m+1;
else e=m;
}
return s;
}
int findr(int x, int y, int z){
int s=x, e=y, m=0;
while(s<e){
m=(s+e)/2+1;
if(find(0, m)!=z) e=m-1;
else s=m;
}
return s;
}
int main(){
//freopen("in.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
scanf("%d%d", &N, &M);
//N=MAX_N+1; M=MAX_N+1;
for(int i=0; i<N; i++) scanf("%d", &arr[i]);
seg.push_back({0, N-1, -1, -1, 0, 0, 0});
init();
sort(arr, arr+N);
/*for(int i=0; i<N; i++){
init(0, i, arr[i]);
}*/
for(int i=(int)seg.size()-1; i>=0; i--){
if(seg[i].s==seg[i].e){
seg[i].max=seg[i].min=arr[seg[i].s];
}else{
seg[i].max=max(seg[seg[i].l].max, seg[seg[i].r].max);
seg[i].min=min(seg[seg[i].l].min, seg[seg[i].r].min);
}
}
char t; int a, b;
int s, e, m, l, r;
for(int i=0; i<M; i++){
scanf("%c", &t);
scanf("%c %d %d", &t, &a, &b);
if(t=='F'){
s=0; e=N-1;
while(s<e){
m=(s+e)/2;
if(min(0, m, N-1)<b) s=m+1;
else e=m;
}
e=min(N-1, s+a-1);
l=findl(s, e, find(0, e));
r=findr(e, N-1, find(0, e));
//cout<<s<<" "<<e<<" "<<l<<" "<<r<<endl;
if(s<=l-1) update(0, s, l-1);
if(r-e+l<=r) update(0, r-e+l, r);
}else{
s=0; e=N;
while(s<e){
m=(s+e)/2;
if(min(0, m, N)<a) s=m+1;
else e=m;
}
l=s; s=-1; e=N-1;
while(s<e){
m=(s+e)/2+1;
if(max(0, -1, m)>b) e=m-1;
else s=m;
}
r=s;
//cout<<l<<" "<<r<<endl;
printf("%d\n", max(0, r-l+1));
}
}
return 0;
}
Compilation message
grow.cpp: In function 'int main()':
grow.cpp:140:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &N, &M);
~~~~~^~~~~~~~~~~~~~~~
grow.cpp:142:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
for(int i=0; i<N; i++) scanf("%d", &arr[i]);
~~~~~^~~~~~~~~~~~~~~
grow.cpp:160:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%c", &t);
~~~~~^~~~~~~~~~
grow.cpp:161:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%c %d %d", &t, &a, &b);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1073 ms |
8652 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
504 KB |
Output is correct |
| 2 |
Execution timed out |
1075 ms |
632 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1086 ms |
1056 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1082 ms |
1056 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1081 ms |
4844 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
722 ms |
8556 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1088 ms |
8432 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
898 ms |
8680 KB |
Output is correct |
| 2 |
Execution timed out |
1083 ms |
8552 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1077 ms |
8556 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
731 ms |
8936 KB |
Output is correct |
