제출 #752570

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
752570		adrilen	벽 (IOI14_wall)	C++17	100 / 100	649 ms	72784 KiB

wall

#include "wall.h"
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
typedef pair<int, int> pii;
constexpr int maxn = 2e6 + 5, bit = 32 - __builtin_clz(maxn), siz = 1 << bit, max_val = 1e9;

const array<int, 2> defa = {0, max_val};

array<int, 2> segtree[siz * 2] = { 0 };

void comp(array<int, 2> &lower, const array<int,2>&over)
{
    if (over[1] < lower[0])
    {
        lower[0] = lower[1] = over[1];
    } else if (over[0] > lower[1])
    {
        lower[0] = lower[1] = over[0];
    } else if (lower[0] <= over[0] && over[1] <= lower[1]) {
        lower = over;
    } else {
        lower[0] = max(lower[0], over[0]);
        lower[1] = min(lower[1], over[1]);
    }
}

void propogate(int p)
{
    comp(segtree[p * 2], segtree[p]);
    comp(segtree[p * 2 + 1], segtree[p]);
    segtree[p] = defa;
}

void update(int pos, int l, int r, int gl, int gr, array<int, 2> p)
{
    if (gl > r || l > gr) return ;

    // Inside
    if (gl <= l && r <= gr)
    {
        comp(segtree[pos], p);
        return ;
    }

    propogate(pos);
    int mid = (l + r) >> 1;
    update(pos * 2, l, mid, gl, gr, p);
    update(pos * 2 + 1, mid + 1, r, gl, gr, p);
}

int output[maxn] = { 0 };

void fnd_answers(int pos, int l, int r, int gl, int gr)
{
    if (l > gr || gl > r) return ;

    if (segtree[pos][0] == segtree[pos][1])
    {
        for (int i = l; i <= r; i++) output[i] = segtree[pos][0];
        // cout << "finished: " <<l  << " " << r << "\n";
        return ;
    }

    propogate(pos);
    int mid = (l + r) >> 1;
    fnd_answers(pos * 2, l, mid, gl, gr);
    fnd_answers(pos * 2 + 1, mid + 1, r, gl, gr);
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
    for (int i = 0; i < siz; i++) segtree[i][1] = max_val;

    array<int, 2> p;
    for (int i = 0; i < k; i++)
    {
        // Min
        if (op[i] == 1) p[0] = height[i], p[1] = max_val;
        // Max
        else p[0] = 0, p[1] = height[i];
        update(1, 0, siz - 1, left[i], right[i], p);

        // cout << i << "\n";
        // for (int i = 1; i < 2 * siz; i++)
        // {
        //     if (__builtin_popcount(i) == 1) cout << "\n";
        //     cout << segtree[i][0] << " " << segtree[i][1] << "\t";
        // }
        // cout << endl << endl;
    }

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

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