제출 #546385

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
546385		alextodoran	벽 (IOI14_wall)	C++17	100 / 100	655 ms	107136 KiB

wall

#include <bits/stdc++.h>

using namespace std;

const int N_MAX = 2000000;

struct SGTInfo {
    int lazyMin, lazyMax;
    SGTInfo () {
        lazyMin = INT_MIN;
        lazyMax = INT_MAX;
    }
    void update (int newMin, int newMax) {
        if (newMax < lazyMin) {
            lazyMin = lazyMax = newMax;
        } else if (lazyMax < newMin) {
            lazyMin = lazyMax = newMin;
        } else {
            lazyMin = max(lazyMin, newMin);
            lazyMax = min(lazyMax, newMax);
        }
    }
};

SGTInfo SGT[N_MAX * 4 + 2];

void build (int node, int l, int r) {
    SGT[node] = SGTInfo();
    if (l == r) {
        SGT[node].update(0, 0);
    } else {
        int mid = (l + r) / 2;
        int lSon = node * 2, rSon = node * 2 + 1;
        build(lSon, l, mid);
        build(rSon, mid + 1, r);
    }
}
void split (int node) {
    int lSon = node * 2, rSon = node * 2 + 1;
    SGT[lSon].update(SGT[node].lazyMin, SGT[node].lazyMax);
    SGT[rSon].update(SGT[node].lazyMin, SGT[node].lazyMax);
    SGT[node] = SGTInfo();
}
void update (int node, int l, int r, int ul, int ur, int utype, int uval) {
    if (ul <= l && r <= ur) {
        if (utype == 1) {
            SGT[node].update(uval, INT_MAX);
        } else {
            SGT[node].update(INT_MIN, uval);
        }
    } else {
        int mid = (l + r) / 2;
        int lSon = node * 2, rSon = node * 2 + 1;
        split(node);
        if (ul <= mid) {
            update(lSon, l, mid, ul, ur, utype, uval);
        }
        if (mid + 1 <= ur) {
            update(rSon, mid + 1, r, ul, ur, utype, uval);
        }
    }
}
int answer[N_MAX];
void getAnswer (int node, int l, int r) {
    if (l == r) {
        answer[l] = SGT[node].lazyMin;
    } else {
        int mid = (l + r) / 2;
        int lSon = node * 2, rSon = node * 2 + 1;
        split(node);
        getAnswer(lSon, l, mid);
        getAnswer(rSon, mid + 1, r);
    }
}

void buildWall (int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
    build(1, 0, n - 1);
    for (int i = 0; i < k; i++) {
        update(1, 0, n - 1, left[i], right[i], op[i], height[i]);
    }
    getAnswer(1, 0, n - 1);
    copy(answer, answer + n, finalHeight);
}

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