Submission #1289173

#	Time	Username	Problem	Language	Result	Execution time	Memory
1289173		kawhiet	Wall (IOI14_wall)	C++20	100 / 100	548 ms	63304 KiB

wall

#include <bits/stdc++.h>
#include "wall.h"
using namespace std;

constexpr int N = 2e6;

int mn[N * 4], mx[N * 4];
bool has[N * 4];

void push(int id, int tl, int tr) {
    if (!has[id] || tl == tr) return;
    int x = (id << 1) + 1, y = x + 1, tm = (tl + tr) >> 1;
    has[x] = has[y] = 1;
    mx[x] = mx[y] = mx[id];
    mn[x] = mn[y] = mn[id];
    has[id] = 0;
}

void add(int id, int tl, int tr, int l, int r, int h) {
    push(id, tl, tr);
    if (r < tl || tr < l || mn[id] >= h) return;
    if (l <= tl && tr <= r && mx[id] <= h) {
        has[id] = 1;
        mn[id] = mx[id] = max(h, mx[id]);
        push(id, tl, tr);
        return;
    }
    int x = (id << 1) + 1, y = x + 1, tm = (tl + tr) >> 1;
    add(x, tl, tm, l, r, h);
    add(y, tm + 1, tr, l, r, h);
    mn[id] = min(mn[x], mn[y]);
    mx[id] = max(mx[x], mx[y]);
}

void remove(int id, int tl, int tr, int l, int r, int h) {
    push(id, tl, tr);
    if (r < tl || tr < l || mx[id] <= h) return;
    if (l <= tl && tr <= r && mn[id] >= h) {
        has[id] = 1;
        mn[id] = mx[id] = min(h, mn[id]);
        push(id, tl, tr);
        return;
    }
    int x = (id << 1) + 1, y = x + 1, tm = (tl + tr) >> 1;
    remove(x, tl, tm, l, r, h);
    remove(y, tm + 1, tr, l, r, h);
    mn[id] = min(mn[x], mn[y]);
    mx[id] = max(mx[x], mx[y]);
}

int get(int id, int tl, int tr, int i) {
    push(id, tl, tr);
    if (tl == tr) {
        return mx[id];
    }
    int x = (id << 1) + 1, y = x + 1, tm = (tl + tr) >> 1;
    if (i <= tm) {
        return get(x, tl, tm, i);
    } else {
        return get(y, tm + 1, tr, i);
    }
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
    for (int i = 0; i < k; i++) {
        int t = op[i], l = left[i], r = right[i], h = height[i];
        if (t == 1) {
            add(0, 0, n - 1, l, r, h);
        } else {
            remove(0, 0, n - 1, l, r, h);
        }
    }
    for (int i = 0; i < n; i++) {
        finalHeight[i] = get(0, 0, n - 1, i);
    }
}

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