Problem:


Score : 300 points

Problem Statement

There are N observatories in AtCoder Hill, called Obs. 1, Obs. 2, ..., Obs. N. The elevation of Obs. i is H_i.
There are also M roads, each connecting two different observatories. Road j connects Obs. A_j and Obs. B_j.

Obs. i is said to be good when its elevation is higher than those of all observatories that can be reached from Obs. i using just one road.
Note that Obs. i is also good when no observatory can be reached from Obs. i using just one road.

How many good observatories are there?

Constraints

2 \leq N \leq 10^5

1 \leq M \leq 10^5

1 \leq H_i \leq 10^9

1 \leq A_i,B_i \leq N

A_i \neq B_i

Multiple roads may connect the same pair of observatories.

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N M
H_1 H_2 ... H_N
A_1 B_1
A_2 B_2
:
A_M B_M

Output

Print the number of good observatories.

Sample Input 1

4 3
1 2 3 4
1 3
2 3
2 4

Sample Output 1

2

From Obs. 1, you can reach Obs. 3 using just one road. The elevation of Obs. 1 is not higher than that of Obs. 3, so Obs. 1 is not good.

From Obs. 2, you can reach Obs. 3 and 4 using just one road. The elevation of Obs. 2 is not higher than that of Obs. 3, so Obs. 2 is not good.

From Obs. 3, you can reach Obs. 1 and 2 using just one road. The elevation of Obs. 3 is higher than those of Obs. 1 and 2, so Obs. 3 is good.

From Obs. 4, you can reach Obs. 2 using just one road. The elevation of Obs. 4 is higher than that of Obs. 2, so Obs. 4 is good.

Thus, the good observatories are Obs. 3 and 4, so there are two good observatories.

Sample Input 2

6 5
8 6 9 1 2 1
1 3
4 2
4 3
4 6
4 6

Sample Output 2

3



Sample input:
4 3
1 2 3 4
1 3
2 3
2 4


Sample output:
2

Submission status: Accepted

Solution code:
# import numpy as np
# import math
# import copy
# from collections import deque
import sys
input = sys.stdin.readline
# sys.setrecursionlimit(10000)


def main():
    N,M = map(int,input().split())
    H = list(map(int,input().split()))
    AB = [list(map(int,input().split())) for i in range(M)]

    next = [set([]) for i in range(N)]

    for i in range(M):
        temp1 = AB[i][0]
        temp2 = AB[i][1]
        next[temp1-1].add(temp2)
        next[temp2-1].add(temp1)

    res = 0

    for i in range(N):
        nownext = next[i]
        nowH = H[i]
        isGood = True
        for j in nownext:
            if H[j-1] >= nowH:
                isGood = False
                break
        if isGood:
            res += 1

    print(res)



main()

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
h = list(map(int, input().split()))
ab = [[int(i) for i in input().split()] for i in range(m)]
l = [1] * n
for i in range(m):
    if h[ab[i][0] - 1] < h[ab[i][1] - 1]:
        l[ab[i][0] - 1] = 0
    elif h[ab[i][0] - 1] > h[ab[i][1] - 1]:
        l[ab[i][1] - 1] = 0
    else:
        l[ab[i][0] - 1] = 0
        l[ab[i][1] - 1] = 0
ans = sum(l)
print(ans)

Submission status: Accepted

Solution code:
n, m = list(map(lambda x: int(x), input().split(' ')))
h = list(map(lambda x: int(x), input().split(' ')))

memo = {}

for i in range(m):
  a, b = list(map(lambda x: int(x), input().split(' ')))

  if not a in memo:
    memo[a] = h[b - 1]
  else:
    memo[a] = max(memo[a], h[b - 1])

  if not b in memo:
    memo[b] = h[a - 1]
  else:
    memo[b] = max(memo[b], h[a - 1])

count = 0

for i, v in memo.items():
  if h[i - 1] > v:
    count += 1

for i in range(1, n + 1):
  if not i in memo:
    count += 1

print(count)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
h = [-1] + list(map(int, input().split()))
ab = [list(map(int, input().split())) for _ in range(m)]

