oj.uz

Submission #153376

# Submission time Handle Problem Language Result Execution time Memory
153376 2019-09-13T19:33:01 Z brcode Growing Trees (BOI11_grow) C++14
100 / 100
 538 ms 9336 KB 
#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){
        if(seg[curr].first>=val){
            return l;
        }
        return -1;
    }
    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){
        if(seg[curr].first<=val){
            return l;
        }
        return -1;
    }
    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(pos1==-1){
                continue;
            }
            if(pos1+c-1>=n){
                update(1,1,n,pos1,n);
                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);
          
            int needed = c-(li-x);
            update(1,1,n,ri-needed+1,ri);
           //cout<<ri-needed<<" "<<ri<<endl;
            //cout<<ri-(li-x)+1<<" "<<ri<<endl;
        }else{
            long long mini,maxi;
            cin>>mini>>maxi;
            

            if(firstpos(1,1,n,mini) == -1||lastpos(1,1,n,maxi)==-1){
                cout<<0<<endl;
                continue;
            }
            cout<<lastpos(1,1,n,maxi)-firstpos(1,1,n,mini)+1<<endl;
          
        }
    }
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 318 ms 7544 KB Output is correct
2 Correct 410 ms 9336 KB Output is correct
3 Correct 185 ms 8824 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 376 KB Output is correct
2 Correct 16 ms 504 KB Output is correct
3 Correct 16 ms 504 KB Output is correct
4 Correct 13 ms 504 KB Output is correct
5 Correct 302 ms 1860 KB Output is correct
6 Correct 393 ms 1992 KB Output is correct
7 Correct 18 ms 760 KB Output is correct
8 Correct 295 ms 1636 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 364 ms 1272 KB Output is correct
2 Correct 370 ms 2168 KB Output is correct
3 Correct 7 ms 760 KB Output is correct
4 Correct 329 ms 1684 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 392 ms 1224 KB Output is correct
2 Correct 415 ms 2164 KB Output is correct
3 Correct 21 ms 888 KB Output is correct
4 Correct 373 ms 2168 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 275 ms 4104 KB Output is correct
2 Correct 368 ms 8620 KB Output is correct
3 Correct 96 ms 2424 KB Output is correct
4 Correct 157 ms 8456 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 296 ms 7300 KB Output is correct
2 Correct 398 ms 8660 KB Output is correct
3 Correct 181 ms 8696 KB Output is correct
4 Correct 99 ms 2504 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 307 ms 7544 KB Output is correct
2 Correct 319 ms 8700 KB Output is correct
3 Correct 185 ms 8796 KB Output is correct
4 Correct 94 ms 2424 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 422 ms 7272 KB Output is correct
2 Correct 365 ms 8440 KB Output is correct
3 Correct 112 ms 8036 KB Output is correct
4 Correct 327 ms 8420 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 382 ms 7416 KB Output is correct
2 Correct 415 ms 8824 KB Output is correct
3 Correct 347 ms 9196 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 538 ms 7800 KB Output is correct