Submission #1232883

#	Time	Username	Problem	Language	Result	Execution time	Memory
1232883		LucaIlie	Wall (IOI14_wall)	C++20	100 / 100	534 ms	88996 KiB

wall

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

using namespace std;

struct info {
    int l, r;
};

const int MAX_N = 2e6;
const int INF = 1e5;
info lazy[4 * MAX_N];

void propag(int v, int l, int r) {
    if (l == r)
        return;

    lazy[v * 2 + 1].l = min(lazy[v * 2 + 1].l, lazy[v].r);
    lazy[v * 2 + 1].l = max(lazy[v * 2 + 1].l, lazy[v].l);
    lazy[v * 2 + 1].r = min(lazy[v * 2 + 1].r, lazy[v].r);
    lazy[v * 2 + 1].r = max(lazy[v * 2 + 1].r, lazy[v].l);

    lazy[v * 2 + 2].l = min(lazy[v * 2 + 2].l, lazy[v].r);
    lazy[v * 2 + 2].l = max(lazy[v * 2 + 2].l, lazy[v].l);
    lazy[v * 2 + 2].r = min(lazy[v * 2 + 2].r, lazy[v].r);
    lazy[v * 2 + 2].r = max(lazy[v * 2 + 2].r, lazy[v].l);

    lazy[v] = {0, INF};
}

int timee = 0;
void update(int v, int l, int r, int lu, int ru, int t, int k) {
    propag(v, l, r);

    if (l > ru || r < lu)
        return;

    if (lu <= l && r <= ru) {
        if (t == 1) {
            lazy[v].l = max(lazy[v].l, k);
            lazy[v].r = max(lazy[v].r, k);
        } else {
            lazy[v].l = min(lazy[v].l, k);
            lazy[v].r = min(lazy[v].r, k);
        }
        propag(v, l, r);
        return;
    }

    int mid = (l + r) / 2;
    update(v * 2 + 1, l, mid, lu, ru, t, k);
    update(v * 2 + 2, mid + 1, r, lu, ru, t, k);
}

void getFinalHeight(int v, int l, int r, int finalHeight[]) {
    propag(v, l, r);

    // printf("%d %d -> %d %d\n", l, r, lazy[v].l, lazy[v].r);
    
    if (l == r) {
        finalHeight[l] = lazy[v].l;
        return;
    }

    int mid = (l + r) / 2;
    getFinalHeight(v * 2 + 1, l, mid, finalHeight);
    getFinalHeight(v * 2 + 2, mid + 1, r, finalHeight);
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
    for (int v = 0; v < 4 * n; v++)
        lazy[v] = {0, INF};

    for (int i = 0; i < k; i++)
        update(0, 0, n - 1, left[i], right[i], op[i], height[i]);

    getFinalHeight(0, 0, n - 1, finalHeight);
}

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