3161. Block Placement Queries

/**
 * Problem: LeetCode 3161 - Block Placement Queries
 * Difficulty: Hard
 * Language: Java
 * Author: CodeByTushu
 */
import java.util.ArrayList;
import java.util.List;

class Solution {
    private int[] treeMax;
    private boolean[] treeHas;

    private void update(int node, int l, int r, int idx, int val, boolean has) {
        if (l == r) {
            treeMax[node] = val;
            treeHas[node] = has;
            return;
        }
        int mid = (l + r) >> 1;
        if (idx <= mid) {
            update(node << 1, l, mid, idx, val, has);
        } else {
            update((node << 1) | 1, mid + 1, r, idx, val, has);
        }
        treeMax[node] = Math.max(treeMax[node << 1], treeMax[(node << 1) | 1]);
        treeHas[node] = treeHas[node << 1] || treeHas[(node << 1) | 1];
    }

    private int queryMax(int node, int l, int r, int ql, int qr) {
        if (ql > r || qr < l) return 0;
        if (ql <= l && r <= qr) return treeMax[node];
        int mid = (l + r) >> 1;
        return Math.max(queryMax(node << 1, l, mid, ql, qr), queryMax((node << 1) | 1, mid + 1, r, ql, qr));
    }

    private int findPrev(int node, int l, int r, int ql, int qr) {
        if (ql > r || qr < l || !treeHas[node]) return -1;
        if (l == r) return l;
        int mid = (l + r) >> 1;
        int res = findPrev((node << 1) | 1, mid + 1, r, ql, qr);
        if (res != -1) return res;
        return findPrev(node << 1, l, mid, ql, qr);
    }

    private int findNext(int node, int l, int r, int ql, int qr) {
        if (ql > r || qr < l || !treeHas[node]) return -1;
        if (l == r) return l;
        int mid = (l + r) >> 1;
        int res = findNext(node << 1, l, mid, ql, qr);
        if (res != -1) return res;
        return findNext((node << 1) | 1, mid + 1, r, ql, qr);
    }

    public List<Boolean> getResults(int[][] queries) {
        int maxCoord = 0;
        for (int[] q : queries) {
            if (q[1] > maxCoord) {
                maxCoord = q[1];
            }
        }
        int M = maxCoord + 1;
        treeMax = new int[4 * M];
        treeHas = new boolean[4 * M];

        // Origin at 0 is an obstacle
        update(1, 0, M - 1, 0, 0, true);

        List<Boolean> ans = new ArrayList<>();
        for (int[] q : queries) {
            if (q[0] == 1) {
                int x = q[1];
                int prev = findPrev(1, 0, M - 1, 0, x - 1);
                int next = findNext(1, 0, M - 1, x + 1, M - 1);
                update(1, 0, M - 1, x, x - prev, true);
                if (next != -1) {
                    update(1, 0, M - 1, next, next - x, true);
                }
            } else {
                int x = q[1];
                int sz = q[2];
                int prev = findPrev(1, 0, M - 1, 0, x);
                int maxGap = Math.max(queryMax(1, 0, M - 1, 0, x), x - prev);
                ans.add(maxGap >= sz);
            }
        }

        return ans;
    }
}

"""
Problem: LeetCode 3161 - Block Placement Queries
Difficulty: Hard
Language: Python
Author: CodeByTushu
"""
from typing import List

