Submission #880971

#	Time	Username	Problem	Language	Result	Execution time	Memory
880971		nghiaaa	Growing Trees (BOI11_grow)	C++14	0 / 100	72 ms	9552 KiB

grow

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define db double
#define ii pair<int,int>
#define f first
#define s second
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define all(v) v.begin(),v.end()
#define BIT(i) ((ll)1<<(i))
#define endl "\n"
#define debug(x) for (auto p: x) cout<<p<<' ';cout<<endl
#define forw(i,j,z) for(int i=(int)j;i<=(int)z;i++)
#define forw2(i,j,z,k) for(int i=(int)j;i<=(int)z;i+=k)
#define ford(i,j,z) for (int i=(int)j;i>=(int)z;i--)
#define ford2(i,j,z,k) for (int i=(int)j;i>=(int)z;i-=k)
#define sz(a) (int)a.size()
const ll inf=(ll)1<<60;
struct IT{
    int lazy;
    ll MAX;
};
const int N=100000;
ll a[N+1];
int n,q;
IT tree[4*N+1];
void build(int node,int l,int r)
{
    if (l==r)
        tree[node].MAX=a[l];
    else{
        int mid=(l+r)>>1;
        build(node<<1,l,mid);
        build(node<<1|1,mid+1,r);
        tree[node].MAX=max(tree[node<<1].MAX,tree[node<<1|1].MAX);
    }
}
void lift(int node,int val)
{
    tree[node].MAX+=val;
    tree[node].lazy+=val;
}
void pull(int node)
{
    if (tree[node].lazy)
    {
        lift(node<<1,tree[node].lazy);
        lift(node<<1|1,tree[node].lazy);
        tree[node].lazy=0;
    }
}
int find_Lower(int node,int l,int r,ll val)
{
    if (l==r)
    {
        if (tree[node].MAX>=val) return l;
        return l+1;
    }
    else{
        pull(node);
        int mid=(l+r)>>1;
        if (tree[node<<1].MAX>=val)
            return find_Lower(node<<1,l,mid,val);
        else return find_Lower(node<<1|1,mid+1,r,val);
    }
}
int getValue(int node,int l,int r,int i)
{
    if (l==r)
        return tree[node].MAX;
    else{
        pull(node);
        int mid=(l+r)>>1;
        if (i<=mid) return getValue(node<<1,l,mid,i);
        else return getValue(node<<1|1,mid+1,r,i);
    }
}
void update(int node,int l,int r,int L,int R)
{
    if (l>=L&&r<=R) lift(node,1);
    else{
        int mid=(l+r)>>1;
        if (!(l>R||mid<L)) update(node<<1,l,mid,L,R);
        if (!(mid+1>R||r<L)) update(node<<1|1,mid+1,r,L,R);
        tree[node].MAX=max(tree[node<<1].MAX,tree[node<<1|1].MAX);
    }
}
void solve()
{
    cin>>n>>q;
    forw(i,1,n) cin>>a[i];
    sort(a+1,a+n+1);
    build(1,1,n);
    while(q--)
    {
        char ask;cin>>ask;
        if (ask=='C')
        {
            ll l,r;
            cin>>l>>r;
            cout<<find_Lower(1,1,n,r+1)-find_Lower(1,1,n,l)<<'\n';
        }
        else{
            int c;ll h;
            cin>>c>>h;
            int l=find_Lower(1,1,n,h),r=l+c-1;
            if (r>=n)
                update(1,1,n,l,n);
            else{
                int val=getValue(1,1,n,r);
                int L=find_Lower(1,1,n,val),R=find_Lower(1,1,n,val+1)-1;
                if (l<L) update(1,1,n,l,L-1);
                int left=c-(L-l);
                if (R-left+1<=R)
                    update(1,1,n,R-left+1,R);
            }
        }
    }
}
signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    //cout<<setprecision(6)<<fixed;
    //time_t TIME_TU=clock();
    int t=1;
    //cin>>t;
    while(t--)
        solve();
    //time_t TIME_TV=clock();
    //cerr<<(db)(TIME_TV-TIME_TU)/CLOCKS_PER_SEC<<endl;
    return 0;
}

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