3454. Separate Squares II

/**
 * Problem: LeetCode 3454 - Separate Squares II
 * Difficulty: Hard
 * Language: Java
 * Author: CodeByTushu
 */
import java.util.*;

class Solution {
    // Event representing the start or end of a square along the y-axis
    static class Event implements Comparable<Event> {
        long y;
        int type; // +1 for square bottom (enter), -1 for square top (exit)
        long x1, x2;

        Event(long y, int type, long x1, long x2) {
            this.y = y;
            this.type = type;
            this.x1 = x1;
            this.x2 = x2;
        }

        @Override
        public int compareTo(Event other) {
            return Long.compare(this.y, other.y);
        }
    }

    // Segment Tree to maintain the union of x-intervals
    static class SegmentTree {
        int n;
        long[] xs;
        int[] count;
        long[] len;

        SegmentTree(long[] xs) {
            this.xs = xs;
            this.n = xs.length - 1; // number of elementary intervals [xs[i], xs[i+1]]
            this.count = new int[4 * n];
            this.len = new long[4 * n];
        }

        void update(int node, int start, int end, int l, int r, int val) {
            if (l <= start && end <= r) {
                count[node] += val;
            } else {
                int mid = start + (end - start) / 2;
                if (l <= mid) {
                    update(2 * node, start, mid, l, r, val);
                }
                if (r > mid) {
                    update(2 * node + 1, mid + 1, end, l, r, val);
                }
            }

            if (count[node] > 0) {
                len[node] = xs[end + 1] - xs[start];
            } else {
                if (start == end) {
                    len[node] = 0;
                } else {
                    len[node] = len[2 * node] + len[2 * node + 1];
                }
            }
        }

        long query() {
            return len[1];
        }
    }

    public double separateSquares(int[][] squares) {
        int n = squares.length;
        List<Event> events = new ArrayList<>(2 * n);
        long[] allX = new long[2 * n];
        int xIdx = 0;

        for (int[] sq : squares) {
            long x1 = sq[0];
            long y1 = sq[1];
            long l = sq[2];
            long x2 = x1 + l;
            long y2 = y1 + l;

            events.add(new Event(y1, 1, x1, x2));
            events.add(new Event(y2, -1, x1, x2));
            allX[xIdx++] = x1;
            allX[xIdx++] = x2;
        }

        Collections.sort(events);
        Arrays.sort(allX);

        // Deduplicate X coordinates
        int uniqueCount = 0;
        for (int i = 0; i < allX.length; i++) {
            if (i == 0 || allX[i] != allX[i - 1]) {
                allX[uniqueCount++] = allX[i];
            }
        }
        long[] xs = Arrays.copyOf(allX, uniqueCount);

        SegmentTree st = new SegmentTree(xs);

        // Strips between consecutive y-events
        // Each strip has: y1, y2, activeWidth, stripArea
        List<double[]> strips = new ArrayList<>();
        double totalArea = 0.0;

        int numEvents = events.size();
        int i = 0;
        int m = xs.length - 2;

        while (i < numEvents) {
            long currentY = events.get(i).y;

            // Apply all events occurring at currentY
            while (i < numEvents && events.get(i).y == currentY) {
                Event e = events.get(i);
                int l = Arrays.binarySearch(xs, e.x1);
                int r = Arrays.binarySearch(xs, e.x2) - 1;
                if (l <= r) {
                    st.update(1, 0, m, l, r, e.type);
                }
                i++;
            }

            if (i < numEvents) {
                long nextY = events.get(i).y;
                long width = st.query();
                long height = nextY - currentY;
                double stripArea = (double) width * height;
                if (stripArea > 0) {
                    strips.add(new double[]{(double) currentY, (double) nextY, (double) width, stripArea});
                    totalArea += stripArea;
                }
            }
        }

        double targetArea = totalArea / 2.0;
        double currentArea = 0.0;

        for (double[] strip : strips) {
            double y1 = strip[0];
            double y2 = strip[1];
            double width = strip[2];
            double area = strip[3];

            if (currentArea + area >= targetArea) {
                double needed = targetArea - currentArea;
                return y1 + (needed / width);
            }
            currentArea += area;
        }

        return events.get(0).y;
    }
}

"""
Problem: LeetCode 3454 - Separate Squares II
Difficulty: Hard
Language: Python
Author: CodeByTushu
"""
from bisect import bisect_left
from typing import List


