Submission #1268406

#	Time	Username	Problem	Language	Result	Execution time	Memory
1268406		abel2008	Growing Trees (BOI11_grow)	C++20	100 / 100	724 ms	3364 KiB

grow

#include <iostream>
#include <algorithm>
using namespace std;
int n,q,a[100005],c,h,minh,maxh,aint[400005],lazy[400005],st,dr,st1,dr1,pos,plateunum;
char op;

void propagate(int node,int l,int r) {
        if (l==r)
                return ;
        if (lazy[node]==0)
                return ;
        int mid = (l+r)/2;
        lazy[node*2]+=lazy[node];
        lazy[node*2+1]+=lazy[node];
        aint[node*2]+=(mid-l+1)*lazy[node];
        aint[node*2+1]+=(r-mid)*lazy[node];
        lazy[node] = 0;
}

void create(int node,int l,int r) {
        if (l==r) {
                aint[node] = a[l];
                return ;
        }
        int mid = (l+r)/2;
        create(node*2,l,mid);
        create(node*2+1,mid+1,r);
        aint[node] = aint[node*2]+aint[node*2+1];
}

int pointquery(int node,int l,int r,int pos) {
        propagate(node,l,r);
        if (r<pos||l>pos)
                return 0;
        if (l==r) {
                return aint[node];
        }
        int mid = (l+r)/2;
        return pointquery(node*2,l,mid,pos) +
        pointquery(node*2+1,mid+1,r,pos);
}

int bs1() {
        int st = 0,dr = n+1;
        // st always smaller, dr is bigger equal
        while(st+1<dr) {
                int mid = (st+dr)/2;
                if (pointquery(1,1,n,mid)<pos) {
                        st = mid;
                } else {
                        dr = mid;
                }
        }
        return dr;
}

int bs2() {
        int st = 0,dr = n+1;
        // st is last index <=
        // dr is >
        while(st+1<dr) {
                int mid = (st+dr)/2;
                if (pointquery(1,1,n,mid)<=pos) {
                        st = mid;
                } else {
                        dr = mid;
                }
        }
        return st;
}

void update(int node,int l,int r,int st,int dr,int ad) {
        propagate(node,l,r);
        if (r<st||l>dr)
                return ;
        if (l>=st&&r<=dr) {
                lazy[node]+=ad;
                aint[node]+=(r-l+1)*ad;
                return ;
        }
        int mid = (l+r)/2;
        update(node*2,l,mid,st,dr,ad);
        update(node*2+1,mid+1,r,st,dr,ad);
        aint[node] = aint[node*2]+aint[node*2+1];
}

int main() {
        cin>>n>>q;
        for (int i = 1;i<=n;++i)
                cin>>a[i];
        sort(a+1,a+1+n);
        create(1,1,n);
        for (int i = 1;i<=q;++i) {
                cin>>op;
                if (op=='F') {
                        cin>>c>>h;
                        // find first el >=h
                        pos = h;
                        st = bs1();
                        if (st==n+1) {
                                // we dont hav
                                continue;
                        }
                        dr = min(n,st+c-1);
                        plateunum = pointquery(1,1,n,dr);
                        pos = plateunum;
                        st1 = bs1();
                         dr1 = bs2();
                        if (st<st1) {
                                // we have pre plateu
                                update(1,1,n,st,st1-1,1);
                        }
                        int remaining = c-(st1-st);
                        int plateuend = dr1;
                        int plateustart = max(st1,dr1-remaining+1);
                        if (plateustart<=plateuend)
                                update(1,1,n,plateustart,plateuend,1);
                } else {
                        cin>>minh>>maxh;
                        pos = minh;
                        st = bs1();
                        pos = maxh;
                        dr = bs2();
                        if (st<=dr&&st!=-1) {
                                cout<<dr-st+1<<'\n';
                        } else {
                                cout<<0<<'\n';
                        }
                }
        }
        return 0;
}

• 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