link = [[] for _ in range(n + 1)]
for x in ab:
    a, b = x[0], x[1]
    link[a].append(b)
    link[b].append(a)

ans = [0] + [1] * n
for i in range(len(link)):
    for j in link[i]:
        if h[i] <= h[j]:
            ans[i] = 0

print(sum(ans))

Submission status: Accepted

Solution code:
n,m = map(int, input().split())
h = list(map(int, input().split()))
t = [1 for i in range(n)]
for i in range(0,m):
    a,b = map(int, input().split())
    if h[a-1] >= h[b-1]:
        t[b-1] = 0
    if h[a-1] <= h[b-1]:
      t[a-1] = 0
print(sum(t))

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
h = list(map(int, input().split()))
lis = [1] * n
for i in range(m):
    a, b = map(int, input().split())
    h[a-1]
    h[b-1]

    if h[a-1] < h[b-1]:
        lis[a-1] = 0
    elif h[a-1] > h[b-1]:
        lis[b-1] = 0
    else:
        lis[a-1]=0
        lis[b-1]=0

print(len([i for i in lis if i == 1]))

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
H = list(map(int, input().split()))

x = []
for i in range(N):
    x.append(0)

for i in range(M):
    A1, A2 = map(int, input().split())
    if H[A1-1] > H[A2-1]:
        x[A2-1] = 1
    elif H[A1-1] < H[A2-1]:
        x[A1-1] = 1
    else:
        x[A1-1] = 1
        x[A2-1] = 1

count = 0
for num in x:
    if num == 0:
        count += 1

print(count)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
H = list(map(int, input().split()))

A = [[] for _ in range(n)]
for _ in range(m):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    A[u].append(v)
    A[v].append(u)

ans = 0
for i, a in enumerate(A):
    _max = H[i]
    flg = True
    for _a in a:
        if _max <= H[_a]:
            flg = False
            break
    if flg:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
hls=list(map(int,input().split()))
abls=[list(map(int,input().split())) for i in range(m)]
d={i+1:0 for i in range(n)}

for i in abls:
    left_h,right_h = hls[i[0]-1],hls[i[1]-1]
    if left_h>=right_h:
        d[i[1]] = -1
    if left_h<=right_h:
        d[i[0]] = -1
 
ans=0
for i in d.values():
    if i==0:
        ans+=1
print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for i2 in range(j)] for i3 in range(k)]
#import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value
#from collections import Counter # a = Counter(A).most_common()
#from itertools import accumulate #list(accumulate(A))

N, M = mi()
A = li()

flag = [0]*N
#for i in range(N):
    #flag[i] = A[i]
flag2 = [0]*N

for i in range(M):
    a, b = mi()
    a -= 1
    b -= 1
    flag[a] = max(A[a], A[b], flag[a])
    flag[b] = max(A[a], A[b], flag[b])
    if A[a] == A[b]:
        flag2[a] = flag2[b] = 1
cnt = 0
for i in range(N):
    if A[i] >= flag[i] and not flag2[i]:
        cnt += 1
print(cnt)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
h = list(map(int, input().split()))
a = [0]*m
b = [0]*m
route = [[] for i in range(n)]
ans = 0

for i in range(m):
    a[i], b[i] = map(int, input().split())
    a[i] -= 1
    b[i] -= 1
    route[a[i]].append(b[i])
    route[b[i]].append(a[i])

for i in range(n):
    flag = True
    for idx in route[i]:
        if h[i] <= h[idx]:
            flag = False
    if flag:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
H = list(map(int,input().split()))
AB = [[] for _ in range(N)]
count = 0
for _ in range(M):
  a,b = map(int,input().split())
  AB[a-1].append(H[b-1])
  AB[b-1].append(H[a-1])
for i in range(N):
  AB[i].sort()
for i in range(N):
  if AB[i] == []:
    count += 1
  elif H[i] > AB[i][-1]:
    count += 1
print(count)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# vim: set fileencoding=utf-8

# pylint: disable=unused-import, invalid-name, missing-docstring, bad-continuation


