Elearning CodePath – CTP Online Judge

Thí sinh nổi bật

NONDOMIN

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

### 📌 Thông tin chung

---
Có $N$ thí sinh tham gia một cuộc thi bốn môn phối hợp.
Kết quả thi của mỗi môn cho ra một xếp hạng của mỗi thí sinh. Cụ thể, thí sinh $i$ đạt thứ hạng $(R_{i,1}, R_{i,2}, R_{i,3}, R_{i,4})$ ở tương ứng các môn thứ nhất, thứ hai, thứ ba và thứ tư. Các giá trị $R_{i,k}$ đều thuộc phạm vi $[1, N]$, giá trị nhỏ hơn thể hiện thứ hạng cao hơn. Phần tử của mỗi dãy $R_{i,k}$ đều là đôi một phân biệt.

Một thí sinh $i$ được gọi là nổi bật nếu không có một thí sinh $j$ nào khác ($j \ne i$) có thứ hạng cao hơn người đó trong cả bốn môn. Nghĩa là, thí sinh $i$ là nổi bật nếu không tồn tại thí sinh $j$ nào khác thoả mã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}
$$
Hãy xác định số lượng thí sinh nổi bật của cuộc thi.

---
### 📥 Dữ liệu

* 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$.

---
### 📤 Kết quả

* 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: 2 (thứ hạng $(1, 2, 1, 1)$) và 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). |

---
### 🏷 Subtasks

| \# | Điểm | Ràng buộc bổ sung | Kỹ thuật (Giả định) |
| :---: | :---: | :--- | :--- |
| $1$ | $50\%$ | $N \le 5000$ | $O(N^2)$ (Duyệt cặp) |
| $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ả) |

---

✅ Đã AC: 0 / 0 submissions