Pawns
Contest: Kotlin Heroes: Episode 7
Tags: *special

There is an infinite chessboard, divided into cells. The cell $$$(x, y)$$$ is the cell on the intersection of the $$$x_i$$$-th row and $$$y_i$$$-th column. $$$n$$$ black pawns are placed on the board, the $$$i$$$-th black pawn occupies the cell $$$(x_i, y_i)$$$.

You want to capture all black pawns. In order to do so, you may perform the following actions:

- place a white pawn into any empty cell (any cell having integer coordinates can be chosen, as long as it doesn't contain any pawns);
- make a move with one of the white pawns according to the chess rules.

Recall that when you make a move with a white pawn in the cell $$$(x, y)$$$, the chess rules allow you to choose exactly one of these actions:

- if there is a black pawn in the cell $$$(x + 1, y - 1)$$$, you can capture it — the black pawn is removed from the board, and the white pawn moves to $$$(x + 1, y - 1)$$$;
- if there is a black pawn in the cell $$$(x + 1, y + 1)$$$, you can capture it — the black pawn is removed from the board, and the white pawn moves to $$$(x + 1, y + 1)$$$;
- if the cell $$$(x + 1, y)$$$ is empty, you can move the white pawn to that cell.

You may perform any finite sequence of actions (placing white pawns and moving them). You want to capture all of the black pawns, and it can be shown that it is always possible; and you want to do it placing as few white pawns as possible.

What is the minimum number of white pawns you have to place to capture all $$$n$$$ black pawns?

Input format:
The first line contains one integer $$$n$$$ ($$$1 \le n \le 5 \cdot 10^5$$$) — the number of black pawns.

Then $$$n$$$ lines follow. The $$$i$$$-th line contains two integers $$$x_i$$$ and $$$y_i$$$ ($$$1 \le x_i, y_i \le 5 \cdot 10^5$$$) denoting a black pawn in the cell $$$(x_i, y_i)$$$. No cell is occupied by two or more black pawns.

Output format:
Print one integer — the minimum number of white pawns you have to place to capture all $$$n$$$ black pawns.

Constraints:
Time limit: 5.0 s
Memory limit: 256.0 MB

Example input:
3
1 1
5 1
2 2

Example output:
1

Example input:
3
3 2
1 3
1 1

Example output:
2

Editorial:
Firstly, let's drop the constraint that white pawns can only be in empty cells. We will solve the problem assuming that white pawns can share cells with each other and/or black pawns without any special effects.
Let's analyze the sequence of black pawns captured by some white pawn. Suppose that some white pawn captures some black pawn $$$i$$$, and then — some other black pawn $$$j$$$. Then the following condition should hold: $$$x_j > x_i$$$ and $$$|y_j - y_i| = 1$$$. So, if we build a directed graph such that each vertex represents a black pawn, and there is an arc from vertex $$$i$$$ to vertex $$$j$$$ if $$$x_j > x_i$$$ and $$$|y_j - y_i| = 1$$$, then each sequence of pawns captured by some white pawn is represented by a path in this graph, and similarly, each path in this graph represents a possible sequence of captures of some white pawn. Since we need to capture all of the black pawns using the minimum possible number of white pawns, it means that we should cover the vertices of this graph using the minimum possible number of non-intersecting paths. Since this graph is a DAG, this problem can be solved with maximum matching (we'll describe the solution and analyze how can it be improved a bit later).
We dropped the constraint that no cell can contain more than one pawn, but in fact, it doesn't change the answer. The only problem which can arise from this constraint is that we have to move white pawns in some sequence, and it's not always possible to move some white pawn (it can be blocked). If we want to move some white pawn to a position with a black pawn, let's move the pawn that will capture that black pawn first (and force it to capture that black pawn). If we want to move some white pawn to a position with another white pawn, we can assume that these pawns are "swapped" — the remaining parts of their paths can be interchanged, and the blocking white pawn can continue the path of the pawn we were considering.
Okay, now let's go back to the problem about covering a DAG, which can be solved with maximum matching. We have to build a bipartite graph, where each vertex of the original DAG is represented by two vertices: one vertex in the left part, and one vertex in the right part (let's denote the vertex representing $$$x$$$ in the left part as $$$x^-$$$, and the vertex representing $$$x$$$ in the right part as $$$x^+$$$). Each arc $$$i \to j$$$ of the original DAG should be represented by an edge connecting $$$i^-$$$ with $$$j^+$$$. So, the maximum matching in this bipartite graph corresponds to the set of arcs belonging to the paths we use to cover the DAG; and the more arcs belong to the paths — the fewer paths we need to cover everything.
Unfortunately, even building this bipartite graph is too slow, let alone running Kuhn (or any other matching algorithm) in it. Let's try to find the maximum independent set in this bipartite graph without actually building it. We will divide this graph into two independent sections:
• the first section contains the vertices $$$i^-$$$ for the pawns $$$i$$$ on odd verticals, and the vertices $$$j^+$$$ for the pawns $$$j$$$ on even verticals;
• the second section contains the vertices $$$i^-$$$ for the pawns $$$i$$$ on even verticals, and the vertices $$$j^+$$$ for the pawns $$$j$$$ on odd verticals.
No edge connects the vertices from different sections, so we can find the maximum independent set in each section separately. The main idea that will allow us to do it in $$$O(n \log n)$$$ is the following one: if a vertex $$$i^-$$$ on some vertical belongs to the maximum independent set, all vertices above it on the same vertical should also belong to the maximum independent set. Similarly, if a vertex $$$j^+$$$ on some vertical belongs to the maximum independent set, then all vertices below it on the same vertical should belong to the maximum independent set as well. This allows us to solve the problem for one section using the following dynamic programming: $$$dp_{a,b}$$$ is the maximum possible number of vertices in the maximum independent set if we considered $$$a$$$ first verticals, and took $$$b$$$ top/bottom pawns on the last vertical into our independent set. It's quite easy to recalculate this dynamic programming for the next vertical using sweepline approach.