"""Module docstring
"""

import functools
import heapq
import itertools
import logging
import math
import random
import string
import sys
from argparse import ArgumentParser
from collections import defaultdict, deque
from copy import deepcopy
from typing import Dict, List, Optional, Set, Tuple


def solve(values: List[Tuple[int, int]], elevations: List[int], nb_obs: int) -> int:
    nb_higher_obs = [0] * nb_obs
    for a, b in values:
        a -= 1
        b -= 1
        if elevations[a] >= elevations[b]:
            nb_higher_obs[b] += 1
        if elevations[a] <= elevations[b]:
            nb_higher_obs[a] += 1
    return nb_higher_obs.count(0)


def do_job():
    "Do the work"
    LOG.debug("Start working")
    # first line is number of test cases
    N, M = map(int, input().split())
    Hs = list(map(int, input().split()))
    assert len(Hs) == N
    values = []
    for _ in range(M):
        values.append(tuple(map(int, input().split())))
    result = solve(values, Hs, N)
    print(result)


def print_output(testcase: int, result) -> None:
    "Formats and print result"
    if result is None:
        result = "IMPOSSIBLE"
    print("Case #{}: {}".format(testcase + 1, result))
    # 6 digits float precision {:.6f} (6 is the default value)
    # print("Case #{}: {:f}".format(testcase + 1, result))


def configure_log() -> None:
    "Configure the log output"
    log_formatter = logging.Formatter("%(lineno)d - " "%(message)s")
    handler = logging.StreamHandler(sys.stdout)
    handler.setFormatter(log_formatter)
    LOG.addHandler(handler)


LOG = None
# for interactive call: do not add multiple times the handler
if not LOG:
    LOG = logging.getLogger("template")
    configure_log()


def main(argv=None):
    "Program wrapper."
    if argv is None:
        argv = sys.argv[1:]
    parser = ArgumentParser()
    parser.add_argument(
        "-v",
        "--verbose",
        dest="verbose",
        action="store_true",
        default=False,
        help="run as verbose mode",
    )
    args = parser.parse_args(argv)
    if args.verbose:
        LOG.setLevel(logging.DEBUG)
    do_job()
    return 0


if __name__ == "__main__":
    import doctest

    doctest.testmod()
    sys.exit(main())


class memoized:
    """Decorator that caches a function's return value each time it is called.
    If called later with the same arguments, the cached value is returned, and
    not re-evaluated.
    """

    def __init__(self, func):
        self.func = func
        self.cache = {}

    def __call__(self, *args):
        try:
            return self.cache[args]
        except KeyError:
            value = self.func(*args)
            self.cache[args] = value
            return value
        except TypeError:
            # uncachable -- for instance, passing a list as an argument.
            # Better to not cache than to blow up entirely.
            return self.func(*args)

    def __repr__(self):
        """Return the function's docstring."""
        return self.func.__doc__

    def __get__(self, obj, objtype):
        """Support instance methods."""
        return functools.partial(self.__call__, obj)

Submission status: Accepted

Solution code:
n,m = map(int, input().split())
h = list(map(int, input().split()))

g = [1 for i in range(n)]
for i in range(m):
	a,b = map(int, input().split())
	if(h[a-1] <= h[b-1]):
		g[a-1] = 0
	if(h[a-1] >= h[b-1]):
		g[b-1] = 0
#	print(a,b,g[a-1],g[b-1])

ret = 0
for i in range(n):
	if(g[i] == 1):
		ret+=1
#print(g)
print(ret)

Submission status: Accepted

Solution code:
from collections import defaultdict

n, m = list(map(int, input().split(' ')))
hn = list(map(int, input().split(' ')))
abm = [None] * m

d = defaultdict(list)
for i in range(m):
    v = list(map(int, input().split(' ')))
    d[v[0]].append(v[1])
    d[v[1]].append(v[0])
    

count = 0

for i in range(1, n + 1):
    cand = d.get(i)
    if cand is None:
        count += 1
        continue
    ok = True
    for c in cand:
        if hn[i - 1] <= hn[c - 1]:
            ok = False
            break
    if ok:
        count += 1
