Submission #272746

#	Time	Username	Problem	Language	Result	Execution time	Memory
272746		toonewbie	Wall (IOI14_wall)	C++17	100 / 100	1292 ms	69780 KiB

wall

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

using namespace std;

const int INF = 2000000000;
const int maxx = 2000005;

#define mn first
#define mx second

pair <int, int> t[maxx << 2];

void relax(int v, int l, int r) {
    if (l != r) {
        int lc = v << 1, rc = v << 1 | 1;
        t[lc] = {max(min(t[lc].mn, t[v].mn), t[v].mx), max(min(t[lc].mx, t[v].mn), t[v].mx)};
        t[rc] = {max(min(t[rc].mn, t[v].mn), t[v].mx), max(min(t[rc].mx, t[v].mn), t[v].mx)};
    }
}

void update(int v, int l, int r, int i, int j, int val, int oq) {
    relax(v, l, r);
    if (i > r || j < l) {
        return;
    }
    if (i <= l && r <= j) {
        if (oq == 1) {
            t[v].mn = max(t[v].mn, val);
            t[v].mx = max(t[v].mx, val);
        } else {
            t[v].mn = min(t[v].mn, val);
            t[v].mx = min(t[v].mx, val);
        }
        return;
    }
    t[v].mn = INF, t[v].mx = -INF;
    int mid = (l + r) >> 1;
    update(v << 1, l, mid, i, j, val, oq);
    update(v << 1 | 1, mid + 1, r, i, j, val, oq);
}
int query(int v, int l, int r, int i) {
    relax(v, l, r);
    if (l == r) {
        return t[v].mn;
    }
    int mid = (l + r) >> 1;
    if (i <= mid) {
        return query(v << 1, l, mid, i);
    } else {
        return query(v << 1 | 1, mid + 1, r, i);
    }
}

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]);
    }
    for (int i = 1; i <= n; i++) {
        finalHeight[i - 1] = query(1, 1, n, i);
    }
    return;
}

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