I would do it with 2d segment tree for max. The LIS for the current position is just max in rectangle [(0, 0) — (xi — 1, yi — 1)] + 1. After that we need to update current position (xi, yi) with the current value of LIS. Its really similar to the solution of LIS of integers except the fact it uses 2d segment tree/BIT. In my opinion this solution is much easier to write and understand.

You can just process all pairs by increasing y, and if some of them have the same y then process them by increasing x. Now if we are proccesing pair (x_i, y_i), then its' result r_i equals to 1 + max r_j where j < i, xj < xi. You can get this max by using segment tree where for each y you store maximal result of already proccesed pairs with exact y. Because cordinates can be up to 10⁹, you need to compress them so you will be able to store them in tree (it's needed only for y). Answer for whole task is maximum result of all pairs.

Numerous O(nlg^2n) solution exists for this problem, and this is my favorite solution.

dp formula is : dp[i] = Max(xj < xi, yj < yi, j < i) dp[j] + 1. In this formula we are considering all O(n^2) pairs one by one — which is slow. Now, I will calculate this table faster with divide & conquer approach.

Let solve(s, e) -> calculate all dp value pairs from s to e. What we will do is -

• call solve(s, m) to get dp values (m = (s+e)/2)

• "propagate" the dp values from [s, m] to [m+1, e]

• call solve(m+1, e) to get the rest.

when we are doing D&C, we should still consider all O(n^2) pairs. This is why we propagate all the values from [s, m] to [m+1, e].

Naive propagation can be done by this short code :

for(i = [m+1, e]) update dp[i] to Max(xj < xi, yj < yi, j = [s, m]) dp[j] + 1

But notice that [s, m] and [m+1, e] are disjoint intervals — which eliminates the needs to consider for i < j. We can preprocess the values in [s, m] by sorting in xcoord & maintaining segment trees by ycoord. Now, updating values in [m+1, e] can be replaced by simple queries.

Time complexity is T(N) = 2T(N/2) + O(NlgN), we can show T(N) = O(Nlg^2N) by master's theorem. Memory complexity is O(N) (which is a lot better than 2d segtrees.)

I implemented a solution using 2D BIT with coordinate compression. We only create entries on the map as needed, so memory and runtime are both O(Nlog^2N). I used unordered_map to speed up the queries, but I'm still getting TLE #3.

I tested it on my computer and it runs in around 2 seconds for the worst test case, but the problem asks for runtime under 0.345 seconds...

I wonder if anyone has anything faster than O(Nlog^2N).

I believe it can be solved in O(nlog(n)^2) in the same manner as usual LIS but with constant less than in segment tree. Let dp[i] denote the set containing smallest elements where subsequence of length i could end(if we sort first elements in this set, the second elements will be anti-sorted).Now upper bound will work in the same manner instead of array of sorted elements d[i] we get array of sorted array sets. I am not sure about that:)

There was a comment that said this problem is similar to problem NICEDAY on spoj. But I can't see the similarity. Does anyone know how?