Submission #1232857

#	Time	Username	Problem	Language	Result	Execution time	Memory
1232857		LucaIlie	Wall (IOI14_wall)	C++20	0 / 100	252 ms	114440 KiB

wall

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

using namespace std;

struct upd {
    int l, r;
};

const int MAX_N = 2e6;
const int INF = 1e9;
vector<int> updatesByL[MAX_N], updatesByR[MAX_N];
upd segTree[4 * MAX_N];

void update(int v, int l, int r, int p, upd x) {
    if (p > r || p < l)
        return;

    if (l == r) {
        segTree[v] = x;
        return;
    }

    int mid = (l + r) / 2;
    update(v * 2 + 1, l, mid, p, x);
    update(v * 2 + 2, mid + 1, r, p, x);

    upd a = segTree[v * 2 + 1];
    upd b = segTree[v * 2 + 2];

    upd ans;

    ans.l = min(max(a.l, b.l), b.r);
    ans.r = min(max(a.r, b.l), b.r);
    // printf("aint %d %d -> %d %d %d\n", l, r, a.l, a.r, a.k);

    segTree[v] = ans;
}

upd queryAll() {
    return segTree[0];
}

void buildWall(int n, int q, int op[], int left[], int right[], int height[], int finalHeight[]){
    for (int v = 0; v < 4 * n; v++)
        segTree[v] = {0, INF};
    for (int i = 0; i < q; i++) {
        updatesByL[left[i]].push_back(i);
        updatesByR[right[i]].push_back(i);
    }

    for (int i = 0; i < n; i++) {
        for (int j: updatesByL[i]) {
            upd u;
            if (op[j] == 1)
                u = {height[j], INF};
            else
                u = {0, height[j]};
            // printf("apare %d %d\n", op[j], height[j]);
            update(0, 0, q - 1, j, u);
        }

        finalHeight[i] = queryAll().l;
        // printf("query %d\n", i);

        for (int j: updatesByR[i]) {
            update(0, 0, q - 1, j, {0, INF});
            // printf("dispare %d %d\n", op[j], height[j]);
        }
    }
}

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