class Solution:
    def getResults(self, queries: List[List[int]]) -> List[bool]:
        max_coord = max(q[1] for q in queries)
        M = max_coord + 1

        tree_max = [0] * (4 * M)
        tree_has = [False] * (4 * M)

        def update(node: int, l: int, r: int, idx: int, val: int, has: bool) -> None:
            if l == r:
                tree_max[node] = val
                tree_has[node] = has
                return
            mid = (l + r) // 2
            if idx <= mid:
                update(node * 2, l, mid, idx, val, has)
            else:
                update(node * 2 + 1, mid + 1, r, idx, val, has)
            tree_max[node] = max(tree_max[node * 2], tree_max[node * 2 + 1])
            tree_has[node] = tree_has[node * 2] or tree_has[node * 2 + 1]

        def query_max(node: int, l: int, r: int, ql: int, qr: int) -> int:
            if ql > r or qr < l:
                return 0
            if ql <= l and r <= qr:
                return tree_max[node]
            mid = (l + r) // 2
            return max(query_max(node * 2, l, mid, ql, qr), query_max(node * 2 + 1, mid + 1, r, ql, qr))

        def find_prev(node: int, l: int, r: int, ql: int, qr: int) -> int:
            if ql > r or qr < l or not tree_has[node]:
                return -1
            if l == r:
                return l
            mid = (l + r) // 2
            res = find_prev(node * 2 + 1, mid + 1, r, ql, qr)
            if res != -1:
                return res
            return find_prev(node * 2, l, mid, ql, qr)

        def find_next(node: int, l: int, r: int, ql: int, qr: int) -> int:
            if ql > r or qr < l or not tree_has[node]:
                return -1
            if l == r:
                return l
            mid = (l + r) // 2
            res = find_next(node * 2, l, mid, ql, qr)
            if res != -1:
                return res
            return find_next(node * 2 + 1, mid + 1, r, ql, qr)

        update(1, 0, M - 1, 0, 0, True)

        ans = []
        for q in queries:
            if q[0] == 1:
                x = q[1]
                prev = find_prev(1, 0, M - 1, 0, x - 1)
                nxt = find_next(1, 0, M - 1, x + 1, M - 1)
                update(1, 0, M - 1, x, x - prev, True)
                if nxt != -1:
                    update(1, 0, M - 1, nxt, nxt - x, True)
            else:
                x, sz = q[1], q[2]
                prev = find_prev(1, 0, M - 1, 0, x)
                max_gap = max(query_max(1, 0, M - 1, 0, x), x - prev)
                ans.append(max_gap >= sz)

        return ans

/**
 * Problem: LeetCode 3161 - Block Placement Queries
 * Difficulty: Hard
 * Language: C++
 * Author: CodeByTushu
 */
#include <vector>
#include <algorithm>

using namespace std;

class Solution {
    vector<int> treeMax;
    vector<bool> treeHas;

    void update(int node, int l, int r, int idx, int val, bool has) {
        if (l == r) {
            treeMax[node] = val;
            treeHas[node] = has;
            return;
        }
        int mid = (l + r) >> 1;
        if (idx <= mid) {
            update(node << 1, l, mid, idx, val, has);
        } else {
            update((node << 1) | 1, mid + 1, r, idx, val, has);
        }
        treeMax[node] = max(treeMax[node << 1], treeMax[(node << 1) | 1]);
        treeHas[node] = treeHas[node << 1] || treeHas[(node << 1) | 1];
    }

    int queryMax(int node, int l, int r, int ql, int qr) {
        if (ql > r || qr < l) return 0;
        if (ql <= l && r <= qr) return treeMax[node];
        int mid = (l + r) >> 1;
        return max(queryMax(node << 1, l, mid, ql, qr), queryMax((node << 1) | 1, mid + 1, r, ql, qr));
    }

    int findPrev(int node, int l, int r, int ql, int qr) {
        if (ql > r || qr < l || !treeHas[node]) return -1;
        if (l == r) return l;
        int mid = (l + r) >> 1;
        int res = findPrev((node << 1) | 1, mid + 1, r, ql, qr);
        if (res != -1) return res;
        return findPrev(node << 1, l, mid, ql, qr);
    }