print(count)

Submission status: Accepted

Solution code:
from sys import stdin
from collections import defaultdict
N,M = [int(x) for x in stdin.readline().rstrip().split()]
H = [int(x) for x in stdin.readline().rstrip().split()]
d = defaultdict(set)
for i in range(M):
    A,B = [int(x) for x in stdin.readline().rstrip().split()]
    d[A].add(B)
    d[B].add(A)
    
ans = 0
for h in range(1,N+1):
    f = True
    for i in d[h]:
        if H[i-1] >= H[h-1]:
            f = False
    if f:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
import sys
from math import factorial
from collections import Counter
from fractions import Fraction
import heapq, bisect, fractions
import math
import itertools
sys.setrecursionlimit(10 ** 5 + 10)
INF = 10**15 +5
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
MOD = 10**9 + 7

n, m = MAP()
H = LIST()
low = []
for i in range(m):
    a, b= MAP()
    if H[a-1] == H[b-1]:
        low.append(a-1)
        low.append(b-1)
    elif H[a-1] < H[b-1]:
        low.append(a-1)
    else:
        low.append(b-1)

print(n-len(set(low)))

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
H = list(map(int, input().split()))
m = [True] * N

for _ in range(M):
  A, B = map(int, input().split())
  
  if H[A - 1] > H[B - 1]:
    m[B - 1] = False
  elif H[B - 1] > H[A - 1]:
    m[A - 1] = False
  else:
    m[A - 1] = False
    m[B - 1] = False
  
ans = m.count(True)

print(ans)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
h=list(map(int,input().split()))
g=[1 for i in range(n)]
for i in range(m):
  a,b=map(int,input().split())
  a=a-1
  b=b-1
  if h[a]<=h[b]:
      g[a]=0
  if h[b]<=h[a]:
      g[b]=0
ans=g.count(1)
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter
N,M = map(int,input().split(" "))
Hs = [int(i) for i in input().split(" ")]
Ts = [1]*N

for _ in range(M):
    A,B = map(int,input().split(" "))
    if Hs[A-1]==Hs[B-1]:
        Ts[A-1]=0
        Ts[B-1]=0
    elif Hs[A-1]>Hs[B-1]:
        Ts[B-1]=0
    else:
        Ts[A-1]=0

C = Counter(Ts)
print(C[1])

Submission status: Accepted

Solution code:


import sys
import math
import itertools
import collections

def solve(N,M,H,A,B):
    total = 0
    dic = {key:[] for key in range(N)}
    for a,b in zip(A,B):
        dic[a-1].append(H[b - 1])
        dic[b-1].append(H[a - 1])
    for n,h in enumerate(H):
        target = dic[n]
        for t in target:
            if(h <= t):break
        else:
            total+= 1

    return total
def main():
    N,M = map(int,input().split())
    H = list(map(int,input().split()))
    A = []
    B = []
    for _ in range(M):
        a,b = map(int,input().split())
        A.append(a)
        B.append(b)

    # solve()
    print(solve(N,M,H,A,B))

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
h=list(map(int,input().split()))
good=[1 for i in range(n)]
for _ in range(m):
    a,b=map(int,input().split())
    a-=1
    b-=1
    if h[a]>h[b]:
        good[b]=0
    elif h[a]<h[b]:
        good[a]=0
    else:
        good[a]=good[b]=0
ans=0
for i in good:
    if i==1:
        ans+=1
print(ans)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
h = list(map(int, input().split()))
a = [[] for i in range(n)]
for i in range(m):
    s, t = map(int, input().split())
    a[s-1].append(t-1)
    a[t-1].append(s-1)
cnt = 0
for i in range(0, n):
    flag = True
    for j in range(len(a[i])):
        if h[i] <= h[a[i][j]]:
            flag = False
            break
    if flag:
        cnt += 1
print(cnt)

Submission status: Accepted

Solution code:

