Đỉnh của dãy Bitonic
Points
45
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
recursion
Đề bài
Một dãy số nguyên $a_1, a_2, \dots, a_N$ ($N \ge 3$) được gọi là dãy Bitonic nếu tồn tại một chỉ số đỉnh $p$ ($2 \le p \le N - 1$) sao cho $a_1 < a_2 < \dots < a_p$ và $a_p > a_{p+1} > \dots > a_N$. Hãy tìm giá trị tại đỉnh $a_p$ và vị trí $p$ bằng thuật toán $O(\log N)$.
Dữ liệu vào
- Dòng đầu tiên chứa số nguyên $N$.
- Dòng thứ hai chứa $N$ số nguyên $a_1, a_2, \dots, a_N$.
Dữ liệu ra
- Một dòng gồm hai số nguyên: $a_p$ và $p$.
Ví dụ
| Input | Output |
|---|---|
| 6\n1 4 9 12 7 2 | 12 4 |
Giới hạn
- $3 \le N \le 2 \cdot 10^5$
- $|a_i| \le 10^9$
Community Discussion