Submission #1267337

#	Time	Username	Problem	Language	Result	Execution time	Memory
1267337		uranium235	Wall (IOI14_wall)	C++17	100 / 100	377 ms	78848 KiB

wall

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

struct state {
    int min = -1, max = -1;
    void merge(state &l, state &r) {
        // min = std::max(l.min, r.min);
        // max = std::min(r.min, l.min);
    }
    void push(state &l, state &r) {
        // assert(min == -1 || max == -1);
        if (min != -1) {
            l.changeLower(min);
            r.changeLower(min);
        }
        if (max != -1) {
            l.changeUpper(max);
            r.changeUpper(max);
        }
        min = max = -1;
    }
    void apply(pair<bool, int> &x) {
        if (x.first) {
            changeUpper(x.second);
        } else {
            changeLower(x.second);
        }
    }
    void changeUpper(int x) {
        if (max == -1) max = x;
        else max = std::min(max, x);
        if (min != -1) min = std::min(min, max);
    }
    void changeLower(int x) {
        if (min == -1) min = x;
        else min = std::max(min, x);
        if (max != -1) max = std::max(max, min);
    }
};

class lazyseg {
    public:
        vector<state> a;
        int n;
        lazyseg(int n) : n(n), a(4 * n) {}
        void upd(int ll, int rr, int l, int r, int v, pair<bool, int> &x) {
            if (r < ll || rr < l) return;
            else if (ll <= l && r <= rr) a[v].apply(x);
            else {
                a[v].push(a[2 * v], a[2 * v + 1]);
                int m = (l + r) / 2;
                upd(ll, rr, l, m, 2 * v, x);
                upd(ll, rr, m + 1, r, 2 * v + 1, x);
                a[v].merge(a[2 * v], a[2 * v + 1]);
            }
        }
        void finalize(int l, int r, int v, int *x) {
            if (l == r) {
                assert(a[v].max == -1 || (a[v].min <= a[v].max));
                // if (a[v].max != -1) x[l] = min(a[v].max)
                x[l] = max(0, a[v].min);
            } else {
                a[v].push(a[2 * v], a[2 * v + 1]);
                int m = (l + r) / 2;
                finalize(l, m, 2 * v, x);
                finalize(m + 1, r, 2 * v + 1, x);
            }
        }
};

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
    lazyseg tree(n);
    for (int i = 0; i < k; i++) {
        pair<bool, int> update = {op[i] == 2, height[i]};
        tree.upd(left[i], right[i], 0, n - 1, 1, update);
    }
    tree.finalize(0, n - 1, 1, finalHeight);
}

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