Submission #1016734

#	Time	Username	Problem	Language	Result	Execution time	Memory
1016734		vivkostov	Wall (IOI14_wall)	C++14	0 / 100	162 ms	16056 KiB

wall

#include<bits/stdc++.h>
#include "wall.h"
#define endl '\n'
using namespace std;
void speed()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}
int n,k,typ,le,ri,hie,otg[10000005],lazy[10000005],p[10000005],lazys[10000005],original[10000005];
void push_lazy(int h,int l,int r)
{
    if(lazys[h])
    {
        if(lazy[h*2]>lazys[h])
        {
            lazy[h*2]=lazys[h];
            p[h*2]=2;
            original[h*2]=2;
        }
        else
        {
            if(!lazys[h*2])lazys[h*2]=lazys[h];
            else lazys[h*2]=min(lazys[h*2],lazys[h]);
        }
        if(lazy[h*2+1]>lazys[h])
        {
            lazy[h*2+1]=lazys[h];
            p[h*2+1]=2;
            original[h*2+1]=2;
        }
        else
        {
            if(!lazys[h*2+1])lazys[h*2+1]=lazys[h];
            else lazys[h*2+1]=min(lazys[h*2+1],lazys[h]);
        }
        lazys[h]=0;
    }
    if(lazy[h]!=-1)
    {
        if(r-l==1)
        {
            if(p[h]==1)
            {
                lazy[h*2]=max(lazy[h],lazy[h*2]);
                lazy[h*2+1]=max(lazy[h],lazy[h*2+1]);
            }
            else
            {
                lazy[h*2]=min(lazy[h],lazy[h*2]);
                lazy[h*2+1]=min(lazy[h],lazy[h*2+1]);
            }
            lazy[h]=-1;
            p[h]=0;
            original[h]=0;
            return;
        }
        if(p[h]==1)
        {
            if(lazy[h*2]==-1)
            {
                lazy[h*2]=lazy[h];
                p[h*2]=1;
                original[h*2]=1;
            }
            else
            {
                if(original[h*2]==2)
                {
                    if(!lazys[h*2])lazys[h*2]=lazy[h*2];
                    else lazys[h*2]=min(lazys[h*2],lazy[h*2]);
                    lazy[h*2]=lazy[h];
                    p[h*2]=1;
                    original[h*2]=1;
                }
                else
                {
                    if(lazy[h]>lazy[h*2])
                    {
                        lazy[h*2]=lazy[h];
                    }
                }
            }
            if(lazy[h*2+1]==-1)
            {
                lazy[h*2+1]=lazy[h];
                p[h*2+1]=1;
                original[h*2+1]=1;
            }
            else
            {
                if(original[h*2+1]==2)
                {
                    if(!lazys[h*2])lazys[h*2+1]=lazy[h*2+1];
                    else lazys[h*2+1]=min(lazys[h*2+1],lazy[h*2+1]);
                    lazy[h*2+1]=lazy[h];
                    p[h*2+1]=1;
                    original[h*2+1]=1;
                }
                else
                {
                    if(lazy[h]>lazy[h*2+1])
                    {
                        lazy[h*2+1]=lazy[h];
                    }
                }
            }
        }
        else
        {
            if(lazy[h*2]==-1)
            {
                lazy[h*2]=lazy[h];
                p[h*2]=2;
                original[h*2]=2;
            }
            else
            {
                if(p[h*2]==1)
                {
                    if(lazy[h]<lazy[h*2])
                    {
                        lazy[h*2]=lazy[h];
                        p[h*2]=1;
                        original[h*2]=2;
                    }
                    else
                    {
                        if(!lazys[h*2])lazys[h*2]=lazy[h];
                        else lazys[h*2]=min(lazys[h*2],lazy[h]);
                    }
                }
                else
                {
                    lazy[h*2]=min(lazy[h],lazy[h*2]);
                }
            }
            if(lazy[h*2+1]==-1)
            {
                lazy[h*2+1]=lazy[h];
                p[h*2+1]=2;
                original[h*2+1]=2;
            }
            else
            {
                if(p[h*2+1]==1)
                {
                    if(lazy[h]<lazy[h*2+1])
                    {
                        lazy[h*2+1]=lazy[h];
                        p[h*2+1]=1;
                        original[h*2+1]=2;
                    }
                    else
                    {
                        if(!lazys[h*2+1])lazys[h*2+1]=lazy[h];
                        else lazys[h*2+1]=min(lazys[h*2+1],lazy[h]);
                    }
                }
                else
                {
                    lazy[h*2+1]=min(lazy[h],lazy[h*2+1]);
                }
            }
        }
        lazy[h]=-1;
        p[h]=0;
        original[h]=0;
    }
}
void make_start(int l,int r,int h)
{
    if(l==r)return;
    lazy[h]=-1;
    int m=(l+r)/2;
    make_start(l,m,h*2);
    make_start(m+1,r,h*2+1);
}
void update(int l,int r,int ql,int qr,int h,int hi,int type)
{
    if(l>qr||r<ql)return;
    if(l!=r)push_lazy(h,l,r);
    if(l>=ql&&r<=qr)
    {
        if(l==r)
        {
            if(type==1)lazy[h]=max(lazy[h],hi);
            else lazy[h]=min(lazy[h],hi);
            return;
        }
        lazy[h]=hi;
        p[h]=type;
        original[h]=type;
        //cout<<l<<" "<<r<<" "<<lazy[h]<<endl;
        return;
    }
    //cout<<l<<" "<<r<<" "<<lazy[h]<<endl;
    int m=(l+r)/2;
    update(l,m,ql,qr,h*2,hi,type);
    update(m+1,r,ql,qr,h*2+1,hi,type);
}
void print(int l,int r,int h)
{
    if(l==r)
    {
        otg[l]=lazy[h];
        return;
    }
    //cout<<l<<" "<<r<<" "<<lazy[h]<<" "<<p[h]<<endl;
    push_lazy(h,l,r);
    //cout<<l<<" "<<r<<" "<<lazy[h]<<" "<<p[h]<<endl;
    //cout<<endl;
    int m=(l+r)/2;
    print(l,m,h*2);
    print(m+1,r,h*2+1);
}
void buildWall(int n, int k, int type[], int le[], int ri[], int hi[], int finalHeight[])
{
    make_start(1,n,1);
    for(int i=0; i<k; i++)
    {
        le[i]++;
        ri[i]++;
        update(1,n,le[i],ri[i],1,hi[i],type[i]);
    }
    print(1,n,1);
    for(int i=1; i<=n; i++)
    {
        finalHeight[i-1]=otg[i];
    }
}
void read()
{
    cin>>n>>k;
    make_start(1,n,1);
    for(int i=1; i<=k; i++)
    {
        cin>>typ>>le>>ri>>hie;
        le++;
        ri++;
        update(1,n,le,ri,1,hie,typ);
    }
    print(1,n,1);
    for(int i=1; i<=n; i++)
    {
        cout<<otg[i]<<" ";
    }
    cout<<endl;
}
/*int main()
{
    speed();
    read();
    return 0;
}
*/

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