Submission #1185356

#	Time	Username	Problem	Language	Result	Execution time	Memory
1185356		tapilyoca	Wall (IOI14_wall)	C++20	100 / 100	742 ms	214144 KiB

wall

/***********************************************
* auth: tapilyoca                              *
* date: 04/15/2025 at 08:29:42                 *
* dots: https://github.com/tapilyoca/dotilyoca * 
***********************************************/

#include <bits/stdc++.h>
#include "wall.h"
using namespace std;
const long long MOD = 1e9+7;

template<typename T>
using vec = vector<T>;
using ll = long long;
using vll = vec<ll>;
using vvll = vec<vll>;
using pll = pair<ll,ll>;
using str = string;
#define pb push_back
#define dbg(x) cerr << #x << ": " << x << endl;

/***********************************************/



struct Segtree {
    int l, r;
    Segtree *lt, *rt;
    int lb, ub;
    bool lazy;

    Segtree(int left, int right) {
        l = left;
        r = right;
        lt = rt = nullptr;
        lb = 0;
        ub = INT_MAX;
        lazy = 0;

        if(l == r) return;
        int mid = (l+r)>>1;
        lt = new Segtree(l,mid);
        rt = new Segtree(mid+1,r);
    }

    void propagate() {
        if(lazy) {
            if(lt){
                // cerr << "from propagation ";
                // lt->debug();
                lt->lb = max(lb, lt->lb);
                lt->ub = max(lt->lb, lt->ub);
                lt->ub = min(ub, lt->ub);
                lt->lb = min(lt->ub, lt->lb);

                rt->lb = max(lb, rt->lb);
                rt->ub = max(rt->lb, rt->ub);
                rt->ub = min(ub, rt->ub);
                rt->lb = min(rt->ub, rt->lb);
                lt->lazy = 1;
                rt->lazy = 1;

                lb = 0;
                ub = INT_MAX;
            }
            lazy = 0;

        }
    }

    void maximize(int ml, int mr, int val) {
        if(l > mr or r < ml) return;
        propagate();
        if(ml <= l and r <= mr) {
            lazy = 1;
            lb = max(val,lb);
            ub = max(lb,ub);
            propagate();
            // debug();
            return;
        }
        lt->maximize(ml,mr,val);
        rt->maximize(ml,mr,val);
        // debug();
    }

    void minimize(int ml, int mr, int val) {
        if(l > mr or r < ml) return;
        propagate();
        if(ml <= l and r <= mr) {
            lazy = 1;
            ub = min(val,ub);
            lb = min(ub,lb);
            propagate();
            // debug();
            return;
        }
        lt->minimize(ml,mr,val);
        rt->minimize(ml,mr,val);
    }

    int query(int dex) {
        propagate();
        if(dex < l or r < dex) return 0;
        // debug();
        if(l == r) {
            return lb;
        }
        return lt->query(dex) + rt->query(dex);
    }

    void debug() {
        cerr << "node " << l << " " << r << " bounds " << lb << " " << ub << endl;
    }

    void preorder() {
        propagate();
        debug();
        if(lt) {
            lt->preorder();
            rt->preorder();
        }
    }
};


void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
    Segtree st(0,n-1);
    for(int i = 0; i < k; i++) {
        bool type = (op[i] == 1 ? 1 : 0);
        if(type) {
            // add aka maximize
            st.maximize(left[i],right[i],height[i]);
        } else {
            st.minimize(left[i],right[i],height[i]);
        }
    }
    // st.preorder();
    for(int i = 0; i < n; i++) {
        finalHeight[i] = st.query(i);
    } 
}

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