제출 #402962

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
402962		danielcm585	벽 (IOI14_wall)	C++14	0 / 100	187 ms	13836 KiB

wall

#include "wall.h"

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

const int INF = 1e9;

struct node {
    node *lf, *rg;
    int l, r;
    int val, lzMin, lzMax;

    node(int x, int y): l(x), r(y), val(0), lzMin(INF), lzMax(-INF) {}

    void build() {
        if (l == r) return;
        int mid = (l+r)/2;
        lf = new node(l,mid); lf->build();
        rg = new node(mid+1,r); rg->build();
    }

    void apply(int mn, int mx) {
        val = min(val,mn); lzMin = min(lzMin,mn);
        val = max(val,mx); lzMax = max(lzMax,mx);
    }

    void prop() {
        if (lzMin == INF && lzMax == -INF) return;
        if (l < r) {
            lf->apply(lzMin,lzMax);
            rg->apply(lzMin,lzMax);
        }
        lzMin = INF, lzMax = -INF;
    }

    void update(int x, int y, int mn, int mx) {
        if (l > y || r < x) return;
        if (l >= x && r <= y) {
            apply(mn,mx);
            return;
        }
        prop();
        lf->update(x,y,mn,mx); rg->update(x,y,mn,mx);
    }

    int query(int x) {
        if (l == r) return val;
        prop();
        int mid = (l+r)/2;
        if (x <= mid) return lf->query(x);
        return rg->query(x);
    }
};

void buildWall(int n, int k, int op[], int l[], int r[], int h[], int ans[]) {
    node *st = new node(0,n-1); st->build();
    for (int i = 0; i < k; i++) {
        if (op[i] == 1) st->update(l[i],r[i],INF,h[i]);
        else st->update(l[i],r[i],h[i],-INF);
        // for (int j = 0; j < n; j++) cout << st->query(j) << ' ';
        // cout << '\n';
    }
    for (int i = 0; i < n; i++) ans[i] = st->query(i);
}

/*
10 6
1 1 8 4
0 4 9 1
0 3 6 5
1 0 5 3
1 2 2 5
0 6 7 0
*/

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