Submission #311954

#	Time	Username	Problem	Language	Result	Execution time	Memory
311954		hhoangcpascal	Wall (IOI14_wall)	C++14	100 / 100	801 ms	77680 KiB

wall

/// hhoangcpascal

#include <cstdio>
#include <iostream>
#include <algorithm>
#define file_name "WALL"

using namespace std;

struct node {
    int mmin, mmax;
} Seg[8000006];

void update(int id, int val, int type) {
    if (type == 2) {
        Seg[id].mmax = min(Seg[id].mmax, val);
        Seg[id].mmin = min(Seg[id].mmin, val);
    } else {
        Seg[id].mmax = max(Seg[id].mmax, val);
        Seg[id].mmin = max(Seg[id].mmin, val);
    }
}

void down(int id) {
    Seg[id<<1].mmax = max(min(Seg[id<<1].mmax, Seg[id].mmax), Seg[id].mmin);
    Seg[id<<1].mmin = min(max(Seg[id<<1].mmin, Seg[id].mmin), Seg[id].mmax);

    Seg[id<<1|1].mmax = max(min(Seg[id<<1|1].mmax, Seg[id].mmax), Seg[id].mmin);
    Seg[id<<1|1].mmin = min(max(Seg[id<<1|1].mmin, Seg[id].mmin), Seg[id].mmax);

    Seg[id].mmax = 1e9, Seg[id].mmin = 0;
}

void update(int id, int l, int r, int u, int v, int val, int type) {
    if (l > v || r < u) return;
    if (u <= l && r <= v) {
        update(id, val, type);
        return;
    }

    int mid = (l + r) >> 1;
    down(id);

    update(id<<1, l, mid, u, v, val, type);
    update(id<<1|1, mid+1, r, u, v, val, type);
}

int ans[2000006];

void cal(int id, int l, int r) {
    if (l > r) return;
    if (l == r) {
        ans[l] = Seg[id].mmin;
        return;
    }

    int mid = (l + r) >> 1;
    down(id);

    cal(id<<1, l, mid);
    cal(id<<1|1, mid+1, r);
}

void buildWall(int n, int k, int op[],  int Left[], int Right[], int height[], int finalHeight[]) {
    for(int i=0; i<k; ++i) 
        update(1, 1, n, Left[i]+1, Right[i]+1, height[i], op[i]);

    cal(1, 1, n);
    for(int i=0; i<n; ++i) finalHeight[i] = ans[i+1];
}

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