Submission #701044

#	Time	Username	Problem	Language	Result	Execution time	Memory
701044		Ahmed57	Growing Trees (BOI11_grow)	C++14	100 / 100	305 ms	6932 KiB

grow

//#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,O3")
#include <bits/stdc++.h>
using namespace std;
long long seg[400001];
long long lazy[400001];
long long arr[100001];
void build(int p,int l,int r){
    if(l==r){
        seg[p] = arr[l];
        return ;
    }
    int md = (l+r)/2;
    build(p*2,l,md);
    build(p*2+1,md+1,r);
    seg[p] = max(seg[p*2],seg[p*2+1]);
}
void propgate(int p,int l,int r){
    seg[p]+=lazy[p];
    if(l!=r){
        lazy[p*2]+=lazy[p];
        lazy[p*2+1]+=lazy[p];
    }
    lazy[p] =0;
}
int lowe(int p,int l,int r,int x){
    propgate(p,l,r);
    if(l==r)return l;
    int md = (l+r)/2;
    propgate(p*2,l,md);
    propgate(p*2+1,md+1,r);
    if(seg[p*2]>=x)return lowe(p*2,l,md,x);
    else return lowe(p*2+1,md+1,r,x);
}
int ge(int p,int l,int r,int ind){
    propgate(p,l,r);
    if(l==r)return seg[p];
    int md = (l+r)/2;
    if(ind<=md)return ge(p*2,l,md,ind);
    else return ge(p*2+1,md+1,r,ind);
}void update(int p,int l,int r,int lq,int rq){
    propgate(p,l,r);
    if(l>=lq&&r<=rq){
        lazy[p]+=1;
        propgate(p,l,r);
        return ;
    }
    if(l>rq||r<lq)return;
    int md = (l+r)/2;
    update(p*2,l,md,lq,rq);update(p*2+1,md+1,r,lq,rq);
    seg[p] = max(seg[p*2],seg[p*2+1]);
}
int main(){
    //ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int n,q;
    cin>>n>>q;
    for(int i = 1;i<=n;i++)cin>>arr[i];
    sort(arr+1,arr+n+1);
    build(1,1,n);
    while(q--){
        char c;cin>>c;
        if(c=='C'){
            int l,r;cin>>l>>r;
            propgate(1,1,n);
            if(seg[1]<l){
                cout<<0<<endl;
                continue;
            }
            int ind1 = lowe(1,1,n,l);
            if(seg[1]<r+1){
                cout<<n-ind1+1<<endl;
                continue;
            }
            int ind2 =lowe(1,1,n,r+1);
            cout<<ind2-ind1<<endl;
        }else{
            propgate(1,1,n);
            int l,r;
            cin>>l>>r;
            if(seg[1]<r){
                continue;
            }
            int ind = lowe(1,1,n,r);
            int val = ge(1,1,n,ind);
            if(ind+l-1>=n){
                update(1,1,n,ind,n);
                continue;
            }
            int d = ge(1,1,n,ind+l-1);
            int ind2 = lowe(1,1,n,d);
            int ind3 = 0;
            if(seg[1]<=d)ind3 = n+1;
            else ind3 = lowe(1,1,n,d+1);
            int len = (ind+l-1)-ind2+1;
            if(d!=val){
                update(1,1,n,ind,ind2-1);
            }
            update(1,1,n,ind3-len,ind3-1);
        }
    }
}

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10