Elearning CodePath – CTP Online Judge

Tầm nhìn Chiều cao

HEIGHT

🟢 Hard #General #Stack

### 📌 Thông tin chung

---

### 📝 Bài toán

Cho một hàng ngang gồm N học sinh, được đánh số từ 1 tới N theo thứ tự từ trái sang phải. Học sinh thứ i có chiều cao là Hi.

Hai học sinh i và j (i < j) được coi là nhìn thấy nhau nếu như không có bất kỳ học sinh nào ở giữa họ có chiều cao lớn hơn chiều cao của cả hai.
Điều kiện: Học sinh i và j nhìn thấy nhau <=> Với mọi k thỏa mãn i < k < j, ta có Hk < Hi và Hk < Hj.

Yêu cầu: Với mỗi học sinh i (1 <= i <= N), hãy đếm số lượng học sinh j khác (j != i) mà học sinh i có thể nhìn thấy và có cùng chiều cao (Hj = Hi).

---

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

Dữ liệu vào từ file height.inp:
* Dòng 1: Số nguyên dương T là số lượng bộ dữ liệu kiểm thử.
* T khối dữ liệu tiếp theo, mỗi khối gồm:
    - Dòng 1: Số nguyên dương N.
    - Dòng 2: N số nguyên dương H1, H2, ..., HN.

Giới hạn:
* $1 <= T <= 10.$
* $1 <= N <= 10^5.$
* $1 <= Hi <= 10^9.$
* Tổng N trong tất cả các bộ test không vượt quá $10^5$.

---

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

Ghi ra file height.out:
* Với mỗi bộ dữ liệu, in ra trên một dòng duy nhất N số nguyên cách nhau bởi dấu cách, số thứ i là kết quả của học sinh tương ứng.

---

### ✨ Ví dụ

| Input (height.inp) | Output (height.out) |
| :--- | :--- |
| 1 <br> 5 <br> 1 2 2 3 2 | 0 1 1 0 0 |

Giải thích:
- Học sinh 2 (H=2) nhìn thấy học sinh 3 (H=2) vì giữa họ không có ai.
- Học sinh 2 không nhìn thấy học sinh 5 (H=2) vì học sinh 4 (H=3) cao hơn chắn tầm nhìn.

---

### 🏷 Subtasks

| Subtask | Ràng buộc | Tỷ lệ điểm |
| :--- | :--- | :--- |
| 1 | N <= 2000 | 30% |
| 2 | N <= 10^5 | 70% |

✅ Đã AC: 0 / 5 submissions