Submission #1006627

#	Time	Username	Problem	Language	Result	Execution time	Memory
1006627		The_Samurai	Wall (IOI14_wall)	C++17	24 / 100	300 ms	11412 KiB

wall

#include "wall.h"
#include "bits/stdc++.h"
using namespace std;
const int inf = 2e9;

vector<int> mn, mx;
int sz;

// first mx, then mn

void impact(int x, int op, int v) {
    if (op == 1) {
        mx[x] = max(mx[x], v);
        if (mn[x] <= v) {
            mn[x] = inf;
        }
    } else {
        mn[x] = min(mn[x], v);
        if (mx[x] >= mn[x]) mx[x] = mn[x];
    }
}

void propagate(int x) {
    if (mx[x] != 0) {
        impact(2 * x + 1, 1, mx[x]);
        impact(2 * x + 2, 1, mx[x]);
        mx[x] = 0;
    }
    if (mn[x] != inf) {
        impact(2 * x + 1, 2, mn[x]);
        impact(2 * x + 2, 2, mn[x]);
        mn[x] = inf;
    }
}

void upd(int l, int r, int op, int v, int x, int lx, int rx) {
    if (l >= rx or lx >= r) return;
    if (l <= lx and rx <= r) {
        impact(x, op, v);
        return;
    }
    propagate(x);
    int mid = (lx + rx) >> 1;
    upd(l, r, op, v, 2 * x + 1, lx, mid);
    upd(l, r, op, v, 2 * x + 2, mid, rx);
}

int get(int i, int x, int lx, int rx) {
    if (rx - lx == 1) {
        return min(mx[x], mn[x]);
    }
    propagate(x);
    int mid = (lx + rx) >> 1;
    if (i < mid) return get(i, 2 * x + 1, lx, mid);
    return get(i, 2 * x + 2, mid, rx);
}

void buildWall(int n, int q, int op[], int left[], int right[], int height[], int finalHeight[]) {
    sz = 1;
    while (sz < n) sz *= 2;
    mn.assign(2 * sz, inf); mx.assign(2 * sz, 0);
    for (int i = 0; i < q; i++) {
        upd(left[i], right[i] + 1, op[i], height[i], 0, 0, sz);
    }
    for (int i = 0; i < n; i++) {
        finalHeight[i] = get(i, 0, 0, sz);
    }
}

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