oj.uz

Submission #900680

# Submission time Handle Problem Language Result Execution time Memory
900680 2024-01-08T21:15:29 Z sverma22 Wall (IOI14_wall) C++17
100 / 100
 693 ms 67292 KB 
#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.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 444 KB Output is correct
3 Correct 2 ms 508 KB Output is correct
4 Correct 5 ms 860 KB Output is correct
5 Correct 4 ms 912 KB Output is correct
6 Correct 4 ms 860 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 106 ms 14192 KB Output is correct
3 Correct 146 ms 8020 KB Output is correct
4 Correct 420 ms 20700 KB Output is correct
5 Correct 286 ms 21228 KB Output is correct
6 Correct 266 ms 19540 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 5 ms 704 KB Output is correct
5 Correct 4 ms 856 KB Output is correct
6 Correct 4 ms 856 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 102 ms 13904 KB Output is correct
9 Correct 161 ms 8120 KB Output is correct
10 Correct 415 ms 20568 KB Output is correct
11 Correct 269 ms 21072 KB Output is correct
12 Correct 268 ms 19592 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 103 ms 13988 KB Output is correct
15 Correct 24 ms 1880 KB Output is correct
16 Correct 424 ms 20820 KB Output is correct
17 Correct 268 ms 20008 KB Output is correct
18 Correct 268 ms 20120 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 5 ms 704 KB Output is correct
5 Correct 4 ms 860 KB Output is correct
6 Correct 4 ms 860 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 102 ms 13836 KB Output is correct
9 Correct 149 ms 8016 KB Output is correct
10 Correct 415 ms 20696 KB Output is correct
11 Correct 275 ms 21188 KB Output is correct
12 Correct 266 ms 19568 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 104 ms 14016 KB Output is correct
15 Correct 24 ms 1900 KB Output is correct
16 Correct 413 ms 20532 KB Output is correct
17 Correct 272 ms 20124 KB Output is correct
18 Correct 270 ms 20052 KB Output is correct
19 Correct 655 ms 67156 KB Output is correct
20 Correct 638 ms 67148 KB Output is correct
21 Correct 646 ms 67152 KB Output is correct
22 Correct 634 ms 67156 KB Output is correct
23 Correct 643 ms 67156 KB Output is correct
24 Correct 636 ms 67152 KB Output is correct
25 Correct 640 ms 67148 KB Output is correct
26 Correct 693 ms 67152 KB Output is correct
27 Correct 644 ms 67292 KB Output is correct
28 Correct 633 ms 67156 KB Output is correct
29 Correct 634 ms 67152 KB Output is correct
30 Correct 635 ms 67152 KB Output is correct