제출 #832280

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
832280		JoenPoenMan	벽 (IOI14_wall)	C++17	24 / 100	501 ms	27668 KiB

wall

#include <bits/stdc++.h>
#include "wall.h"

using namespace std;
#define INF 1e6

struct Tree {
    int l, r, v = 0, lazyAdd = -1, lazyRem = INF;
    bool addFirst = true;
    Tree *lptr = NULL, *rptr = NULL;

    Tree(int n) : l(0), r(n-1) {};
    Tree(int _l, int _r) : l(_l), r(_r) {};

    void push(Tree *p) {
        int p_lazyAdd = p->lazyAdd, p_lazyRem = p->lazyRem;
        bool p_addFirst = p->addFirst;

        if (lazyAdd == -1 && lazyRem == INF) {
            lazyAdd = p_lazyAdd;
            lazyRem = p_lazyRem;
            addFirst = p_addFirst;
        } else if (p_lazyAdd == -1 && p_lazyRem == INF) {
            return;
        }

        else if (p_lazyAdd > p_lazyRem) {
            lazyAdd = p_lazyAdd;
            lazyRem = p_lazyRem;
            addFirst = lazyAdd;
        } else if (lazyAdd > lazyRem) {
            int val = (p_addFirst ? lazyRem : lazyAdd);
            lazyAdd = max((p_addFirst ? val : min(val, p_lazyRem)), p_lazyAdd);
            lazyRem = min((p_addFirst ? max(val, p_lazyAdd) : val), p_lazyRem);
            addFirst = p_addFirst;
        } 
        
        else if (addFirst && ! p_addFirst) {
            lazyRem = min(lazyRem, p_lazyRem);
            lazyAdd = max(p_lazyAdd, min(lazyAdd, lazyRem));
            addFirst = false;
        } else if (!addFirst && p_addFirst) {
            lazyAdd = max(lazyAdd, p_lazyAdd);
            lazyRem = min(p_lazyRem, max(lazyRem, lazyAdd));
            addFirst = true;
        }

        else if (addFirst && p_addFirst) {
            lazyAdd = max(p_lazyAdd, lazyAdd);
            lazyRem = min(p_lazyRem, max(lazyRem, p_lazyAdd));
            addFirst = true;
        } else if (!addFirst && !p_addFirst) {
            lazyRem = min(p_lazyRem, lazyRem);
            lazyAdd = max(p_lazyAdd, min(lazyAdd, p_lazyRem));
            addFirst = false;
        }
    }

    void processLazy() {
        if (addFirst) {
            v = max(v, lazyAdd);
        }
        v = min(v, lazyRem);
        if (!addFirst) {
            v = max(v, lazyAdd);
        }
        lazyAdd = -1;
        lazyRem = INF;
    }

    void opp(int a, int b, int op, int h) {
        if (a > b) return;
        if (a == l && b == r) {
            if      ( addFirst && op == 2) lazyRem = min(lazyRem, h);
            else if (!addFirst && op == 1) lazyAdd = max(lazyAdd, h);
            else if (op == 2) {
                lazyRem = min(h, max(lazyRem, lazyAdd));
                addFirst = true;
            }
            else if (op == 1) {
                lazyAdd = max(h, min(lazyRem, lazyAdd));
                addFirst = false;
            }
            if (l == r) processLazy();
            return;
        }
        if (l == r) {
            processLazy();
            return;
        }
        int mid = (l + r)/2;
        if (lptr == NULL) {
            lptr = new Tree(l, mid);
            rptr = new Tree(mid + 1, r);
        }
        lptr->push(this);
        rptr->push(this);
        lazyAdd = -1, lazyRem = INF;
        lptr->opp(a, min(mid, b), op, h);
        rptr->opp(max(mid+1, a), b, op, h);
    }

    void readAll(int finalHeight[]) {
        if (lptr == NULL) {
            processLazy();
            for (int i = l; i <= r; i++) {
                finalHeight[i] = v;
            }
            return;
        }
        lptr->push(this);
        rptr->push(this);
        lptr->readAll(finalHeight);
        rptr->readAll(finalHeight);
    }


};

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[])
{
    Tree *t = new Tree(n);
    for (int i = 0; i < k; i++) {
        t->opp(left[i], right[i], op[i], height[i]);
    }
    t->readAll(finalHeight);
}

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