Submission #583745

#	Time	Username	Problem	Language	Result	Execution time	Memory
583745		Drew_	Wall (IOI14_wall)	C++17	100 / 100	660 ms	69452 KiB

wall

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

#define mp make_pair
#define f1 first
#define s2 second

using ii = pair<int, int>;

const int MAX = 2e6 + 69;
const int inf = 1e9 + 69;

ii st[1 << 22]; // [up, down]
void add(int p, int q, int u, int d, int node, int l, int r)
{
    if (l > q || r < p)
        return;
    if (p <= l && r <= q)
    {
        st[node].f1 = max(st[node].f1, u);
        st[node].s2 = max(st[node].s2, u);
        st[node].f1 = min(st[node].f1, d);
        st[node].s2 = min(st[node].s2, d);
        return;
    }

    int mid = (l + r) >> 1;    
    st[node << 1].f1 = max(st[node << 1].f1, st[node].f1);
    st[node << 1].f1 = min(st[node << 1].f1, st[node].s2);
    st[node << 1].s2 = max(st[node << 1].s2, st[node].f1);
    st[node << 1].s2 = min(st[node << 1].s2, st[node].s2);

    st[node << 1 | 1].f1 = max(st[node << 1 | 1].f1, st[node].f1);
    st[node << 1 | 1].f1 = min(st[node << 1 | 1].f1, st[node].s2);
    st[node << 1 | 1].s2 = max(st[node << 1 | 1].s2, st[node].f1);
    st[node << 1 | 1].s2 = min(st[node << 1 | 1].s2, st[node].s2);

    st[node] = { 0, inf };

    add(p, q, u, d, node << 1, l, mid);
    add(p, q, u, d, node << 1 | 1, mid+1, r);
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[])
{
    fill(st, st + (1 << 22), mp(0, inf));
    for (int i = 0; i < k; ++i)
    {
        if (op[i] == 1)
            add(left[i], right[i], height[i], inf, 1, 0, n-1);
        else add(left[i], right[i], 0, height[i], 1, 0, n-1);
    }

    const auto getAns = [&](const auto &self, int node, int l, int r) -> void
    {
        if (l == r)
        {
            finalHeight[l] = min(st[node].f1, st[node].s2);
            return;
        }
        int mid = (l + r) >> 1;
        st[node << 1].f1 = max(st[node << 1].f1, st[node].f1);
        st[node << 1].f1 = min(st[node << 1].f1, st[node].s2);
        st[node << 1].s2 = max(st[node << 1].s2, st[node].f1);
        st[node << 1].s2 = min(st[node << 1].s2, st[node].s2);

        st[node << 1 | 1].f1 = max(st[node << 1 | 1].f1, st[node].f1);
        st[node << 1 | 1].f1 = min(st[node << 1 | 1].f1, st[node].s2);
        st[node << 1 | 1].s2 = max(st[node << 1 | 1].s2, st[node].f1);
        st[node << 1 | 1].s2 = min(st[node << 1 | 1].s2, st[node].s2);

        st[node] = { 0, inf };

        self(self, node << 1, l, mid);
        self(self, node << 1 | 1, mid+1, r);
    };
    getAns(getAns, 1, 0, n-1);

    return;
}

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