Submission #1114636

#	Time	Username	Problem	Language	Result	Execution time	Memory
1114636		_callmelucian	Wall (IOI14_wall)	C++14	100 / 100	770 ms	89160 KiB

wall

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

typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pl;
typedef pair<int,int> pii;
typedef tuple<int,int,int> tpl;

#define all(a) a.begin(), a.end()
#define filter(a) a.erase(unique(all(a)), a.end())

struct IT {
    vector<int> lo, hi;
    IT (int sz) : lo(4 * sz), hi(4 * sz) {}

    void applyRange (int k, int fL, int fR) {
        lo[k] = max(lo[k], fL), hi[k] = max(hi[k], fL);
        lo[k] = min(lo[k], fR), hi[k] = min(hi[k], fR);
    }

    void pushDown (int k) {
        applyRange(2 * k, lo[k], hi[k]), applyRange(2 * k + 1, lo[k], hi[k]);
    }

    void update (int a, int b, int fL, int fR, int k, int l, int r) {
        if (b < l || r < a) return;
        if (a <= l && r <= b)
            return applyRange(k, fL, fR), void();
        pushDown(k);
        int mid = (l + r) >> 1;
        update(a, b, fL, fR, 2 * k, l, mid);
        update(a, b, fL, fR, 2 * k + 1, mid + 1, r);
        lo[k] = min(lo[2 * k], lo[2 * k + 1]), hi[k] = max(hi[2 * k], hi[2 * k + 1]);
    }

    void dfsPrint (int k, int l, int r, int finalHeight[]) {
        if (l == r) {
            assert(lo[k] == hi[k]);
            return finalHeight[l] = lo[k], void();
        }
        pushDown(k);
        int mid = (l + r) >> 1;
        dfsPrint(2 * k, l, mid, finalHeight);
        dfsPrint(2 * k + 1, mid + 1, r, finalHeight);
        lo[k] = min(lo[2 * k], lo[2 * k + 1]), hi[k] = max(hi[2 * k], hi[2 * k + 1]);
    }
};

void buildWall (int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
    IT tree(n);
    for (int i = 0; i < k; i++) {
        if (op[i] == 1) tree.update(left[i], right[i], height[i], INT_MAX, 1, 0, n - 1);
        if (op[i] == 2) tree.update(left[i], right[i], INT_MIN, height[i], 1, 0, n - 1);
    }
    tree.dfsPrint(1, 0, n - 1, finalHeight);
}

#ifdef LOCAL
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    int op[] = {1, 2, 2, 1, 1, 2}, left[] = {1, 4, 3, 0, 2, 6}, right[] = {8, 9, 6, 5, 2, 7};
    int height[] = {4, 1, 5, 3, 5, 0}, finalHeight[10] = {0};
    buildWall(10, 6, op, left, right, height, finalHeight);

    for (int i = 0; i < 10; i++) cout << finalHeight[i] << " ";

    return 0;
}
#endif // LOCAL

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