oj.uz

Submission #66824

# Submission time Handle Problem Language Result Execution time Memory
66824 2018-08-12T11:26:48 Z Kubalionzzale Wall (IOI14_wall) C++14
100 / 100
 1004 ms 67264 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 };

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 376 KB Output is correct
2 Correct 4 ms 492 KB Output is correct
3 Correct 4 ms 572 KB Output is correct
4 Correct 9 ms 904 KB Output is correct
5 Correct 8 ms 1180 KB Output is correct
6 Correct 10 ms 1180 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1180 KB Output is correct
2 Correct 177 ms 8480 KB Output is correct
3 Correct 240 ms 8480 KB Output is correct
4 Correct 626 ms 11536 KB Output is correct
5 Correct 373 ms 12176 KB Output is correct
6 Correct 388 ms 12176 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12176 KB Output is correct
2 Correct 4 ms 12176 KB Output is correct
3 Correct 4 ms 12176 KB Output is correct
4 Correct 11 ms 12176 KB Output is correct
5 Correct 7 ms 12176 KB Output is correct
6 Correct 9 ms 12176 KB Output is correct
7 Correct 2 ms 12176 KB Output is correct
8 Correct 174 ms 12176 KB Output is correct
9 Correct 210 ms 12176 KB Output is correct
10 Correct 618 ms 12176 KB Output is correct
11 Correct 396 ms 12176 KB Output is correct
12 Correct 377 ms 12176 KB Output is correct
13 Correct 3 ms 12176 KB Output is correct
14 Correct 192 ms 12176 KB Output is correct
15 Correct 68 ms 12176 KB Output is correct
16 Correct 992 ms 12176 KB Output is correct
17 Correct 432 ms 12176 KB Output is correct
18 Correct 401 ms 12176 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12176 KB Output is correct
2 Correct 4 ms 12176 KB Output is correct
3 Correct 5 ms 12176 KB Output is correct
4 Correct 12 ms 12176 KB Output is correct
5 Correct 7 ms 12176 KB Output is correct
6 Correct 8 ms 12176 KB Output is correct
7 Correct 2 ms 12176 KB Output is correct
8 Correct 203 ms 12176 KB Output is correct
9 Correct 197 ms 12176 KB Output is correct
10 Correct 610 ms 12176 KB Output is correct
11 Correct 395 ms 12176 KB Output is correct
12 Correct 381 ms 12212 KB Output is correct
13 Correct 3 ms 12212 KB Output is correct
14 Correct 182 ms 12212 KB Output is correct
15 Correct 42 ms 12212 KB Output is correct
16 Correct 905 ms 12212 KB Output is correct
17 Correct 373 ms 12212 KB Output is correct
18 Correct 392 ms 12212 KB Output is correct
19 Correct 810 ms 67124 KB Output is correct
20 Correct 858 ms 67124 KB Output is correct
21 Correct 817 ms 67124 KB Output is correct
22 Correct 867 ms 67124 KB Output is correct
23 Correct 1004 ms 67124 KB Output is correct
24 Correct 885 ms 67124 KB Output is correct
25 Correct 806 ms 67124 KB Output is correct
26 Correct 895 ms 67264 KB Output is correct
27 Correct 797 ms 67264 KB Output is correct
28 Correct 842 ms 67264 KB Output is correct
29 Correct 785 ms 67264 KB Output is correct
30 Correct 836 ms 67264 KB Output is correct