Champion Contest

View as PDF

Submit solution


Points: 7
Time limit: 1.0s
Memory limit: 256M

Author:
Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

gunners101101 likes to play LOL (League of Legends). He currently has a list of champions, each with a value v_i, denoting how good the champion is. If a champion has a higher value than another champion, v_a > v_b, then a will win in a 1 on 1 fight with champion 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 champions, and k friendships. You are to find the number of champions each champion can defeat.

Input Specification

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

Second line, n space separated integers v_i denoting the value of each champion.

Next k lines, two integers a_i and b_i, denoting that a_i and 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
  • 0 \le k \le \min(10^5, \frac{n(n-1)}{2})
  • 1 \le v_i \le 10^9
  • 1 \le a_i, b_i \le n
  • All pairs of a_i and b_i are unique, and a_i \ne b_i

Sample Input

4 2
10 4 10 15
1 2
4 3

Sample Output

0 0 1 2

Explanation Of Sample

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


  • 1
    edwinwaterloo  commented on July 20, 2020, 5:51 p.m.

    Why can't I use NumPy for my program?


  • 1
    pblpbl  commented on Oct. 13, 2019, 9:26 p.m. edited

    Why am I getting TLE? edit: fixed


    • 11
      magicalsoup  commented on Oct. 13, 2019, 10:07 p.m.

      Because your program is too slow.