Submission #66823

#	Time	Username	Problem	Language	Result	Execution time	Memory
66823		Kubalionzzale	Wall (IOI14_wall)	C++14	100 / 100	938 ms	175004 KiB

wall

#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 / 8
• Subtask 2: 24 / 24
• Subtask 3: 29 / 29
• Subtask 4: 39 / 39