Submission #7535

#	Time	Username	Problem	Language	Result	Execution time	Memory
7535		baneling100	Wall (IOI14_wall)	C++98	100 / 100	876 ms	49496 KiB

wall

#include "wall.h"
#define INF 0x7fffffff

int N, M, Idx[4194304][2], LeftBound, RightBound, Height;

void ReNewPlus(int Now)
{
    if(Idx[Now][0]>Idx[Now][1])
        Idx[Now][1]=Idx[Now][0];
}

void ReNewMinus(int Now)
{
    if(Idx[Now][0]>Idx[Now][1])
        Idx[Now][0]=Idx[Now][1];
}

void Spray(int Now)
{
    if(Idx[2*Now][0]<Idx[Now][0])
        Idx[2*Now][0]=Idx[Now][0];
    ReNewPlus(2*Now);
    if(Idx[2*Now][1]>Idx[Now][1])
        Idx[2*Now][1]=Idx[Now][1];
    ReNewMinus(2*Now);
    if(Idx[2*Now+1][0]<Idx[Now][0])
        Idx[2*Now+1][0]=Idx[Now][0];
    ReNewPlus(2*Now+1);
    if(Idx[2*Now+1][1]>Idx[Now][1])
        Idx[2*Now+1][1]=Idx[Now][1];
    ReNewMinus(2*Now+1);
    Idx[Now][0]=0;
    Idx[Now][1]=INF;
}

void IdxPlus(int Left, int Right, int Now)
{
    int Mid;

    if(LeftBound<=Left && Right<=RightBound)
    {
        if(Idx[Now][0]<Height)
            Idx[Now][0]=Height;
        ReNewPlus(Now);
    }
    else
    {
        Spray(Now);
        Mid=(Left+Right)/2;
        if(LeftBound<=Mid)
            IdxPlus(Left,Mid,2*Now);
        if(Mid+1<=RightBound)
            IdxPlus(Mid+1,Right,2*Now+1);
    }
}

void IdxMinus(int Left, int Right, int Now)
{
    int Mid;

    if(LeftBound<=Left && Right<=RightBound)
    {
        if(Idx[Now][1]>Height)
            Idx[Now][1]=Height;
        ReNewMinus(Now);
    }
    else
    {
        Spray(Now);
        Mid=(Left+Right)/2;
        if(LeftBound<=Mid)
            IdxMinus(Left,Mid,2*Now);
        if(Mid+1<=RightBound)
            IdxMinus(Mid+1,Right,2*Now+1);
    }
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[])
{
    int i;

    N=n;
    for(M=1 ; M<N ; M*=2);
    for(i=2 ; i<2*M ; i++)
        Idx[i][1]=INF;
    for(i=0 ; i<k ; i++)
    {
        LeftBound=left[i];
        RightBound=right[i];
        Height=height[i];
        if(op[i]==1)
            IdxPlus(0,M-1,1);
        else
            IdxMinus(0,M-1,1);
    }
    for(i=1 ; i<M ; i++)
        Spray(i);
    for(i=M ; i<M+N ; i++)
        finalHeight[i-M]=Idx[i][0];
}

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