P9272 [CEOI 2013] Land of a Thousand Islands / Adritic

Translated from [CEOI 2013 Day 2](https://ceoi2013.hsin.hr/tasks/tasks_day2.pdf). “Land of a Thousand Islands” was the official slogan of Croatia’s tourism industry in the mid-1990s. Although the slogan is not actually accurate (Croatia has slightly more than $1000$ islands), “island hopping” (sailing from one island to another) is a popular summer activity. The map of the Adriatic Sea is represented by a grid of unit squares with $2500$ rows and $2500$ columns. Rows are numbered from north to south as $1$ to $2500$, and columns are numbered from west to east as $1$ to $2500$. There are $N$ islands in the sea, numbered from $1$ to $N$, and each island lies inside one unit square of the grid. The position of island $K$ is given by the coordinates of that grid cell: its row number $R_K$ and column number $C_K$. No two islands share the same position. Due to wind and sea currents, you can sail directly from one island to another only when island $B$ is roughly to the northwest or southeast of $A$. More precisely, you can “hop” from island $A$ to island $B$ only if either $R_A < R_B$ and $C_A < C_B$ both hold, or $R_A > R_B$ and $C_A > C_B$ both hold. Note that the distance between two islands, or the presence of other islands, does not affect whether it is possible to hop from one to the other. If it is not possible to hop directly from $A$ to $B$, you may be able to travel from $A$ to $B$ using a sequence of hops via other islands. The travel distance from $A$ to $B$ is defined as the minimum number of hops needed to get from $A$ to $B$.  For example, in the figure above, starting from the island located at row $2$, column $3$, we can hop to four other islands, while the travel distance to the remaining two islands is two hops.

A sailing regatta is being planned, and the organizers are considering each island as a possible venue. For each candidate island, they want to know: if every other island sends a sailboat, what is the minimum total number of hops required for all sailboats to reach the candidate island, or equivalently, what is the sum of travel distances from all other islands to the candidate island. Write a program that, given the positions of $N$ islands, computes for each island $K$ the sum of travel distances from all other islands to island $K$. The testdata guarantee that for every pair of islands $A$ and $B$, it is possible to travel from $A$ to $B$ using some sequence of hops.

The first line contains an integer $N$ ($1\le N\le250000$), the number of islands. The next $N$ lines contain the island positions. Each position is given as a pair of integers between $1$ and $2500$ (inclusive), representing the row number and the column number.

Output $N$ lines. For each island, in the order given in the input, output the sum of travel distances from all other islands to that island, one line per island.

In $25\%$ of the test cases, $N$ is at most $100$. In $50\%$ of the test cases, $N$ is at most $1500$. In $60\%$ of the test cases, $N$ is at most $5000$. In $80\%$ of the test cases, $N$ is at most $25000$. In $100\%$ of the test cases, $1\le N\le250000$. **Note: $N$ can be $1$.** Translated by ChatGPT 5