Elearning CodePath – CTP Online Judge

Maximum Difference

DIFFS

🟢 Hard #General

### 📌 Thông tin chung

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

Cho $N$ loại giống cây khác nhau, cây thứ $i$ có chiều cao $h_i$. Nhiệm vụ của trạm thử nghiệm là thực hiện hai công việc:

1.  Tìm ra hiệu lớn nhất về độ cao của một cặp cây trồng bất kỳ, tức là tìm $\max(|h_i - h_j|)$ với $1 \le i, j \le N$.
2.  Đếm số cách chọn các cặp cây trồng $(i, j)$ có hiệu độ cao bằng hiệu lớn nhất vừa tìm được.

Yêu cầu: Lập trình giúp trạm nghiên cứu thực hiện hai công việc trên.

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

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

* Dòng 1: Một số nguyên $N$: số loại giống cây.
* Dòng 2: Gồm $N$ số nguyên $h_1, h_2, \dots, h_N$, cách nhau bởi một dấu cách, là chiều cao của các cây.

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

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

Ghi ra file `DIFFS.OUT` một dòng duy nhất chứa hai số nguyên, lần lượt là:
1.  Hiệu lớn nhất về độ cao của một cặp cây trồng bất kỳ.
2.  Số cách chọn các cặp cây trồng có hiệu lớn nhất.

---
### ✨ Ví dụ

| Input | Output |
| :--- | :--- |
| `5` <br> `3 1 2 3 1` | `2 4` |

---
### 🏷 Subtasks

| Subtask | Ràng buộc | Tỷ lệ điểm |
| :--- | :--- | :--- |
| 1 | $1 \le N \le 10^2$; $1 \le h_i \le 10^5$ | $40\%$ |
| 2 | $10^2 < N \le 10^3$; $10^5 < h_i \le 10^6$ | $30\%$ |
| 3 | $1 \le N \le 2 \times 10^5$; $1 \le h_i \le 10^9$ | $30\%$ |

---

✅ Đã AC: 2 / 16 submissions