제출 #1363181

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1363181		toma_ariciu	벽 (IOI14_wall)	C++20	100 / 100	332 ms	78564 KiB

wall

#include <bits/stdc++.h>

#include "wall.h"

using namespace std;

const int inf = 0x3f3f3f3f;

void minSelf(int &x, int y) {
    if (y < x) {
        x = y;
    }
}

void maxSelf(int &x, int y) {
    if (y > x) {
        x = y;
    }
}

struct SegTree {
    struct Node {
        int mini, maxi;
    };

    int n;
    vector <Node> v;
    
    void build(int nod, int st, int dr) {
        v[nod].mini = 0;
        v[nod].maxi = inf;

        if (st == dr) {
            return;
        }

        int med = (st + dr) / 2;
        build(2 * nod, st, med);
        build(2 * nod + 1, med + 1, dr);
    }

    void minimize(int nod, int val) {
        if (val < v[nod].mini) {
            v[nod].mini = val;
            v[nod].maxi = val;
        } else if (val < v[nod].maxi) {
            v[nod].maxi = val;
        }
    }

    void maximize(int nod, int val) {
        if (val > v[nod].maxi) {
            v[nod].mini = val;
            v[nod].maxi = val;
        } else if (val > v[nod].mini) {
            v[nod].mini = val;
        }
    }

    void propag(int nod) {
        minimize(2 * nod, v[nod].maxi);
        maximize(2 * nod, v[nod].mini);

        minimize(2 * nod + 1, v[nod].maxi);
        maximize(2 * nod + 1, v[nod].mini);

        v[nod].mini = 0;
        v[nod].maxi = inf;
    }

    void update(int nod, int st, int dr, int ust, int udr, int val, int type) {
        if (ust <= st && dr <= udr) {
            if (type == 1) {
                maximize(nod, val);
            } else {
                minimize(nod, val);
            }
            return;
        }

        propag(nod);

        int med = (st + dr) / 2;
        if (ust <= med) {
            update(2 * nod, st, med, ust, udr, val, type);
        }
        if (med < udr) {
            update(2 * nod + 1, med + 1, dr, ust, udr, val, type);
        }
    }

    void update(int ust, int udr, int val, int type) {
        update(1, 1, n, ust, udr, val, type);
    }

    int getVal(int nod, int st, int dr, int poz) {
        if (st == dr) {
            return clamp(0, v[nod].mini, v[nod].maxi);
        }

        int med = (st + dr) / 2, x;
        if (poz <= med) {
            x = getVal(2 * nod, st, med, poz);
        } else {
            x = getVal(2 * nod + 1, med + 1, dr, poz);
        }
        return clamp(x, v[nod].mini, v[nod].maxi);
    }

    void print(int nod, int st, int dr, int ans[]) {
        if (st == dr) {
            ans[st - 1] = clamp(0, v[nod].mini, v[nod].maxi);
            return;
        }

        propag(nod);
        
        int med = (st + dr) / 2;
        print(2 * nod, st, med, ans);
        print(2 * nod + 1, med + 1, dr, ans);
    }

    void print(int ans[]) {
        print(1, 1, n, ans);
    }

    SegTree(int n_) : n(n_), v(4 * n + 1) {
        build(1, 1, n);
    }
};



void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
    SegTree aint(n);

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

    aint.print(finalHeight);
}

• 서브태스크 1: 8 / 8
• 서브태스크 2: 24 / 24
• 서브태스크 3: 29 / 29
• 서브태스크 4: 39 / 39