class SegmentTree:

    def __init__(self, xs: List[int]):
        self.xs = xs
        self.n = len(xs) - 1
        self.count = [0] * (4 * self.n)
        self.length = [0] * (4 * self.n)

    def update(
        self,
        node: int,
        start: int,
        end: int,
        left: int,
        right: int,
        val: int,
    ) -> None:
        if left <= start and end <= right:
            self.count[node] += val
        else:
            mid = (start + end) // 2
            left_child = 2 * node
            right_child = 2 * node + 1
            if left <= mid:
                self.update(left_child, start, mid, left, right, val)
            if right > mid:
                self.update(right_child, mid + 1, end, left, right, val)

        if self.count[node] > 0:
            self.length[node] = self.xs[end + 1] - self.xs[start]
        else:
            if start == end:
                self.length[node] = 0
            else:
                self.length[node] = (
                    self.length[2 * node] + self.length[2 * node + 1]
                )

    def query(self) -> int:
        return self.length[1]


class Solution:

    def separateSquares(self, squares: List[List[int]]) -> float:
        events = []
        x_coords = set()

        for x, y, l in squares:
            events.append((y, 1, x, x + l))
            events.append((y + l, -1, x, x + l))
            x_coords.add(x)
            x_coords.add(x + l)

        events.sort(key=lambda e: e[0])
        xs = sorted(x_coords)
        tree = SegmentTree(xs)

        strips = []
        total_area = 0

        i = 0
        num_events = len(events)
        m = len(xs) - 2

        while i < num_events:
            curr_y = events[i][0]

            while i < num_events and events[i][0] == curr_y:
                _, event_type, x1, x2 = events[i]
                l_idx = bisect_left(xs, x1)
                r_idx = bisect_left(xs, x2) - 1
                if l_idx <= r_idx:
                    tree.update(1, 0, m, l_idx, r_idx, event_type)
                i += 1

            if i < num_events:
                next_y = events[i][0]
                width = tree.query()
                height = next_y - curr_y
                strip_area = width * height
                if strip_area > 0:
                    strips.append((curr_y, next_y, width, strip_area))
                    total_area += strip_area

        target = total_area / 2.0
        curr_area = 0.0

        for y1, y2, width, area in strips:
            if curr_area + area >= target:
                needed = target - curr_area
                return y1 + (needed / width)
            curr_area += area

        return float(events[0][0])

/**
 * Problem: LeetCode 3454 - Separate Squares II
 * Difficulty: Hard
 * Language: C++
 * Author: CodeByTushu
 */
#include <vector>
#include <algorithm>

using namespace std;

struct Event {
    long long y;
    int type; // +1 enter, -1 exit
    long long x1, x2;

    bool operator<(const Event& other) const {
        return y < other.y;
    }
};

class SegmentTree {
private:
    int n;
    const vector<long long>& xs;
    vector<int> count;
    vector<long long> len;

public:
    SegmentTree(const vector<long long>& x_coords) : xs(x_coords) {
        n = static_cast<int>(xs.size()) - 1;
        count.assign(4 * n, 0);
        len.assign(4 * n, 0);
    }

    void update(int node, int start, int end, int l, int r, int val) {
        if (l <= start && end <= r) {
            count[node] += val;
        } else {
            int mid = start + (end - start) / 2;
            if (l <= mid) {
                update(2 * node, start, mid, l, r, val);
            }
            if (r > mid) {
                update(2 * node + 1, mid + 1, end, l, r, val);
            }
        }

        if (count[node] > 0) {
            len[node] = xs[end + 1] - xs[start];
        } else {
            if (start == end) {
                len[node] = 0;
            } else {
                len[node] = len[2 * node] + len[2 * node + 1];
            }
        }
    }

    long long query() const {
        return len[1];
    }
};

