Elearning CodePath – CTP Online Judge

Thí sinh nổi bật

DP006

🟢 Hard #Dynamic Programming #Segment Tree #Fenwick Tree #Interval #Data Structure

### 📌 Thông tin chung

---
### 📝 Định nghĩa Thí sinh Nổi bật

Có $N$ thí sinh tham gia một cuộc thi bốn môn phối hợp.
Thí sinh $i$ có thứ hạng là $(R_{i,1}, R_{i,2}, R_{i,3}, R_{i,4})$ tương ứng với bốn môn. Giá trị nhỏ hơn thể hiện thứ hạng cao hơn.

Thí sinh $i$ được gọi là **nổi bật** nếu **không có** thí sinh $j$ nào khác ($j \ne i$) thỏa mãn điều kiện:
$$
R_{j,1} < R_{i,1} \quad \text{VÀ} \quad R_{j,2} < R_{i,2} \quad \text{VÀ} \quad R_{j,3} < R_{i,3} \quad \text{VÀ} \quad R_{j,4} < R_{i,4}
$$
(Thí sinh $j$ có thứ hạng cao hơn thí sinh $i$ trong **cả bốn môn**).

---
### 📝 Yêu cầu

Hãy xác định **số lượng** thí sinh nổi bật của cuộc thi.

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

* Dòng 1: Số nguyên $N$ là số thí sinh.
* $N$ dòng tiếp theo: Dòng $i$ ghi bốn số nguyên $R_{i,1}, R_{i,2}, R_{i,3}, R_{i,4}$ là thứ hạng của thí sinh $i$.

Giới hạn:
* $N$ là số thí sinh.
* Thứ hạng $R_{i,k}$ đều thuộc phạm vi $[1, N]$.
* Phần tử của mỗi dãy $R_{i,1}, \dots, R_{i,4}$ đều là đôi một phân biệt (tức là không có hai thí sinh nào có cùng thứ hạng trong cùng một môn).

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

Dòng duy nhất ghi số nguyên là số lượng thí sinh nổi bật của cuộc thi.

---
### ✨ Ví dụ

| Input | Output | Giải thích ví dụ |
| :---: | :---: | :--- |
| `4` <br> `4 3 2 3` <br> `1 2 1 1` <br> `2 4 4 2` <br> `3 1 3 4` | `2` | Hai thí sinh: $\mathbf{2}$ (thứ hạng $(1, 2, 1, 1)$) và $\mathbf{4}$ (thứ hạng $(3, 1, 3, 4)$) là thí sinh nổi bật (không ai có thứ hạng cao hơn mỗi người trong cả bốn môn thi). |

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

| \# | Điểm | Ràng buộc bổ sung | Kỹ thuật (Giả định) | Tỷ lệ điểm |
| :---: | :---: | :--- | :--- | :--- |
| $1$ | $50\%$ | $N \le 5000$ | $O(N^2)$ (Duyệt cặp) | $50\%$ |
| $2$ | $50\%$ | Không có ràng buộc bổ sung (Giả định $N \le 10^5$) | $O(N \log N)$ (Sử dụng cấu trúc dữ liệu 2D/3D hiệu quả) | $50\%$ |

---

✅ Đã AC: 0 / 0 submissions