Submission #1185812

#	Time	Username	Problem	Language	Result	Execution time	Memory
1185812		jasonic	Wall (IOI14_wall)	C++20	61 / 100	749 ms	276872 KiB

wall

/*

im gonna copy gabee's style of making the top row my thinking space

idea: store a segment tree that lazily stores each update.
what will each range contain? it will contain the minimum and maximum value of each range. thus, the updates get reworded as:

add    -> replace both values with max(self, v)
remove -> replace both values with min(self, v)

*/

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

#define ll long long
#define fastIO cin.tie(0); ios::sync_with_stdio(false)

struct ST{
    ll mn, mx;
    ST *lt, *rt;
    ll l, r;
    bool lazy;

    void combine() {
        mn = min(lt->mn, rt->mn);
        mx = max(lt->mx, rt->mx);
    }

    void prop() {
        if(!lazy) return;

        if(lt) {
            lt->mn = mn;
            lt->mx = mx;

            rt->mn = mn;
            rt->mx = mx;

            lt->lazy = true;
            rt->lazy = true;
        }

        lazy = false;
    }

    ST(ll bl, ll br) {
        l = bl; r = br;
        lt = rt = nullptr;
        mn = mx = 0;
        lazy = false;

        if(l != r) {
            ll m = (l+r)>>1;
            lt = new ST(l, m);
            rt = new ST(m+1, r);
        }
    }

    void addUpd(ll ql, ll qr, ll qv) {
        prop();
        if(qr < l || r < ql || mn >= qv) return;
        if(ql <= l && r <= qr && mn == mx) {
            mn = max(mn, qv);
            mx = max(mn, qv);
            lazy = true;
            prop();
            return;
        }
        
        if(!lt) return;
        lt->addUpd(ql, qr, qv);
        rt->addUpd(ql, qr, qv);
        combine();
    }
    
    void remUpd(ll ql, ll qr, ll qv) {
        prop();
        if(qr < l || r < ql || mx <= qv) return;
        if(ql <= l && r <= qr && mn == mx) {
            mn = min(mn, qv);
            mx = min(mx, qv);
            lazy = true;
            prop();
            return;
        }
        
        if(!lt) return;
        lt->remUpd(ql, qr, qv);
        rt->remUpd(ql, qr, qv);
        combine();
    }

    ll qry(ll i) {
        prop();
        if(i < l || r < i) return -1;
        if(l == r && r == i) {return mn;}
        
        return max(lt->qry(i), rt->qry(i));
    }
};

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
    ST tree(0, n-1);

    for(int i = 0; i < k; i++) {
        if(op[i] == 1) { // add
            tree.addUpd(left[i], right[i], height[i]);
        } else {
            tree.remUpd(left[i], right[i], height[i]);
        }
    }

    for(int i = 0; i < n; i++) {
        finalHeight[i] = tree.qry(i);
    }
}

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