Submission #900680

#	Time	Username	Problem	Language	Result	Execution time	Memory
900680		sverma22	Wall (IOI14_wall)	C++17	100 / 100	693 ms	67292 KiB

wall

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

class SegTree {

    public: 
    int sz_; 
    int n_; 
    vector<int> mini_, maxi_; 
    SegTree(int n) {
        n_= n; 
        sz_ = 1; 
        while(sz_ < n) sz_ *= 2; 
        mini_.resize(2 * sz_); // i think it went like this 
        maxi_.resize(2 * sz_); 
    } // no need to build b/c all 0s anyways 

    void upd_min(int l, int r, int val) {
        upd_min(l, r, val, 1, 1, n_); 
    }

    // is this all there is ?!? 
    void upd_min(int l, int r, int val, int node, int lx, int rx) {
        // always need to propagate initially 
        // which this time means checking the parent a bit diff way of doing things but might be okay
        int par = node / 2; 
        if(par != 0) {
            mini_[node] = min(max(mini_[node], mini_[par]), maxi_[par]); 
            maxi_[node] = max(min(maxi_[node], maxi_[par]), mini_[par]); 
        }

        if(rx < l || r < lx) return; 
        if(l <= lx && rx <= r) { 
            maxi_[node] = min(maxi_[node], val); 
            mini_[node] = min(mini_[node], val); 
            // but the children god damn this is hard to think ab [every child is lazy then] 
            return; 
        }

        int mid = (lx + rx) / 2; 
        upd_min(l, r, val, 2 * node, lx, mid); 
        upd_min(l, r, val, 2 * node + 1, mid + 1, rx); 
        mini_[node] = min(mini_[2 * node], mini_[2 * node + 1]); 
        maxi_[node] = max(maxi_[2 * node], maxi_[2 * node + 1]); 
    }

    void upd_max(int l, int r, int val) {
        upd_max(l, r, val, 1, 1, n_); 
    }

    // is this all there is ?!? 
    void upd_max(int l, int r, int val, int node, int lx, int rx) {
        // always need to propagate initially 
        // which this time means checking the parent a bit diff way of doing things but might be okay
        int par = node / 2; 
        if(par != 0) {
            mini_[node] = min(max(mini_[node], mini_[par]), maxi_[par]); 
            maxi_[node] = max(min(maxi_[node], maxi_[par]), mini_[par]); 
        }

        if(rx < l || r < lx) return; 
        if(l <= lx && rx <= r) { 
            maxi_[node] = max(maxi_[node], val); 
            mini_[node] = max(mini_[node], val); 
            // but the children god damn this is hard to think ab [every child is lazy then] 
            return; 
        }

        int mid = (lx + rx) / 2; 
        upd_max(l, r, val, 2 * node, lx, mid); 
        upd_max(l, r, val, 2 * node + 1, mid + 1, rx); 
        mini_[node] = min(mini_[2 * node], mini_[2 * node + 1]); 
        maxi_[node] = max(maxi_[2 * node], maxi_[2 * node + 1]); 
    }

    void query(int node, int l, int r, vector<int> &ans) {
        int par = node / 2; 
        if(par != 0) {
            mini_[node] = min(max(mini_[node], mini_[par]), maxi_[par]); 
            maxi_[node] = max(min(maxi_[node], maxi_[par]), mini_[par]); 
        }
        if(l == r) {
            ans[l] = mini_[node]; 
            return; 
        }
        int mid = (l + r) / 2; 
        query(2 * node, l, mid, ans); 
        query(2 * node + 1, mid + 1, r, ans); 
        mini_[node] = min(mini_[2 * node], mini_[2 * node + 1]); 
        maxi_[node] = max(maxi_[2 * node], maxi_[2 * node + 1]); 
    }

}; 

// w/ segtree working w/ own test case is real nice 

// this input format is mad annoying 
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
    // need to construct a seg tree 

    SegTree st(n); 

    for(int i = 0; i < k; i++) {
        if(op[i] == 1) {
            st.upd_max(left[i] + 1, right[i] + 1, height[i]); 
        } else {
            st.upd_min(left[i] + 1, right[i] + 1, height[i]); 
        }
    }


    vector<int> ans(n + 1); 
    st.query(1, 1, n, ans); 

    for(int i = 1; i <= n; i++) {
        finalHeight[i - 1] = ans[i]; 
    }
}

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

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