Submission #1016891

#	Time	Username	Problem	Language	Result	Execution time	Memory
1016891		simona1230	Wall (IOI14_wall)	C++17	100 / 100	710 ms	84100 KiB

wall

#include "wall.h"
#include "bits/stdc++.h"
using namespace std;

struct node
{
    int l,r;
    int v1,v2;
    node() {}
    node(int lf,int rt,int _v1,int _v2)
    {
        l=lf;
        r=rt;
        v1=_v1;
        v2=_v2;
    }
};

int a[2000001],b[2000001];
struct tree
{
    vector<node> t= {{-1,-1,0,(int)1e9}};
    tree() {}
    void children(int i)
    {
        t.push_back({-1,-1,0,(int)1e9});
        t[i].l=t.size()-1;
        t.push_back({-1,-1,0,(int)1e9});
        t[i].r=t.size()-1;
    }

    void push_lazy(int i,int l,int r)
    {
        if(l==r)return;

        if(t[i].l==-1)children(i);

        int i1=t[i].l,i2=t[i].r;

        //cout<<l<<" "<<r<<" "<<t[i].v1<<" "<<t[i].v2<<endl;
        //cout<<t[i1].v1<<" "<<t[i1].v2<<endl;
        if(t[i].v1>t[i1].v2)
        {
            t[i1].v1=t[i1].v2=t[i].v1;
        }
        else if(t[i].v2<t[i1].v1)
        {
            t[i1].v1=t[i1].v2=t[i].v2;
        }
        else
        {
            t[i1].v1=max(t[i].v1,t[i1].v1);
            t[i1].v2=min(t[i].v2,t[i1].v2);
        }

        if(t[i].v1>t[i2].v2)
        {
            t[i2].v1=t[i2].v2=t[i].v1;
        }
        else if(t[i].v2<t[i2].v1)
        {
            t[i2].v1=t[i2].v2=t[i].v2;
        }
        else
        {
            t[i2].v1=max(t[i].v1,t[i2].v1);
            t[i2].v2=min(t[i].v2,t[i2].v2);
        }
        //cout<<t[i1].v1<<" "<<t[i1].v2<<endl;

        t[i].v1=0;
        t[i].v2=1e9;
    }

    void update(int i,int l,int r,int ql,int qr,int val,int type)
    {
        push_lazy(i,l,r);
        if(ql>qr)return;

        if(ql<=l&&r<=qr)
        {
            if(type==1)
            {
                if(val>t[i].v2)
                {
                    t[i].v1=val;
                    t[i].v2=val;
                }
                else
                {
                    //cout<<"in"<<endl;
                    t[i].v1=max(t[i].v1,val);
                }
            }
            else
            {
                if(t[i].v1>val)
                {
                    t[i].v1=val;
                    t[i].v2=val;
                }
                else t[i].v2=min(t[i].v2,val);
            }
            push_lazy(i,l,r);
            //cout<<i<<" "<<t[i].v1<<" "<<t[i].v2<<endl;
            return;
        }
        int m=(l+r)/2;
        if(t[i].l==-1)children(i);
        update(t[i].l,l,m,ql,min(qr,m),val,type);
        update(t[i].r,m+1,r,max(ql,m+1),qr,val,type);
    }

    void fix(int i,int l,int r)
    {
        if(t[i].l==-1)
        {
            //cout<<i<<endl;
            for(int j=l;j<=r;j++)
                a[j]=t[i].v1;
            return;
        }
        //cout<<l<<" "<<r<<endl;
        push_lazy(i,l,r);
        int m=(l+r)/2;
        fix(t[i].l,l,m);
        fix(t[i].r,m+1,r);
    }
};

tree t;

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[])
{
    for(int i=0; i<k; i++)
    {
        //cout<<height[i]<<" "<<op[i]<<endl;
        t.update(0,0,n-1,left[i],right[i],height[i],op[i]);
        //cout<<endl;
    }

    t.fix(0,0,n-1);
    for(int i=0; i<n; i++)
        finalHeight[i]=a[i];
}
/*
10 1
1 0 9 1
*/

• Subtask 1: 8 / 8
• Subtask 2: 24 / 24
• Subtask 3: 29 / 29
• Subtask 4: 39 / 39