oj.uz

Submission #66823

# Submission time Handle Problem Language Result Execution time Memory
66823 2018-08-12T11:26:11 Z Kubalionzzale Wall (IOI14_wall) C++14
100 / 100
 938 ms 175004 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 3 ms 376 KB Output is correct
2 Correct 6 ms 620 KB Output is correct
3 Correct 5 ms 680 KB Output is correct
4 Correct 10 ms 1008 KB Output is correct
5 Correct 11 ms 1128 KB Output is correct
6 Correct 8 ms 1280 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1280 KB Output is correct
2 Correct 186 ms 14364 KB Output is correct
3 Correct 236 ms 14364 KB Output is correct
4 Correct 627 ms 17276 KB Output is correct
5 Correct 349 ms 17836 KB Output is correct
6 Correct 471 ms 17836 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 17836 KB Output is correct
2 Correct 4 ms 17836 KB Output is correct
3 Correct 5 ms 17836 KB Output is correct
4 Correct 10 ms 17836 KB Output is correct
5 Correct 8 ms 17836 KB Output is correct
6 Correct 8 ms 17836 KB Output is correct
7 Correct 2 ms 17836 KB Output is correct
8 Correct 175 ms 17836 KB Output is correct
9 Correct 222 ms 17836 KB Output is correct
10 Correct 657 ms 17836 KB Output is correct
11 Correct 326 ms 17856 KB Output is correct
12 Correct 385 ms 17912 KB Output is correct
13 Correct 2 ms 17912 KB Output is correct
14 Correct 227 ms 17912 KB Output is correct
15 Correct 43 ms 17912 KB Output is correct
16 Correct 938 ms 17912 KB Output is correct
17 Correct 390 ms 17912 KB Output is correct
18 Correct 393 ms 17912 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 17912 KB Output is correct
2 Correct 4 ms 17912 KB Output is correct
3 Correct 4 ms 17912 KB Output is correct
4 Correct 11 ms 17912 KB Output is correct
5 Correct 12 ms 17912 KB Output is correct
6 Correct 8 ms 17912 KB Output is correct
7 Correct 3 ms 17912 KB Output is correct
8 Correct 201 ms 17912 KB Output is correct
9 Correct 243 ms 17912 KB Output is correct
10 Correct 671 ms 17912 KB Output is correct
11 Correct 363 ms 17960 KB Output is correct
12 Correct 328 ms 17960 KB Output is correct
13 Correct 3 ms 17960 KB Output is correct
14 Correct 172 ms 17960 KB Output is correct
15 Correct 56 ms 17960 KB Output is correct
16 Correct 811 ms 17960 KB Output is correct
17 Correct 391 ms 17960 KB Output is correct
18 Correct 324 ms 17960 KB Output is correct
19 Correct 809 ms 73112 KB Output is correct
20 Correct 909 ms 73112 KB Output is correct
21 Correct 860 ms 83420 KB Output is correct
22 Correct 844 ms 91296 KB Output is correct
23 Correct 856 ms 101968 KB Output is correct
24 Correct 790 ms 112404 KB Output is correct
25 Correct 885 ms 122768 KB Output is correct
26 Correct 896 ms 135772 KB Output is correct
27 Correct 862 ms 146248 KB Output is correct
28 Correct 882 ms 154180 KB Output is correct
29 Correct 907 ms 164720 KB Output is correct
30 Correct 868 ms 175004 KB Output is correct