제출 #117356

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
117356		dolphingarlic	벽 (IOI14_wall)	C++14	100 / 100	704 ms	99264 KiB

wall

// Power Of Ninja Go
#include <bits/stdc++.h>
#ifdef atom
#include "grader.cpp"
#else
#include "wall.h"
#endif
using namespace std;
typedef long long ll;
typedef pair<int, int> ii;
#define X first
#define Y second
#define vi vector<int>
#define vii vector<ii>
#define pb push_back
struct node {
    int lo, hi;
    node() {
        lo = 0;
        hi = 1e5;
    }
};
const int maxn = 2e6 + 5;
node st[4 * maxn];
int n;
void change(int p, int op, int v) {
    if (op == 1)
        st[p].lo = max(st[p].lo, v), st[p].hi = max(st[p].hi, v);
    else
        st[p].lo = min(st[p].lo, v), st[p].hi = min(st[p].hi, v);
}
void update(int i, int j, int op, int v, int p = 1, int L = 0, int R = n - 1) {
    if (i > R || j < L) return;
    if (i <= L && R <= j) {
        change(p, op, v);
        return;
    }
    change(2 * p, 1, st[p].lo);
    change(2 * p + 1, 1, st[p].lo);
    change(2 * p, 2, st[p].hi);
    change(2 * p + 1, 2, st[p].hi);
    st[p].lo = 0, st[p].hi = 1e5;
    int M = (L + R) / 2;
    update(i, j, op, v, 2 * p, L, M);
    update(i, j, op, v, 2 * p + 1, M + 1, R);
}
int *arr;
void prop(int p = 1, int L = 0, int R = n - 1) {
    if (L == R) {
        arr[L] = st[p].lo;
        return;
    }
    change(2 * p, 1, st[p].lo);
    change(2 * p + 1, 1, st[p].lo);
    change(2 * p, 2, st[p].hi);
    change(2 * p + 1, 2, st[p].hi);
    int M = (L + R) / 2;
    prop(2 * p, L, M);
    prop(2 * p + 1, M + 1, R);
}
void buildWall(int N, int k, int op[], int left[], int right[], int height[],
               int finalHeight[]) {
    n = N;
    arr = finalHeight;
    for (int i = 0; i < k; i++) update(left[i], right[i], op[i], height[i]);
    prop();
}

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