def resolve():
    import sys
    input = sys.stdin.readline
    n, m = list(map(int, input().split()))
    h = list(map(int, input().split()))
    good = [True for _ in range(n)]
    for i in range(m):
        a, b = list(map(int, input().split()))
        a = a - 1
        b = b - 1

        if h[a] <= h[b]:
            good[a] = False
        if h[a] >= h[b]:
            good[b] = False

    print(good.count(True))


# x = list(map(int, input().split()))

if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
n, m = list(map(int,input().split()))
h = list(map(int,input().split()))
a = []
b = []
for i in range(m):
  a0, b0 = list(map(int,input().split()))
  a.append(a0)
  b.append(b0)
  
count = [0] * n

for i in range(m):
  if h[a[i] - 1] <= h[b[i] - 1]:
    count[a[i] - 1] = 1
  if h[a[i] - 1] >= h[b[i] - 1]:
    count[b[i] - 1] = 1
      
print(count.count(0))

Submission status: Accepted

Solution code:
N,M = [int(i) for i in input().split(' ')]
H = [int(i) for i in input().split(' ')]
A = []
for i in range(M):
	x,y = [int(j) for j in input().split(' ')]
	if H[x-1] < H[y-1]:
		A.append(x)
	elif H[x-1] > H[y-1]:
		A.append(y)
	else:
		A.append(x)
		A.append(y)

print(N-len(set(A)))

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
H = tuple(map(int, input().split()))

tower = [True for i in range(n)]

for idx in range(m):
    a, b = map(int, input().split())
    if H[a - 1] > H[b - 1]:
        tower[b - 1] = False
    elif H[a - 1] == H[b - 1]:
        tower[b - 1] = False
        tower[a - 1] = False
    else:
        tower[a - 1] = False

ans = 0
for t in tower:
    if t:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
from math import ceil #切り上げ
import numpy as np
 
def inp(): return int(input()) #一個だけ読み取り
def inpm(): return map(int,input().split()) #mapオブジェクトで呼び出し
def inpl(): return list(map(int, input().split())) #数字リストをintで
def inpls(): return list(input().split()) #リストをstrで

N,M = inpl()
H = inpl()

all_list = []
for h in H:
  all_list.append([h])

for i in range(M):
  A, B = inpl()
  all_list[A-1].append(all_list[B-1][0])
  all_list[B-1].append(all_list[A-1][0])
  
count = 0

for ss in all_list:
  tmp = 0
  for i in range(1,len(ss)):
    if ss[i] >= ss[0]:
      tmp = 1
      break
    else:
      pass
  if tmp == 0:
    count = count+1
    

print(count)

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
H = list(map(int,input().split()))
T = [[] for i in range(N+1)]
for i in range(M):
    a,b = map(int,input().split())
    T[a].append(b)
    T[b].append(a)

ans = [1]*(N+1)
for i in range(1,N+1):
    h = H[i-1]
    for c in T[i]:
        if h<=H[c-1]:
            ans[i] = 0
            break
print(sum(ans)-1)

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
H = list(map(int,input().split()))
AB = [map(int, input().split()) for _ in range(M)]
A, B = [list(i) for i in zip(*AB)]
X = [1 for i in range(N)]
for i in range(0,M):
    if H[A[i]-1] < H[B[i]-1]:
        X[A[i]-1] = 0
    elif H[A[i]-1] > H[B[i]-1]:
        X[B[i]-1] = 0
    else:
        X[A[i]-1] = 0
        X[B[i]-1] = 0
ans = 0
for i in range(0,len(X)):
    ans = ans + X[i]
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
from heapq import heapify,heappop,heappush,heappushpop
from copy import copy,deepcopy
from itertools import product,permutations,combinations,combinations_with_replacement
from collections import defaultdict,Counter
from bisect import bisect_left,bisect_right
# from math import gcd,ceil,floor,factorial
# from fractions import gcd
from functools import reduce
from pprint import pprint

def myinput():
    return map(int,input().split())

def mylistinput(n):
    return [ list(myinput()) for _ in range(n) ]

def mycol(data,col):
    return [ row[col] for row in data ]

