제출 #372361

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
372361		idk321	벽 (IOI14_wall)	C++11	100 / 100	1274 ms	59500 KiB

wall

#include "wall.h"

#include <bits/stdc++.h>
using namespace std;

const int N = 2000005;
const int M = 1000000000;
int tree[4 * N][2];

void apply(int node, array<int, 2>& make)
{
    if (tree[node][0] <= make[0])
    {
        tree[node][0] = max(make[0], tree[node][0]);
        tree[node][1] = max(min(make[1], tree[node][1]), tree[node][0]);
    } else
    {
        tree[node][1] = min(make[1], tree[node][1]);
        tree[node][0] = min(max(make[0], tree[node][0]), tree[node][1]);
    }

}

void push(int node)
{
    array<int, 2> temp = {tree[node][0], tree[node][1]};
    for (int i = 0; i <= 1; i++) apply(node * 2 + i, temp);
    tree[node][0] = -1;
    tree[node][1] = M;
}

void ins(int from, int to, array<int, 2>& make, int a, int b, int node)
{
    if (from <= a && b <= to)
    {
        apply(node, make);
        return;
    }

    int mid = (a + b) / 2;
    push(node);
    if (from <= mid) ins(from, to, make, a, mid, node * 2);
    if (to > mid) ins(from, to, make, mid + 1, b, node * 2 +1);
}

int getRes(int i, int a, int b, int node)
{
    if (a == b) return tree[node][0];

    int mid = (a + b) / 2;
    push(node);
    if (i <= mid) return getRes(i, a, mid, node * 2);
    return getRes(i, mid + 1, b, node * 2 + 1);
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
    for (int i = 0; i < k; i++)
    {
        int a = left[i];
        int b = right[i];
        array<int, 2> make = {};
        make[0] = -1;
        make[1] = M;
        if (op[i] == 1)
        {
            make[0] = height[i];
        } else make[1] = height[i];
        ins(a, b, make, 0, n - 1, 1);
    }

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

• Subtask 1: 8 / 8
• Subtask 2: 24 / 24
• Subtask 3: 29 / 29
• Subtask 4: 39 / 39