This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define MAXN (1000005)
struct node{
ll s, e, m, val, maxi, lazy;
node *l, *r;
node(ll S, ll E){
s = S, e = E, m = (s+e)/2;
val = 0;
maxi = 0;
lazy = 0;
if(s != e){
l = new node(s,m);
r = new node(m + 1,e);
}
}
void propogate(){
if(lazy==0) return;
val += lazy*(e-s+1);
maxi += lazy;
if(s != e){ //not a leaf, send lazy tags to children (remember to write this if statement)
l->lazy += lazy;
r->lazy += lazy;
}
lazy = 0;
}
void update(int S, int E, ll V){
if(s == S && e == E) lazy += V;
else{
if(E <= m) l->update(S, E, V);
else if (m < S) r->update(S, E, V);
else l->update(S, m, V),r->update(m+1, E, V);
l->propogate(),r->propogate();
val = l->val + r->val;
maxi = max(l -> maxi,r -> maxi);
}
}
ll bsL(ll H){ //leftmost position >= H
propogate(); //remember to propogate
if(s == e){
if(maxi >= H) return s;
else return 1000000005;
}
if(l -> maxi >= H){
return l -> bsL(H);
}else if(r -> maxi >= H){
return r -> bsL(H);
}else{
return 1000000005;
}
}
ll query(int S, int E){
propogate(); //remember to propogate
if(s == S && e == E) return val;
else if(E <= m) return l->query(S, E);
else if(S >= m+1) return r->query(S, E);
else return l->query(S, m) + r->query(m+1, E);
}
} *root;
int main(){
ios_base::sync_with_stdio(false);cin.tie(0);
ll N,M;
cin>>N>>M;
root = new node(0,N - 1);
ll arr[N];
for(ll i = 0;i < N;i++){
cin>>arr[i];
}
sort(arr,arr + N);
for(ll i = 0;i < N;i++){
root -> update(i,i,arr[i]);
}
for(ll i = 0;i < M;i++){
char t;
cin>>t;
if(t == 'F'){
ll c,h;
cin>>c>>h;
ll start = root -> bsL(h);
if(start == 1000000005){
continue;
}
ll endval = root -> query(min(N - 1,start + c - 1),min(N - 1,start + c - 1));
ll end = -1e18;
end = root -> bsL(endval);
end--;
ll end2 = root -> bsL(endval + 1);
if(end2 == 1000000005){
end2 = N - 1;
}else{
end2--;
}
ll start2 = max(end + 1,end2 - (c - (end - start + 1)) + 1);
if(start2 == 1000000005){
continue;
}
if(start <= end) root -> update(start,end,1);
if(start2 <= end2) root -> update(start2,end2,1);
}else if(t == 'C'){
ll L,R;
cin>>L>>R;
ll start = root -> bsL(L);
ll end = root -> bsL(R + 1);
if(end == 1000000005){
end = N - 1;
}else{
end--;
}
if(start == 1000000005 || end == 1000000005){
cout<<0<<'\n';
}else{
cout<<end - start + 1<<'\n';
}
}
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |