Submission #1177091

#	Time	Username	Problem	Language	Result	Execution time	Memory
1177091		sardor_salimov	벽 (IOI14_wall)	C++17	100 / 100	472 ms	96880 KiB

wall

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

using namespace std;

const int N = 2e6 + 6;
ar <int, 2> t[N << 2];
int ans[N];

ar <int, 2> merge(const ar <int, 2> a, const ar <int, 2> b) {
    int nl = max(a[0], b[0]), nr = min(a[1], b[1]);
    ar <int, 2> res;
    if (nl <= nr)
        res = {nl, nr};
    else if (nr < a[0])
        res = {a[0], a[0]};
    else
        res = {a[1], a[1]};
    return res;
}

void push(int v, int l, int r) {
    if (l != r) {
        t[v << 1] = merge(t[v], t[v << 1]);
        t[v << 1 | 1] = merge(t[v], t[v << 1 | 1]);
        t[v] = {0, N};
    }
}

int ql, qr, qt, qx, tl, tr;

void update(int v, int l, int r) {
    push(v, l, r);
    if (ql <= l && r <= qr)
        return t[v] = merge({tl, tr}, t[v]), void();
    if (ql > r || l > qr)
        return;
    int m = l + r >> 1;
    update(v << 1, l, m);
    update(v << 1 | 1, m + 1, r);
}

void go(int v, int l, int r) {
    push(v, l, r);
    if (l == r)
        return ans[l] = t[v][0], void();
    int m = l + r >> 1;
    go(v << 1, l, m);
    go(v << 1 | 1, m + 1, r);
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
    for (int i = 0; i < (N << 2); i++)
        t[i] = {0, 0};
    for (int i = 0; i < k; i++) {
        ql = left[i], qr = right[i];
        if (op[i] == 1)
            tl = height[i], tr = N;
        else
            tl = 0, tr = height[i];
        update(1, 0, n - 1);
    }
    go(1, 0, n - 1);
    for (int i = 0; i < n; i++)
        finalHeight[i] = ans[i];
}

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