def mysort(data,col,reverse_flag):
    data.sort(key=lambda x:x[col],reverse=reverse_flag)
    return data

def mymax(data):
    M = -1*float("inf")
    for i in range(len(data)):
        m = max(data[i])
        M = max(M,m)
    return M

def mymin(data):
    m = float("inf")
    for i in range(len(data)):
        M = min(data[i])
        m = min(m,M)
    return m

def myoutput(ls,space=True):
    if space:
        if len(ls)==0:
            print(" ")
        elif type(ls[0])==str:
            print(" ".join(ls))
        elif type(ls[0])==int:
            print(" ".join(map(str,ls)))
        else:
            print("Output Error")
    else:
        if len(ls)==0:
            print("")
        elif type(ls[0])==str:
            print("".join(ls))
        elif type(ls[0])==int:
            print("".join(map(str,ls)))
        else:
            print("Output Error")

N,M = myinput()
H = list(myinput())
AB = mylistinput(M)

g = [ [] for _ in range(N) ]
for i in range(M):
    a = AB[i][0] - 1
    b = AB[i][1] - 1
    g[a].append(b)
    g[b].append(a)
# print(g)

count = 0
for i in range(N):
    ls = g[i]
    h = H[i]
    flag = True
    for j in range(len(ls)):
        if H[ls[j]]>=h:
            flag = False
    if flag:
        # print("i={}".format(i))
        count += 1
print(count)

Submission status: Accepted

Solution code:
n, m = map(int,input().split())
H  = list(map(int,input().split()))
A_B = [list(map(int,input().split())) for i in range(m)]
s = set()

for i in A_B:
    if H[i[0]-1] < H[i[1]-1]:
        s.add(i[0])
    elif H[i[0]-1] == H[i[1]-1]:
        s.add(i[0])
        s.add(i[1])
    else:
        s.add(i[1])

print(n-len(s))

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

import math

N, M = map(int, input().split())
Hs = list(map(int, input().split()))

s = set()

for i in range(0, M):
    A, B = map(int, input().split())
    if Hs[A - 1] <= Hs[B - 1]:
        s.add(A)
    if Hs[A - 1] >= Hs[B - 1]:
        s.add(B)

# print(s)
# print(len(s))
print(N - len(s))

Submission status: Accepted

Solution code:
n,m = map(int, input().split())
h_list = list(map(int,input().split()))
ans = [1]*n
for i in range(m):
    a,b = map(int, input().split())
    if h_list[a-1] == h_list[b-1]:
        ans[a-1] = 0
        ans[b-1] = 0
    else:
        if h_list[a-1] > h_list[b-1]:
            ans[b-1] = 0
        else:
            ans[a-1] = 0
print(sum(ans))

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
H = list(map(int,input().split()))
road = [[] for i in range(N+1)]
for i in range(M):
    A,B = map(int,input().split())
    road[A].append(H[B-1])
    road[B].append(H[A-1])
ans = 0
for i in range(N):
    if len(road[i+1]) > 0:
        rival = max(road[i+1])
        if H[i] > rival:
            ans += 1
    else:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
h=list(map(int,input().split()))
a=[]
for i in range(m):
    a.append(list(map(int,input().split())))

res=[1]*n
for i in range(m):
    if(h[a[i][0]-1]==h[a[i][1]-1]):
        res[a[i][0]-1]=0
        res[a[i][1]-1]=0
        
    elif(h[a[i][0]-1]<h[a[i][1]-1]):
        res[a[i][0]-1]=0
    else:
        res[a[i][1]-1]=0
ans=0
for i in range(n):
    if(res[i]==1):
        ans+=1
print(ans)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
H = list(map(int, input().split()))
query = [tuple(map(int, input().split())) for _ in range(m)]

table = [0 for _ in range(n)]

for a, b in query:
    if H[a-1] > H[b-1]:
        table[b-1] += 1
    elif H[a-1] < H[b-1]:
        table[a-1] += 1
    else:
        table[a-1] += 1
        table[b-1] += 1

ans = 0
for i in table:
    if i == 0:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
