P12564 [UTS 2024] Jobs

You are given a set of $n$ points with integer coordinates. Each point has its own weight. We can split the plane using a point of coordinates $(x, y)$ into four dials by drawing the vertical line in $x + 0.5$ and the horizontal line in $y + 0.5$. We define the weight of a dial to be the sum of the weights of all the points in that dial. Furthermore, the $\underline{\text{imbalance}}$ of such a split is the maximum difference between the weight of two of its dials. For each integer $x$ such that $1 \leq x < n$, find the minimum imbalance of a split that uses a point on the vertical line $x$.

The first line contains an integer $n$ ($1 \leq n \leq 2 \cdot 10^5$). Each of the next $n$ lines contains three integers $x_i$, $y_i$, and $w_i$ ($1 \leq x_i, y_i \leq n$, $1 \leq w_i \leq 10^9$) --- the coordinates and weight of the $i$-th point.

The only line of the output should contain $n - 1$ integers, the required minimum imbalances.

- ($7$ points): $1 \leq n \leq 200$; - ($17$ points): $1 \leq n \leq 5000$; - ($53$ points): $1 \leq n \leq 100\,000$; - ($23$ points): no further restrictions.