Elearning CodePath – CTP Online Judge

Đếm Dãy Quà

COUNT

🟢 Hard #Two Pointers #Array

### 📌 Thông tin chung

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

Cho dãy $N$ phần quà có giá trị $a_1, a_2, \dots, a_N$.
Phần quà được nhận là một dãy con liên tiếp các phần quà mà trong đó tồn tại ít nhất một phần quà có giá trị lớn hơn hoặc bằng $M$.

Yêu cầu: Hãy đếm xem có bao nhiêu cách chọn quà thỏa mãn điều kiện trên.

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

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

* Dòng đầu: Ghi số $N$ (tổng số phần quà) và $M$ (giá trị ngưỡng), cách nhau bởi dấu cách.
* Dòng thứ hai: Ghi $N$ số nguyên là các giá trị của phần quà $a_i$. Các số cách nhau bởi một dấu cách.

Giới hạn:
* $1 \le N \le 10^5$.
* $1 \le M \le 10^6$.
* $1 \le a_i \le 10^6$.

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

Ghi ra file `COUNT.OUT` gồm một số duy nhất là kết quả cần tìm (số lượng dãy con thỏa mãn).

---
### ✨ Ví dụ

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

---
### 🏷 Ràng buộc

| Tỷ lệ điểm | Ràng buộc |
| :--- | :--- |
| $50\%$ | $1 \le N, M \le 20$; $a_i \le 10^2$ |
| $30\%$ | $20 < N, M \le 10^3$; $a_i \le 10^4$ |
| $20\%$ | $10^3 < N, M \le 10^5$; $a_i \le 10^6$ |

---

✅ Đã AC: 14 / 56 submissions