Submission #776653

#	Time	Username	Problem	Language	Result	Execution time	Memory
776653		aiyah	Wall (IOI14_wall)	C++17	100 / 100	819 ms	224548 KiB

wall

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

int clamp(int val, pair<int,int> bounds) {
    return max(bounds.first, min(bounds.second,val));
}

pair<int,int> compose_clamps(pair<int,int> outside, pair<int,int> inside) {
    if (outside.second <= inside.first) return {outside.second, outside.second};
    if (outside.first >= inside.second) return {outside.first, outside.first};
    return {max(outside.first,inside.first), min(outside.second,inside.second)};
}

struct Node {
    int l;
    int r;
    Node *ln;
    Node *rn;
    pair<int,int> bounds;

    Node(int tl, int tr): l(tl), r(tr) {
        bounds = {INT_MIN,INT_MAX};

        if (l + 1 == r) {
            ln = rn = NULL;
            return;
        }

        int mid = (l + r) / 2;
        ln = new Node(l, mid);
        rn = new Node(mid, r);
    }

    int get(int i) {
        if (l <= i && i < r) {
            if (l + 1 == r) {
                return clamp(0, bounds);
            }
            return clamp(ln->get(i) + rn->get(i), bounds);
        }
        return 0;
    }

    void avoid_responsibility() {
        ln->bounds = compose_clamps(bounds, ln->bounds);
        rn->bounds = compose_clamps(bounds, rn->bounds);
        bounds = {INT_MIN,INT_MAX};
    }

    void apply(int lb, int rb, pair<int,int> bds) {
        if (rb <= l || r <= lb) return;
        if (lb <= l && r <= rb) {
            bounds = compose_clamps(bds, bounds);
            return;
        }
        avoid_responsibility();
        ln->apply(lb, rb, bds);
        rn->apply(lb, rb, bds);
    }
};

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
    Node *root = new Node(0, n);
    for (int i = 0; i < k; i++) {
        if (op[i] == 1) {
            root->apply(left[i], right[i] + 1, {height[i],INT_MAX});
        } else {
            root->apply(left[i], right[i] + 1, {INT_MIN,height[i]});
        }
    }
    for (int i = 0; i < n; i++) {
        finalHeight[i] = root->get(i);
    }
}

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