H = list(map(int,input().split())) #標高の高さ
best_list = [True]*N

A=0
B=0
for k in range(0,M):
    A,B=map(int,input().split())
    if(H[A-1]-H[B-1]<=0):
        best_list[A-1]=False
    if(H[B-1]-H[A-1]<=0):
        best_list[B-1]=False
print(best_list.count(True))

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
H = list(map(int, input().split()))

DP =[1]*N
for i in range(M):
  A, B = map(int, input().split())
  if H[A-1] > H[B-1]:
    if DP[A-1]!=-1:
	    DP[A-1] = 1
    DP[B-1] = -1
  elif H[B-1] > H[A-1]:
    if DP[B-1]!=-1:
	    DP[B-1] = 1
    DP[A-1] = -1
  else:
    DP[A-1] = -1
    DP[B-1] = -1
ans = DP.count(1)
print(ans)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
H = list(map(int, input().split()))
L = [1] * n
for _ in range(m):
    a, b = map(int, input().split())
    if H[a-1] < H[b-1]:
        L[a - 1] = 0
    elif H[a-1] > H[b-1]:
        L[b - 1] = 0
    else:
        L[a - 1] = 0
        L[b-1] = 0
print(sum(L))

Submission status: Accepted

Solution code:
import math
from collections import Counter
n,m=map(int,input().split())
e=[int(x) for x in input().split()]
di={}
for i in range(m):
	a,b=map(int,input().split())
	if a in di:
		di[a]+=[b]
	else: di[a]=[b]
	if b in di:
		di[b]+=[a]
	else: di[b]=[a]

c=0
for u,v in di.items():
	h=e[u-1]
	f=False
	for i in v:
		if h<=e[i-1]:
			f=True
			break
	if not f:
		c+=1

for i in range(1,len(e)+1):
	if i not in di:
		c+=1

print(c)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
l=[1]*n
h=list(map(int,input().split()))
for i in range(m):
    a,b=map(int,input().split())
    if h[a-1]>h[b-1]:
        l[b-1]=0
    elif h[a-1]<h[b-1]:
        l[a-1]=0
    else:
        l[a-1]=0
        l[b-1]=0
print(l.count(1))

Submission status: Accepted

Solution code:
n, m = list(map(int, input().split()))
h = list(map(int, input().split()))
#a = []
#b = []

result = [True] * n

for i in range(m):
    aa, bb = list(map(int, input().split()))
    if h[aa-1] == h[bb-1]:
        result[bb-1] = False
        result[aa-1] = False
    elif h[aa-1] > h[bb-1]:
        result[bb-1] = False
    else:
        result[aa-1] = False

#print(result)
s = 0
for i in range(n):
    if result[i]:
        s += 1
print(s)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
H = list(map(int, input().split()))
paths = [list(map(int, input().split())) for _ in range(M)]

d = {i + 1: [] for i in range(N)}
for p in paths:
    d[p[0]].append(H[p[1] - 1])
    d[p[1]].append(H[p[0] - 1])

ans = 0
for i in range(N):
    # i = 0
    hs = d[i + 1]
    if len(hs) == 0:
        ans += 1
        continue

    my_h = H[i]
    flag = True
    for h in hs:
        if h >= my_h:
            flag = False

    if flag:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip()
n, m = map(int, input().split())

h = list(map(int, input().split()))
route = [[] for _ in range(n)]
for i in range(m):
    a, b = map(int, input().split())
    route[a - 1].append(b - 1)
    route[b - 1].append(a - 1)
ans = 0
now = 0
for r in route:
    if len(r) == 0:
        ans += 1
    else:
        height = h[now]
        safe = True
        for rr in r:
            if height <= h[rr]:
                safe = False
                break
        if safe:
            ans += 1
    now += 1
print(ans)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
h = [int(_) for _ in input().split()]
a = [0] * m
b = [0] * m
for i in range(m):
    aa, bb = map(int, input().split())
    a[i], b[i] = aa, bb

