4D longest path - FlandreOJ: Flandre Online Judge

4D longest path

Time limit: 1000 ms
Memory limit: 256 MB
In a four-dimensional space, there are $n$ points $x_i=(a_i,b_i,c_i,d_i)$. It's possible to move from point $x_i$ to point $x_j$ if $a_i \leq a_j$, $b_i \leq b_j$, $c_i \leq c_j$, and $d_i \leq d_j$. Find the longest path passing through each point at most once. You can start from any point. ### Input - The first line contains an integer $n$. - The next $n$ lines each contain four integers $a_i, b_i, c_i, d_i$. ### Output - Print an integer, the maximum number of points that can be visited. ### Constraints - $1 \leq n \leq 5 \times 10^4$. - $1 \leq a_i, b_i, c_i, d_i \leq 10^9$. ### Example Input: ``` 3 2 3 4 4 1 2 3 4 2 2 1 3 ``` Output: ``` 2 ```