class Solution {
public:
    double separateSquares(vector<vector<int>>& squares) {
        int n = squares.size();
        vector<Event> events;
        events.reserve(2 * n);
        vector<long long> xs;
        xs.reserve(2 * n);

        for (const auto& sq : squares) {
            long long x1 = sq[0];
            long long y1 = sq[1];
            long long l = sq[2];
            long long x2 = x1 + l;
            long long y2 = y1 + l;

            events.push_back({y1, 1, x1, x2});
            events.push_back({y2, -1, x1, x2});
            xs.push_back(x1);
            xs.push_back(x2);
        }

        sort(events.begin(), events.end());
        sort(xs.begin(), xs.end());
        xs.erase(unique(xs.begin(), xs.end()), xs.end());

        SegmentTree st(xs);

        struct Strip {
            double y1, y2, width, area;
        };
        vector<Strip> strips;
        double totalArea = 0.0;

        int numEvents = events.size();
        int i = 0;
        int m = static_cast<int>(xs.size()) - 2;

        while (i < numEvents) {
            long long currY = events[i].y;

            while (i < numEvents && events[i].y == currY) {
                const auto& e = events[i];
                int l = lower_bound(xs.begin(), xs.end(), e.x1) - xs.begin();
                int r = lower_bound(xs.begin(), xs.end(), e.x2) - xs.begin() - 1;
                if (l <= r) {
                    st.update(1, 0, m, l, r, e.type);
                }
                i++;
            }

            if (i < numEvents) {
                long long nextY = events[i].y;
                long long width = st.query();
                long long height = nextY - currY;
                double stripArea = static_cast<double>(width) * height;
                if (stripArea > 0) {
                    strips.push_back({static_cast<double>(currY), static_cast<double>(nextY), static_cast<double>(width), stripArea});
                    totalArea += stripArea;
                }
            }
        }

        double targetArea = totalArea / 2.0;
        double currentArea = 0.0;

        for (const auto& strip : strips) {
            if (currentArea + strip.area >= targetArea) {
                double needed = targetArea - currentArea;
                return strip.y1 + (needed / strip.width);
            }
            currentArea += strip.area;
        }

        return static_cast<double>(events[0].y);
    }
};

/**
 * Problem: LeetCode 3454 - Separate Squares II
 * Difficulty: Hard
 * Language: JavaScript
 * Author: CodeByTushu
 */
class SegmentTree {
    constructor(xs) {
        this.xs = xs;
        this.n = xs.length - 1;
        this.count = new Int32Array(4 * this.n);
        this.len = new Float64Array(4 * this.n);
    }

    update(node, start, end, l, r, val) {
        if (l <= start && end <= r) {
            this.count[node] += val;
        } else {
            const mid = (start + end) >> 1;
            if (l <= mid) {
                this.update(2 * node, start, mid, l, r, val);
            }
            if (r > mid) {
                this.update(2 * node + 1, mid + 1, end, l, r, val);
            }
        }

        if (this.count[node] > 0) {
            this.len[node] = this.xs[end + 1] - this.xs[start];
        } else {
            if (start === end) {
                this.len[node] = 0;
            } else {
                this.len[node] = this.len[2 * node] + this.len[2 * node + 1];
            }
        }
    }

    query() {
        return this.len[1];
    }
}

function binarySearch(arr, target) {
    let low = 0;
    let high = arr.length - 1;
    while (low <= high) {
        const mid = (low + high) >> 1;
        if (arr[mid] >= target) {
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }
    return low;
}

/**
 * @param {number[][]} squares
 * @return {number}
 */
var separateSquares = function(squares) {
    const events = [];
    const xSet = new Set();

    for (let i = 0; i < squares.length; i++) {
        const [x, y, l] = squares[i];
        events.push({ y, type: 1, x1: x, x2: x + l });
        events.push({ y: y + l, type: -1, x1: x, x2: x + l });
        xSet.add(x);
        xSet.add(x + l);
    }

    events.sort((a, b) => a.y - b.y);
    const xs = Array.from(xSet).sort((a, b) => a - b);

    const st = new SegmentTree(xs);
    const strips = [];
    let totalArea = 0;

    let i = 0;
    const numEvents = events.length;
    const m = xs.length - 2;

    while (i < numEvents) {
        const currY = events[i].y;

        while (i < numEvents && events[i].y === currY) {
            const e = events[i];
            const l = binarySearch(xs, e.x1);
            const r = binarySearch(xs, e.x2) - 1;
            if (l <= r) {
                st.update(1, 0, m, l, r, e.type);
            }
            i++;
        }

        if (i < numEvents) {
            const nextY = events[i].y;
            const width = st.query();
            const height = nextY - currY;
            const stripArea = width * height;
            if (stripArea > 0) {
                strips.push({ y1: currY, y2: nextY, width, area: stripArea });
                totalArea += stripArea;
            }
        }
    }

    const targetArea = totalArea / 2;
    let currentArea = 0;

    for (let j = 0; j < strips.length; j++) {
        const strip = strips[j];
        if (currentArea + strip.area >= targetArea) {
            const needed = targetArea - currentArea;
            return strip.y1 + (needed / strip.width);
        }
        currentArea += strip.area;
    }

    return events[0].y;
};