Submission #1209577

#	Time	Username	Problem	Language	Result	Execution time	Memory
1209577		badge881	Wall (IOI14_wall)	C++20	100 / 100	621 ms	92008 KiB

wall

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

const int INF = 1e9;

const pair<int, int> base = {INF, -INF};

void minimize(pair<int, int> &A, int t)
{
    A.first = min(A.first, t);
    A.second = min(A.first, A.second);
}

void maximize(pair<int, int> &A, int t)
{
    A.second = max(A.second, t);
    A.first = max(A.second, A.first);
}

const int maxn = 2e6 + 5;
int a[maxn];

struct Segtree
{
    pair<int, int> st[4 * maxn], lz[4 * maxn];

    void init(int id, int l, int r)
    {
        if (l == r)
            return st[id] = lz[id] = base, void();

        int mid = (l + r) >> 1;
        init(id * 2, l, mid);
        init(id * 2 + 1, mid + 1, r);

        st[id] = st[id * 2];
        minimize(st[id], st[id * 2 + 1].first);
        maximize(st[id], st[id * 2 + 1].second);
    }

    void push(int id)
    {
        pair<int, int> &t = lz[id];
        if (t == base)
            return;

        minimize(st[id * 2], t.first);
        maximize(st[id * 2], t.second);
        minimize(lz[id * 2], t.first);
        maximize(lz[id * 2], t.second);

        minimize(st[id * 2 + 1], t.first);
        maximize(st[id * 2 + 1], t.second);
        minimize(lz[id * 2 + 1], t.first);
        maximize(lz[id * 2 + 1], t.second);

        t = base;
    }

    void update(int id, int l, int r, int u, int v, int t, int type)
    {
        if (l == u && r == v)
        {
            if (type == 2)
                minimize(st[id], t),
                    minimize(lz[id], t);
            else
                maximize(st[id], t),
                    maximize(lz[id], t);
            return;
        }

        int mid = (l + r) >> 1;
        push(id);
        if (v <= mid)
            update(id * 2, l, mid, u, v, t, type);
        else if (u > mid)
            update(id * 2 + 1, mid + 1, r, u, v, t, type);
        else
        {
            update(id * 2, l, mid, u, mid, t, type);
            update(id * 2 + 1, mid + 1, r, mid + 1, v, t, type);
        }

        st[id] = st[id * 2];
        minimize(st[id], st[id * 2 + 1].first);
        maximize(st[id], st[id * 2 + 1].second);
    }

    pair<int, int> get(int id, int l, int r, int u, int v)
    {
        if (l == u && r == v)
            return st[id];

        int mid = (l + r) >> 1;
        push(id);
        if (v <= mid)
            return get(id * 2, l, mid, u, v);
        else if (u > mid)
            return get(id * 2 + 1, mid + 1, r, u, v);
        else
        {
            pair<int, int> L = get(id * 2, l, mid, u, mid);
            pair<int, int> R = get(id * 2 + 1, mid + 1, r, mid + 1, v);
            minimize(L, R.first);
            maximize(L, R.second);
            return L;
        }
    }
} Segtree;

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[])
{
    Segtree.init(1, 1, n);

    for (int i = 0; i < k; ++i)
        Segtree.update(1, 1, n, left[i] + 1, right[i] + 1, height[i], op[i]);

    for (int i = 0; i < n; ++i)
    {
        pair<int, int> get = Segtree.get(1, 1, n, i + 1, i + 1);
        finalHeight[i] = get.second;
    }

    return;
}

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