oj.uz

Submission #7535

# Submission time Handle Problem Language Result Execution time Memory
7535 2014-08-10T13:02:09 Z baneling100 Wall (IOI14_wall) C++
100 / 100
 876 ms 49496 KB 
#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.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 33856 KB Output is correct
2 Correct 0 ms 33856 KB Output is correct
3 Correct 0 ms 33856 KB Output is correct
4 Correct 4 ms 33856 KB Output is correct
5 Correct 4 ms 33856 KB Output is correct
6 Correct 4 ms 33856 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 33856 KB Output is correct
2 Correct 172 ms 41680 KB Output is correct
3 Correct 248 ms 37104 KB Output is correct
4 Correct 688 ms 42072 KB Output is correct
5 Correct 368 ms 42072 KB Output is correct
6 Correct 376 ms 42072 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 33856 KB Output is correct
2 Correct 0 ms 33856 KB Output is correct
3 Correct 0 ms 33856 KB Output is correct
4 Correct 4 ms 33856 KB Output is correct
5 Correct 4 ms 33856 KB Output is correct
6 Correct 0 ms 33856 KB Output is correct
7 Correct 0 ms 33856 KB Output is correct
8 Correct 168 ms 41680 KB Output is correct
9 Correct 248 ms 37104 KB Output is correct
10 Correct 696 ms 42072 KB Output is correct
11 Correct 384 ms 42072 KB Output is correct
12 Correct 356 ms 42072 KB Output is correct
13 Correct 0 ms 33856 KB Output is correct
14 Correct 172 ms 41680 KB Output is correct
15 Correct 36 ms 34340 KB Output is correct
16 Correct 740 ms 42072 KB Output is correct
17 Correct 380 ms 42072 KB Output is correct
18 Correct 376 ms 42072 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 33856 KB Output is correct
2 Correct 0 ms 33856 KB Output is correct
3 Correct 0 ms 33856 KB Output is correct
4 Correct 8 ms 33856 KB Output is correct
5 Correct 4 ms 33856 KB Output is correct
6 Correct 4 ms 33856 KB Output is correct
7 Correct 0 ms 33856 KB Output is correct
8 Correct 184 ms 41680 KB Output is correct
9 Correct 248 ms 37104 KB Output is correct
10 Correct 676 ms 42072 KB Output is correct
11 Correct 392 ms 42072 KB Output is correct
12 Correct 380 ms 42072 KB Output is correct
13 Correct 0 ms 33856 KB Output is correct
14 Correct 176 ms 41680 KB Output is correct
15 Correct 44 ms 34340 KB Output is correct
16 Correct 728 ms 42072 KB Output is correct
17 Correct 368 ms 42072 KB Output is correct
18 Correct 384 ms 42072 KB Output is correct
19 Correct 856 ms 49496 KB Output is correct
20 Correct 848 ms 49496 KB Output is correct
21 Correct 876 ms 49496 KB Output is correct
22 Correct 820 ms 49496 KB Output is correct
23 Correct 868 ms 49496 KB Output is correct
24 Correct 836 ms 49496 KB Output is correct
25 Correct 844 ms 49496 KB Output is correct
26 Correct 840 ms 49496 KB Output is correct
27 Correct 840 ms 49496 KB Output is correct
28 Correct 856 ms 49496 KB Output is correct
29 Correct 816 ms 49496 KB Output is correct
30 Correct 856 ms 49496 KB Output is correct