oj.uz

Submission #66822

# Submission time Handle Problem Language Result Execution time Memory
66822 2018-08-12T11:25:06 Z Kubalionzzale Wall (IOI14_wall) C++14
61 / 100
 948 ms 263168 KB 
#include "wall.h"

#include <vector>
#include <iostream>
#include <algorithm>
#include <set>
#include <bitset>

int lowSeg[8000010] = { 0 }, highSeg[8000010] = { 0 };
int ans[2000010] = { 0 };
std::bitset<8000010> visited = { 0 };

void construct(int low, int high, int pos)
{
    if (low == high)
    {
        lowSeg[pos] = 0;
        highSeg[pos] = 0;
        return;
    }

    lowSeg[pos] = 1e6;
    highSeg[pos] = -1;

    int mid = low + (high - low) / 2;

    construct(low, mid, pos * 2 + 1);
    construct(mid + 1, high, pos * 2 + 2);
}

void update(int low, int high, int qlow, int qhigh, int value, int oper, int pos)
{
    if (low > qhigh || high < qlow)
        return;

    if (qlow <= low && high <= qhigh)
    {
        if (oper == 2)
        {
            lowSeg[pos] = std::min(lowSeg[pos], value);
        }
        else
        {
            highSeg[pos] = std::max(highSeg[pos], value);
        }

        if (lowSeg[pos] < highSeg[pos])
        {
            lowSeg[pos] = value;
            highSeg[pos] = value;
        }

        int next1 = pos * 2 + 1;
        int next2 = pos * 2 + 2;

        if (low != high)
        {
            if (lowSeg[pos] <= highSeg[next1])
            {
                lowSeg[next1] = lowSeg[pos];
                highSeg[next1] = lowSeg[pos];
            }
            else if (highSeg[pos] >= lowSeg[next1])
            {
                lowSeg[next1] = highSeg[pos];
                highSeg[next1] = highSeg[pos];
            }
            else
            {
                lowSeg[next1] = std::min(lowSeg[next1], lowSeg[pos]);
                highSeg[next1] = std::max(highSeg[next1], highSeg[pos]);
            }

            if (lowSeg[pos] <= highSeg[next2])
            {
                lowSeg[next2] = lowSeg[pos];
                highSeg[next2] = lowSeg[pos];
            }
            else if (highSeg[pos] >= lowSeg[next2])
            {
                lowSeg[next2] = highSeg[pos];
                highSeg[next2] = highSeg[pos];
            }
            else
            {
                lowSeg[next2] = std::min(lowSeg[next2], lowSeg[pos]);
                highSeg[next2] = std::max(highSeg[next2], highSeg[pos]);
            }

            lowSeg[pos] = 1e6;
            highSeg[pos] = -1;
        }
        return;
    }

    int next1 = pos * 2 + 1;
    int next2 = pos * 2 + 2;

    if (lowSeg[pos] <= highSeg[next1])
    {
        lowSeg[next1] = lowSeg[pos];
        highSeg[next1] = lowSeg[pos];
    }
    else if (highSeg[pos] >= lowSeg[next1])
    {
        lowSeg[next1] = highSeg[pos];
        highSeg[next1] = highSeg[pos];
    }
    else
    {
        lowSeg[next1] = std::min(lowSeg[next1], lowSeg[pos]);
        highSeg[next1] = std::max(highSeg[next1], highSeg[pos]);
    }

    if (lowSeg[pos] <= highSeg[next2])
    {
        lowSeg[next2] = lowSeg[pos];
        highSeg[next2] = lowSeg[pos];
    }
    else if (highSeg[pos] >= lowSeg[next2])
    {
        lowSeg[next2] = highSeg[pos];
        highSeg[next2] = highSeg[pos];
    }
    else
    {
        lowSeg[next2] = std::min(lowSeg[next2], lowSeg[pos]);
        highSeg[next2] = std::max(highSeg[next2], highSeg[pos]);
    }

    lowSeg[pos] = 1e6;
    highSeg[pos] = -1;

    int mid = low + (high - low) / 2;

    update(low, mid, qlow, qhigh, value, oper, next1);
    update(mid + 1, high, qlow, qhigh, value, oper, next2);
}

