Submission #403332

#	Time	Username	Problem	Language	Result	Execution time	Memory
403332		danielcm585	Wall (IOI14_wall)	C++14	100 / 100	1048 ms	224648 KiB

wall

#include "wall.h"

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

const int INF = 1e9;

struct ops {
    int mn, mx;

    ops(int x = INF, int y = -INF): mn(x), mx(y) {}

    ops operator + (ops v) {
        if (mn < v.mx) return ops(v.mx,v.mx);
        if (mx > v.mn) return ops(v.mn,v.mn);
        return ops(min(mn,v.mn),max(mx,v.mx));
    }
};

struct segTree {
    segTree *lf, *rg;
    int l, r;
    ops val;

    segTree(int x, int y) {
        l = x, r = y;
        val = ops(0,0);
    }

    void build() {
        if (l == r) return;
        int mid = (l+r)/2;
        lf = new segTree(l,mid); lf->build();
        rg = new segTree(mid+1,r); rg->build();
    }

    void prop() {
        lf->val = lf->val+val;
        rg->val = rg->val+val;
        val = ops();
    }

    void update(int x, int y, ops v) {
        if (l > y || r < x) return;
        if (l >= x && r <= y) {
            val = val+v;
            return;
        }
        prop();
        lf->update(x,y,v); rg->update(x,y,v);
    }

    void solve(int ans[]) {
        if (l == r) {
            ans[l] = val.mn;
            return;
        }
        prop();
        lf->solve(ans); rg->solve(ans);
    }

} *st;

void buildWall(int n, int k, int op[], int l[], int r[], int h[], int ans[]) {
    st = new segTree(0,n-1); st->build();
    for (int i = 0; i < k; i++) {
        if (op[i] == 1) st->update(l[i],r[i],ops(INF,h[i]));
        else st->update(l[i],r[i],ops(h[i],-INF));
        // st->solve(ans);
        // for (int j = 0; j < n; j++) cout << ans[j] << ' ';
        // cout << '\n';
    }
    st->solve(ans);
}

/*
10 6
1 1 8 4
0 4 9 1
0 3 6 5
1 0 5 3
1 2 2 5
0 6 7 0
*/

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