LIS Nghiêm Ngặt Và Không Giảm

Binary-search Buổi 75-76 — Stress Test Dynamic Programming
Points
34
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
Uncategorized
Submissions
Đề bài

Cho mảng gồm $N$ số nguyên $a_1, \dots, a_N$. Hãy tìm:

  1. Độ 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}$).
  2. Độ 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$
Draft saved