    int findNext(int node, int l, int r, int ql, int qr) {
        if (ql > r || qr < l || !treeHas[node]) return -1;
        if (l == r) return l;
        int mid = (l + r) >> 1;
        int res = findNext(node << 1, l, mid, ql, qr);
        if (res != -1) return res;
        return findNext((node << 1) | 1, mid + 1, r, ql, qr);
    }

public:
    vector<bool> getResults(vector<vector<int>>& queries) {
        int maxCoord = 0;
        for (const auto& q : queries) {
            if (q[1] > maxCoord) {
                maxCoord = q[1];
            }
        }
        int M = maxCoord + 1;
        treeMax.assign(4 * M, 0);
        treeHas.assign(4 * M, false);

        // Origin at 0 is an obstacle
        update(1, 0, M - 1, 0, 0, true);

        vector<bool> ans;
        for (const auto& q : queries) {
            if (q[0] == 1) {
                int x = q[1];
                int prev = findPrev(1, 0, M - 1, 0, x - 1);
                int next = findNext(1, 0, M - 1, x + 1, M - 1);
                update(1, 0, M - 1, x, x - prev, true);
                if (next != -1) {
                    update(1, 0, M - 1, next, next - x, true);
                }
            } else {
                int x = q[1];
                int sz = q[2];
                int prev = findPrev(1, 0, M - 1, 0, x);
                int maxGap = max(queryMax(1, 0, M - 1, 0, x), x - prev);
                ans.push_back(maxGap >= sz);
            }
        }

        return ans;
    }
};

/**
 * Problem: LeetCode 3161 - Block Placement Queries
 * Difficulty: Hard
 * Language: JavaScript
 * Author: CodeByTushu
 */
/**
 * @param {number[][]} queries
 * @return {boolean[]}
 */
var getResults = function(queries) {
    let maxCoord = 0;
    for (let i = 0; i < queries.length; i++) {
        if (queries[i][1] > maxCoord) {
            maxCoord = queries[i][1];
        }
    }
    const M = maxCoord + 1;
    const treeMax = new Int32Array(4 * M);
    const treeHas = new Uint8Array(4 * M);

    function update(node, l, r, idx, val, has) {
        if (l === r) {
            treeMax[node] = val;
            treeHas[node] = has;
            return;
        }
        const mid = (l + r) >> 1;
        if (idx <= mid) {
            update(node << 1, l, mid, idx, val, has);
        } else {
            update((node << 1) | 1, mid + 1, r, idx, val, has);
        }
        treeMax[node] = Math.max(treeMax[node << 1], treeMax[(node << 1) | 1]);
        treeHas[node] = treeHas[node << 1] | treeHas[(node << 1) | 1];
    }

    function queryMax(node, l, r, ql, qr) {
        if (ql > r || qr < l) return 0;
        if (ql <= l && r <= qr) return treeMax[node];
        const mid = (l + r) >> 1;
        return Math.max(queryMax(node << 1, l, mid, ql, qr), queryMax((node << 1) | 1, mid + 1, r, ql, qr));
    }

    function findPrev(node, l, r, ql, qr) {
        if (ql > r || qr < l || !treeHas[node]) return -1;
        if (l === r) return l;
        const mid = (l + r) >> 1;
        const res = findPrev((node << 1) | 1, mid + 1, r, ql, qr);
        if (res !== -1) return res;
        return findPrev(node << 1, l, mid, ql, qr);
    }

    function findNext(node, l, r, ql, qr) {
        if (ql > r || qr < l || !treeHas[node]) return -1;
        if (l === r) return l;
        const mid = (l + r) >> 1;
        const res = findNext(node << 1, l, mid, ql, qr);
        if (res !== -1) return res;
        return findNext((node << 1) | 1, mid + 1, r, ql, qr);
    }

    // Origin 0 is an obstacle
    update(1, 0, M - 1, 0, 0, 1);

    const ans = [];
    for (let i = 0; i < queries.length; i++) {
        const q = queries[i];
        if (q[0] === 1) {
            const x = q[1];
            const prev = findPrev(1, 0, M - 1, 0, x - 1);
            const next = findNext(1, 0, M - 1, x + 1, M - 1);
            update(1, 0, M - 1, x, x - prev, 1);
            if (next !== -1) {
                update(1, 0, M - 1, next, next - x, 1);
            }
        } else {
            const x = q[1];
            const sz = q[2];
            const prev = findPrev(1, 0, M - 1, 0, x);
            const maxBefore = queryMax(1, 0, M - 1, 0, x);
            const maxGap = Math.max(maxBefore, x - prev);
            ans.push(maxGap >= sz);
        }
    }

    return ans;
};