ans = [1] * n
for i in range(m):
    if h[a[i]-1] == h[b[i]-1]:
        ans[a[i]-1], ans[b[i]-1] = 0, 0
    elif h[a[i]-1] > h[b[i]-1]:
        ans[b[i]-1] = 0
    else:
        ans[a[i]-1] = 0

print(sum(ans))

Submission status: Accepted

Solution code:

def resolve():
    N, M = map(int, input().split())
    H = list(map(int, input().split()))

    BL = [True]*(N)
    for _ in range(M):
        a, b = map(lambda x:int(x)-1, input().split())
        if BL[a] == True:
            if H[a] <= H[b]:
                BL[a] = False
        if BL[b] == True:
            if H[b] <= H[a]:
                BL[b] = False
    print(sum(BL))

if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
import numpy as np
N, M = map(int,input().split())
H = list(map(int,input().split()))

goodpoint = [1]*N #1 is good point

for i in range (M):
    A, B = map(int,input().split())
    if H[A-1] <=H[B-1]:
        goodpoint[A-1] = 0
    if H[B-1] <=H[A-1]:
        goodpoint[B-1] = 0
print(sum((np.array(goodpoint)==1)*1))###aaaaaaaaああああああみすったあ

Submission status: Accepted

Solution code:
def resolve():
    n,m=map(int, input().split())
    h = list(map(int, input().split()))
    ans = [1 for i in range(n)]
    high = [0 for i in h]

    for i in range(m):
        a,b = map(int, input().split())
        a -= 1
        b -= 1
        if h[a] == h[b]:
            ans[a] = 0
            ans[b] = 0
        elif h[a] < h[b]:
            ans[a] = 0
        else:
            ans[b] = 0
    print(sum(ans))

if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
N, M = [int(x) for x in input().split()]
H = [int(x) for x in input().split()]
to = [set() for _ in range(N)]
for _ in range(M):
    a, b = [int(x)-1 for x in input().split()]
    to[a].add(b)
    to[b].add(a)
ans = 0
for i, h in enumerate(H):
    tmp = 1
    for v in to[i]:
        tmp *= (h > H[v])
    ans += tmp
print(ans)

Submission status: Accepted

Solution code:
import sys
from io import StringIO
import unittest

def resolve():
    n, m = map(int, input().split())

    h = list(map(int, input().split()))

    road = [[] for _ in range(n)]

    for _ in range(m):
        a, b = map(int, input().split())
        road[a - 1].append(b)
        road[b - 1].append(a)

    ans = 0

    for i, r in enumerate(road):
        if r == []:
            ans += 1
            continue
        elif h[i] > max([h[p - 1] for p in r]):
            ans += 1

    print(ans)


class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)
    def test_入力例_1(self):
        input = """4 3
1 2 3 4
1 3
2 3
2 4"""
        output = """2"""
        self.assertIO(input, output)
    def test_入力例_2(self):
        input = """6 5
8 6 9 1 2 1
1 3
4 2
4 3
4 6
4 6"""
        output = """3"""
        self.assertIO(input, output)

if __name__ == "__main__":
    # unittest.main()
    resolve()

Submission status: Accepted

Solution code:
import sys
import itertools
sys.setrecursionlimit(1000000000)
from heapq import heapify,heappop,heappush,heappushpop
import math
import collections

n,m = map(int,input().split())
H = list(map(int,input().split()))
edge =[[] for i in range(n)]
for i in range(m):
    a,b = map(int,input().split())
    edge[a-1].append(b-1)
    edge[b-1].append(a-1)
cnt = 0

for i in range(n):
    flag = False
    for j in range(len(edge[i])):
        if H[i]<=H[edge[i][j]]:
            flag = True
            break
    if flag == False:
        cnt+=1
print(cnt)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys

sys.setrecursionlimit(10 ** 8)
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N, M = map(int, readline().split())
H = list(map(int, readline().split()))
good = [True] * N
for i in range(M):
    a, b = [int(x) - 1 for x in readline().split()]
    if H[a] <= H[b]:
        good[a] = False
    if H[a] >= H[b]:
        good[b] = False


def solve():
    return sum(good)


if __name__ == "__main__":
    print(solve())