void spread(int low, int high, int pos)
{
    if (low == high)
    {
        ans[low] = lowSeg[pos];
        return;
    }

    int next1 = pos * 2 + 1;
    int next2 = pos * 2 + 2;

    if (lowSeg[pos] <= highSeg[next1])
    {
        lowSeg[next1] = lowSeg[pos];
        highSeg[next1] = lowSeg[pos];
    }
    else if (highSeg[pos] >= lowSeg[next1])
    {
        lowSeg[next1] = highSeg[pos];
        highSeg[next1] = highSeg[pos];
    }
    else
    {
        lowSeg[next1] = std::min(lowSeg[next1], lowSeg[pos]);
        highSeg[next1] = std::max(highSeg[next1], highSeg[pos]);
    }

    if (lowSeg[pos] <= highSeg[next2])
    {
        lowSeg[next2] = lowSeg[pos];
        highSeg[next2] = lowSeg[pos];
    }
    else if (highSeg[pos] >= lowSeg[next2])
    {
        lowSeg[next2] = highSeg[pos];
        highSeg[next2] = highSeg[pos];
    }
    else
    {
        lowSeg[next2] = std::min(lowSeg[next2], lowSeg[pos]);
        highSeg[next2] = std::max(highSeg[next2], highSeg[pos]);
    }

    int mid = low + (high - low) / 2;

    spread(low, mid, next1);
    spread(mid + 1, high, next2);
}

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

    construct(0, n - 1, 0);
    for (int i = 0; i < k; ++i)
    {
        update(0, n - 1, left[i], right[i], height[i], op[i], 0);
    }

    spread(0, n - 1, 0);
    for (int i = 0; i < n; ++i)
    {
        finalHeight[i] = ans[i];
    }
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 352 KB Output is correct
2 Correct 4 ms 488 KB Output is correct
3 Correct 5 ms 600 KB Output is correct
4 Correct 16 ms 1256 KB Output is correct
5 Correct 8 ms 1420 KB Output is correct
6 Correct 8 ms 1504 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1504 KB Output is correct
2 Correct 179 ms 14736 KB Output is correct
3 Correct 219 ms 14736 KB Output is correct
4 Correct 641 ms 31280 KB Output is correct
5 Correct 417 ms 41952 KB Output is correct
6 Correct 347 ms 50620 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 50620 KB Output is correct
2 Correct 6 ms 50620 KB Output is correct
3 Correct 4 ms 50620 KB Output is correct
4 Correct 9 ms 50620 KB Output is correct
5 Correct 10 ms 50620 KB Output is correct
6 Correct 11 ms 50620 KB Output is correct
7 Correct 3 ms 50620 KB Output is correct
8 Correct 181 ms 53260 KB Output is correct
9 Correct 207 ms 53260 KB Output is correct
10 Correct 710 ms 69624 KB Output is correct
11 Correct 416 ms 80208 KB Output is correct
12 Correct 361 ms 88900 KB Output is correct
13 Correct 2 ms 88900 KB Output is correct
14 Correct 223 ms 91228 KB Output is correct
15 Correct 47 ms 91228 KB Output is correct
16 Correct 893 ms 104832 KB Output is correct
17 Correct 437 ms 113772 KB Output is correct
18 Correct 388 ms 122772 KB Output is correct

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 122772 KB Output is correct
2 Correct 4 ms 122772 KB Output is correct
3 Correct 5 ms 122772 KB Output is correct
4 Correct 10 ms 122772 KB Output is correct
5 Correct 8 ms 122772 KB Output is correct
6 Correct 10 ms 122772 KB Output is correct
7 Correct 2 ms 122772 KB Output is correct
8 Correct 240 ms 125748 KB Output is correct
9 Correct 225 ms 125748 KB Output is correct
10 Correct 648 ms 142196 KB Output is correct
11 Correct 385 ms 152852 KB Output is correct
12 Correct 465 ms 161496 KB Output is correct
13 Correct 4 ms 161496 KB Output is correct
14 Correct 198 ms 163792 KB Output is correct
15 Correct 49 ms 163792 KB Output is correct
16 Correct 891 ms 177236 KB Output is correct
17 Correct 385 ms 186384 KB Output is correct
18 Correct 346 ms 195396 KB Output is correct
19 Correct 948 ms 259808 KB Output is correct
20 Runtime error 913 ms 263168 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
21 Halted 0 ms 0 KB -