제출 #749706

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
749706		adrilen	벽 (IOI14_wall)	C++17	24 / 100	537 ms	36968 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;

struct Node {
    int val;
    bool empty, is_max, fini;

    void comp(const Node &other) {

        if (other.empty) return ;

        if (empty || other.fini) {
            val = other.val, empty = other.empty, is_max = other.is_max, fini = other.fini;

        }
        else if (is_max)
        {
            if (other.is_max)
            {
                val = max(val, other.val);
            } else {
                if (other.val < val)
                {
                    val = other.val;
                    is_max = false;
                    fini = true;
                }
            }
        } else {
            if (other.is_max)
            {
                if (other.val > val)
                {
                    val = other.val;
                    is_max = true;
                    fini = true;
                } 
            } else {
                val = min(val, other.val);
            }
        }
    }
} ;

Node defa = Node{0, true, false, false};

Node segtree[siz * 2] = { 0 };


void propogate(int pos)
{
    segtree[pos * 2].comp(segtree[pos]);
    segtree[pos * 2 + 1].comp(segtree[pos]);

    segtree[pos] = defa;
}

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

    // Inside
    if (gl <= l && r <= gr)
    {
        segtree[pos].comp(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 ;
    // cout << pos << endl;

    if (segtree[pos].fini)
    {
        for (int i = l; i <= r; i++) output[i] = segtree[pos].val;
        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 = 1; i < siz; i++) segtree[i].empty = true;
    for (int i = siz; i < siz + n; i++) segtree[i].fini = true;

    for (int i = 0; i < k; i++)
    {
        // cout << i << "\n";
        update(1, 0, siz - 1, left[i], right[i], Node{height[i], false, (bool)(op[i] & 1), false});
        // for (int i = 1; i < 2 * siz; i++)
        // {
        //     if (__builtin_popcount(i) == 1) cout << "\n";
        //     cout << segtree[i].val << " " << segtree[i].is_max << " " << segtree[i].empty << " " << segtree[i].fini << "    ";
        // }
        // cout << "\n\n";
    }

    fnd_answers(1, 0, siz - 1, 0, n - 1);

    for (int i = 0; i < n; i++) finalHeight[i] = output[i];
    return ;
}

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