LIS2 - Another Longest Increasing Subsequence Problem
Given a sequence of N pairs of integers, find the length of the longest increasing subsequence of it.
An increasing sequence A1..An is a sequence such that for every i < j, Ai < Aj.
A subsequence of a sequence is a sequence that appears in the same relative order, but not necessarily contiguous.
A pair of integers (x1, y1) is less than (x2, y2) iff x1 < x2 and y1 < y2.
Input
The first line of input contains an integer N (2 ≤ N ≤ 100000).
The following N lines consist of N pairs of integers (xi, yi) (-109 ≤ xi, yi ≤ 109).
Output
The output contains an integer: the length of the longest increasing subsequence of the given sequence.
Example
Input: 8 1 3 3 2 1 1 4 5 6 3 9 9 8 7 7 6 Output: 3
hide comments
|
fr_sarker:
2023-11-24 10:53:33
helpfull Comment to solve this problem without segment tree:
|
|
albatroz:
2022-11-18 15:21:09
TL is too tight |
|
hyl_tianmeng:
2021-07-24 05:24:30
你好 |
|
mahmud2690:
2018-04-20 17:03:30
2D-BIT >> 2D-Segment tree... |
|
Md. Najim Ahmed:
2017-12-29 00:51:53
solved it n(log2n)^2 with 2d bit and grid compression ... |
|
rihaz_zahir:
2017-02-01 16:08:51
@theph0enix, (1, 3) is not less than (2, 3), that all we care, even if (2, 3) comes before (1, 3) we would say (2, 3) is not less than (1, 3) Last edit: 2017-02-01 16:11:23 |
|
rogerioagjr:
2016-07-21 03:28:19
TLE O(n*log(n)^2) :/ |
|
mkfeuhrer:
2016-06-29 22:11:58
dp gives tle !! LIS dp wont work! |
|
theph0enix:
2016-02-24 07:25:28
How do we compare (1, 3) and say (2, 3) since by the given definition of inequality these two pairs are neither less nor greater than the other. They cant even be considered equal since (1,3) is less than (2, 4) but (2, 4) is again neither less nor greater than (2, 3). |
|
abhishekrahul:
2015-12-21 05:28:01
what it means TLE #3 ???
|
| Added by: | Bin Jin |
| Date: | 2008-01-20 |
| Time limit: | 1s |
| Source limit: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Languages: | All except: CPP |
RSS