Trạm phát sóng vượt trội

Buổi 24 — Mock Contest Phase 1
Points
8
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
Uncategorized
Submissions
Đề bài

Một mạng lưới viễn thông gồm $N$ trạm phát sóng đánh số từ $1$ đến $N$ và $M$ đường kết nối hai chiều giữa các cặp trạm. Mỗi trạm $i$ có công suất phát sóng $A_i$.

Một trạm $u$ được gọi là vượt trội nếu công suất của nó lớn hơn hẳn công suất của tất cả các trạm kết nối trực tiếp với nó (tức là $A_u > A_v$ với mọi $v$ kề với $u$). Nếu một trạm không có trạm nào kề với nó, nó mặc nhiên được coi là vượt trội.

Hãy đếm số lượng trạm vượt trội trong mạng lưới.

Dữ liệu vào
  • Dòng đầu chứa hai số nguyên $N, M$ ($1 \le N \le 10^5$, $0 \le M \le 2 \cdot 10^5$).
  • Dòng thứ hai chứa $N$ số nguyên $A_1, A_2, \dots, A_N$ ($1 \le A_i \le 10^9$).
  • $M$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $u, v$ ($1 \le u, v \le N$, $u \ne v$) mô tả một đường kết nối hai chiều.
Dữ liệu ra
  • In ra một số nguyên duy nhất là số lượng trạm vượt trội.
Ví dụ
Input Output
4 3
10 5 8 3
1 2
2 3
3 4
2
5 4
4 4 4 4 4
1 2
2 3
3 4
4 5
0
Giới hạn
  • $1 \le N \le 10^5$, $0 \le M \le 2 \cdot 10^5$.
  • $1 \le A_i \le 10^9$.
Draft saved