Elearning CodePath – CTP Online Judge

Sức mạnh Lớn nhất

MAXSTRONG

🟢 Hard #General

### 📌 Thông tin chung

---
### 📝 Bài toán

Cho một dãy $N$ học sinh, học sinh thứ $i$ có chiều cao $H_i$.
Một nhóm là một dãy các học sinh liên tiếp.
* **Kích cỡ** của nhóm là số lượng học sinh trong nhóm.
* **Sức mạnh** của nhóm được định nghĩa là chiều cao của học sinh thấp nhất (giá trị nhỏ nhất) trong nhóm đó.

Yêu cầu: Với mỗi kích cỡ nhóm $K$ ($1 \le K \le N$), tìm **sức mạnh lớn nhất** có thể của một nhóm học sinh với kích cỡ $K$.

Gọi $S(i, K)$ là sức mạnh của nhóm bắt đầu từ vị trí $i$ và có kích cỡ $K$:
$S(i, K) = \min(H_i, H_{i+1}, \dots, H_{i+K-1})$
Kết quả cần tìm $R_K$ cho mỗi $K$ là:
$R_K = \max_{1 \le i \le N-K+1} S(i, K)$

---
### 📥 Định dạng Đầu vào

Dữ liệu vào từ file `MAXSTRONG.INP`:

* Dòng 1: Ghi số nguyên dương $N$.
* Dòng 2: Ghi $N$ số nguyên dương $H_1, H_2, \dots, H_N$ (chiều cao của học sinh), cách nhau bởi dấu cách.

Giới hạn:
* $1 \le N \le 2 \times 10^5$.
* $1 \le H_i \le 10^9$.

---
### 📤 Định dạng Đầu ra

Ghi ra file `MAXSTRONG.OUT` một dòng duy nhất gồm $N$ số nguyên. Số thứ $K$ ($1 \le K \le N$) in ra là sức mạnh lớn nhất của nhóm học sinh cỡ $K$. Các số cách nhau bởi dấu cách.

---
### ✨ Ví dụ

| Input (`MAXSTRONG.INP`) | Output (`MAXSTRONG.OUT`) |
| :--- | :--- |
| `10` <br> `1 2 3 4 5 4 3 2 1 6` | `6 4 4 3 3 2 2 1 1 1` |

Giải thích:
* $K=1$: $\max(1, 2, \dots, 6) = 6$.
* $K=2$: Nhóm [4, 5] $\rightarrow \min=4$. Nhóm [5, 4] $\rightarrow \min=4$. Max là 4.
* $K=4$: Nhóm [2, 3, 4, 5] $\rightarrow \min=2$. Nhóm [3, 4, 5, 4] $\rightarrow \min=3$. Max là 3.

---
### 🏷 Subtask

| Subtask | Ràng buộc | Số điểm ước tính |
| :--- | :--- | :--- |
| 1 | $N \le 5000$ | $50\%$ |
| 2 | $N \le 2 \times 10^5$ | $50\%$ |

---

✅ Đã AC: 3 / 10 submissions