Submission #1023595

#	Time	Username	Problem	Language	Result	Execution time	Memory
1023595		AtinaR	Growing Trees (BOI11_grow)	C++14	100 / 100	209 ms	5968 KiB

grow

#include <bits/stdc++.h>

using namespace std;
const int MAX=1e5+10;
int n,q;
int niza[MAX];
int treemin[4*MAX],treemax[4*MAX],lazy[4*MAX];
void build(int node, int L, int R)
{
    lazy[node]=0;
    if(L==R)
    {
        treemin[node]=niza[L];
        treemax[node]=niza[L];
        return;
    }
    int mid=(L+R)/2;
    build(2*node,L,mid);
    build(2*node+1,mid+1,R);
    treemin[node]=min(treemin[2*node],treemin[2*node+1]);
    treemax[node]=max(treemax[2*node],treemax[2*node+1]);
}
void push(int node, int L, int R)
{
    int mid=(L+R)/2;
    treemax[2*node]+=lazy[node];
    treemax[2*node+1]+=lazy[node];
    treemin[2*node]+=lazy[node];
    treemin[2*node+1]+=lazy[node];
    lazy[2*node]+=lazy[node];
    lazy[2*node+1]+=lazy[node];
    lazy[node]=0;
}
int firstx(int node, int L, int R, int x)///first at least x
{
    if(L==R)
    {
        return L;
    }
    push(node,L,R);
    int mid=(L+R)/2;
    if(treemax[2*node]>=x)return firstx(2*node,L,mid,x);
    else if(treemax[2*node+1]>=x)return firstx(2*node+1,mid+1,R,x);
    else return n;
}
int lastx(int node, int L, int R, int x)
{
    if(L==R)
    {
        return L;
    }
    push(node,L,R);
    int mid=(L+R)/2;
    if(treemin[2*node+1]<=x)return lastx(2*node+1,mid+1,R,x);
    else if(treemin[2*node]<=x)return lastx(2*node,L,mid,x);
    else return -1;
}
void update(int node, int L, int R, int _left, int _right, int val)
{
    if(L>=_left && R<=_right)
    {
        treemin[node]+=val;
        treemax[node]+=val;
        lazy[node]+=val;
        return;
    }
    if(L>_right || R<_left)return;
    push(node,L,R);
    int mid=(L+R)/2;
    update(2*node,L,mid,_left,_right,val);
    update(2*node+1,mid+1,R,_left,_right,val);
    treemin[node]=min(treemin[2*node],treemin[2*node+1]);
    treemax[node]=max(treemax[2*node],treemax[2*node+1]);
}
int get(int node, int L, int R, int x)
{
    if(L==R)
    {
        return treemin[node];
    }
    push(node,L,R);
    int mid=(L+R)/2;
    if(x>mid)return get(2*node+1,mid+1,R,x);
    else return get(2*node,L,mid,x);
}
int main()
{
    cin>>n>>q;
    for(int i=0; i<n; i++)
    {
        cin>>niza[i];
    }
    sort(niza,niza+n);
    //for(int i=0; i<n; i++)cout<<niza[i]<<" ";
    //cout<<endl;
    build(1,0,n-1);
    for(int i=0; i<q; i++)
    {
        char type;
        cin>>type;
        if(type=='F')
        {
            int c,h;
            cin>>c>>h;
            int lborder=firstx(1,0,n-1,h);
            if(lborder==n)continue;
            int rborder=min(n-1,lborder+c-1);
            //cout<<"l r: "<<lborder+1<<" "<<rborder+1<<endl;
            int elborder=get(1,0,n-1,rborder);
            int lastofthat=lastx(1,0,n-1,elborder);
            //cout<<"last of number: "<<elborder<<" is: "<<lastofthat+1<<endl;
            if(rborder==lastofthat)
            {
                //cout<<"get full range: "<<endl;
                update(1,0,n-1,lborder,rborder,1);
                continue;
            }
            elborder--;
            int prevlast=lastx(1,0,n-1,elborder);
            //cout<<"last of number: "<<elborder<<" is: "<<prevlast+1<<endl;
            update(1,0,n-1,lborder,prevlast,1);
            //cout<<"so updating from: "<<lborder+1<<" to: "<<prevlast+1<<endl;
            int leftt=c-(prevlast-lborder+1);
            int newl=lastofthat-leftt+1;
            //cout<<"and from: "<<newl+1<<" "<<lastofthat+1<<endl;
            update(1,0,n-1,newl,lastofthat,1);
        }
        else
        {
            int mnn,mxx;
            cin>>mnn>>mxx;
            int x=firstx(1,0,n-1,mnn);
            int y=lastx(1,0,n-1,mxx);
            if(x==n)
            {
                cout<<0<<endl;
                continue;
            }
            cout<<y-x+1<<endl;
        }
    }
    return 0;
}
/*
5
2 3 5 6 6
*/

Compilation message (stderr)

grow.cpp: In function 'void push(int, int, int)':
grow.cpp:25:9: warning: unused variable 'mid' [-Wunused-variable]
   25 |     int mid=(L+R)/2;
      |         ^~~

• 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