LIS Nghiêm Ngặt Và Không Giảm
Points
34
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
Uncategorized
Đề bài
Cho mảng gồm $N$ số nguyên $a_1, \dots, a_N$. Hãy tìm:
- Độ dài dãy con tăng nghiêm ngặt dài nhất ($a_{i_1} < a_{i_2} < \dots < a_{i_k}$).
- Độ dài dãy con không giảm dài nhất ($a_{i_1} \le a_{i_2} \le \dots \le a_{i_k}$).
Dữ liệu vào
- Dòng đầu chứa số nguyên $N$ ($1 \le N \le 2 \times 10^5$).
- Dòng thứ hai chứa $N$ số nguyên $a_1, \dots, a_N$ ($-10^9 \le a_i \le 10^9$).
Dữ liệu ra
- In ra hai số nguyên trên một dòng: độ dài LIS nghiêm ngặt và độ dài LNDS không giảm.
Ví dụ
| Input | Output |
|---|---|
| 5 2 2 2 2 2 |
1 5 |
Giới hạn
- $1 \le N \le 2 \times 10^5$, $-10^9 \le a_i \le 10^9$
Community Discussion