Champion Contest

Points: 7

Time limit: 1.0s

Memory limit: 256M

Author:

Problem type

gunners101101 likes to play LOL (League of Legends). He currently has a list of champions, each with a value $v_i$ $v_{i}$ , denoting how good the champion is. If a champion has a higher value than another champion, $v_a > v_b$ $v_{a} > v_{b}$ , then $a$ $a$ will win in a 1 on 1 fight with champion $b$ $b$ .

However, due to some lore hidden in this game, some champions are friends with other champions, as such, they refuse to fight, and the result of their fight will be a draw.

You are given $n$ $n$ champions, and $k$ $k$ friendships. You are to find the number of champions each champion can defeat.

Input Specification

First line, two integers $n$ $n$ and $k$ $k$ , denoting the number of champions and number of friendships.

Second line, $n$ $n$ space separated integers $v_i$ $v_{i}$ denoting the value of each champion.

Next $k$ $k$ lines, two integers $a_i$ $a_{i}$ and $b_i$ $b_{i}$ , denoting that $a_i$ $a_{i}$ and $b_i$ $b_{i}$ are friends.

Output Specification

For each champion, output the number champions that they can defeat, output the answer on one line separated by spaces.

Constraints

$2 \le n \le 10^5$ $2 \leq n \leq 10^{5}$
$0 \le k \le \min(10^5, \frac{n(n-1)}{2})$ $0 \leq k \leq min (10^{5}, \frac{n (n - 1)}{2})$
$1 \le v_i \le 10^9$ $1 \leq v_{i} \leq 10^{9}$
$1 \le a_i, b_i \le n$ $1 \leq a_{i}, b_{i} \leq n$
All pairs of $a_i$ $a_{i}$ and $b_i$ $b_{i}$ are unique, and $a_i \ne b_i$ $a_{i} \neq b_{i}$

Sample Input

Copy

Sample Output

Copy

0 0 1 2

Explanation for Sample Output

The first champion can only win against the second champion, but since they are friends, he cannot defeat any champion. The second champion has the lowest value, and thus he cannot defeat any other champion. The third champion can only defeat the second champion. The last champion can defeat all the champions except for the third champion, as they are friends.

Comments

0

edwinwaterloo commented on July 20, 2020, 9:51 p.m.

Why can't I use NumPy for my program?

1

planT_444 commented on Feb. 10, 2022, 2:58 p.m.

im kind of late but i think it's a third-party library that's not a part of the standard python modules