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:
N,M = map(int, input().split())
H = [0] + list(map(int, input().split()))
P = [0] + [1]*N
for i in range(M):
  A,B = map(int, input().split())
  if H[A]<=H[B]:
    P[A]=0
  if H[A]>=H[B]:
    P[B]=0
print(sum(P))

Submission status: Accepted

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

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

ans = [1] * N

for i in range(M):
    A, B = list(map(int, input().split()))
    if H[A - 1] > H[B - 1]:
        ans[B - 1] = 0
    elif H[A - 1] < H[B - 1]:
        ans[A - 1] = 0
    else:
        ans[A - 1] = 0
        ans[B - 1] = 0

print(sum(ans))

Submission status: Accepted

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

isgood = {}
for ni in range(1, n + 1):
    isgood[ni] = True

for mi in range(m):
    if h[a[mi] - 1] <= h[b[mi] - 1]:
        isgood[a[mi]] = False
    if h[b[mi] - 1] <= h[a[mi] - 1]:
        isgood[b[mi]] = False

ans = 0
for tow in isgood.keys():
    if isgood[tow]:
        ans += 1

print(ans)

Submission status: Accepted

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

    way = [ [] for _ in range(N+1)]

    for i in range(M):
        a = A[i][0]
        b = A[i][1]
        way[a].append(b)
        way[b].append(a)

    #print(way)
    ans = 0
    for j in range(N):
        cnt = 0
        if way[j+1] == []:
            ans += 1
            continue
        for k in way[j+1]:
            if H[j] <= H[k-1]:
                break
            cnt += 1
            if cnt == len(way[j+1]):
                ans += 1

    return ans

print(main())

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
def Ii():return int(sys.stdin.buffer.read())
def Mi():return map(int,sys.stdin.buffer.readline().split())
def Li():return list(map(int,sys.stdin.buffer.readline().split()))

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

Submission status: Accepted

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

list = [1]*n
for i in range(m):
    a = rlist[i][0] - 1
    b = rlist[i][1] - 1
    if hlist[a] <= hlist[b]:
        list[a] = 0
    if hlist[a] >= hlist[b]:
        list[b] = 0

print(list.count(1))

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
H = list(map(int, input().split()))
l = [1] * N
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
    elif H[A - 1] == H[B - 1]:
        l[A - 1], l[B - 1] = 0, 0
print(l.count(1))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from collections import defaultdict, deque

(n, m), h, g = map(int, input().split()), list(map(int, input().split())), defaultdict(list)
for i in range(m): a, b = map(int, input().split()); g[a-1].append(b-1); g[b-1].append(a-1)
good = [True for i in range(n)]
for i in range(n):
    for j in g[i]:
        if h[j] >= h[i]: good[i] = False
print(good.count(True))

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
H = list(map(int, input().split()))
l = [1] * N
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
    elif H[A - 1] == H[B - 1]:
        l[A - 1], l[B - 1] = 0, 0
print(l.count(1))

Submission status: Accepted

Solution code:
N = list(map(int, input().split()))
H = list(map(int, input().split()))
B = [list(map(int, input().split())) for i in range(N[1])]

# N = [6, 5]
# H = [8, 6, 9, 1, 2, 1]
# B = [[1, 3], [4, 2], [4, 3], [4, 6], [4, 6]]

# N = [4, 3]
# H = [1, 2, 3, 4]
# B = [[1, 3],[2, 3],[2, 4]]

counter = [1 for i in range(N[0])]

for b in B:
    if H[b[1]-1] > H[b[0]-1]:
        counter[b[0]-1] = 0
    elif H[b[0]-1] > H[b[1]-1]:
        counter[b[1]-1] = 0
    elif H[b[0]-1] == H[b[1]-1]:
        counter[b[0]-1] = 0
        counter[b[1]-1] = 0

print(sum(counter))

Submission status: Accepted

Solution code:
from collections import defaultdict
n,m = map(int,input().split())
h_list = list(map(int,input().split()))
connect_dic = defaultdict(set)

for i in range(m):
    a,b = map(int,input().split())
    connect_dic[a].add(b)
    connect_dic[b].add(a)

count = 0
for k,v in connect_dic.items():
    if h_list[k-1]>max([h_list[num-1] for num in v]):
        count += 1

print(count + n - len(connect_dic))

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
H = list(map(int,input().split()))
a = [list(map(int,input().split())) for _ in range(M)]
A = [set() for __ in range(N)]
#print(A)
for d in a:
    A[d[0]-1].add(d[1]-1)
    A[d[1]-1].add(d[0]-1)
#print(A)
count = 0
for i,h in enumerate(H):
    if len(A[i]) == 0:
        count += 1
        continue
    is_high = 1
    for a in A[i]:
        if H[a] >= h:
            is_high = 0
            break
    count += is_high
print(count)

Submission status: Accepted

Solution code:
from collections import defaultdict
n,m = map(int,input().split())
h_list = list(map(int,input().split()))
connect_dic = defaultdict(set)

for i in range(m):
    a,b = map(int,input().split())
    connect_dic[a].add(b)
    connect_dic[b].add(a)

count = 0
for k,v in connect_dic.items():
    if h_list[k-1]>max([h_list[num-1] for num in v]):
        count += 1

print(count + n - len(connect_dic))

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
H = list(map(int, input().split()))
G = [[] for _ in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    G[a].append(b)
    G[b].append(a)
ans = 0
for i in range(N):
    for j in G[i]:
        if H[i] <= H[j]:
            break
    else:
        ans += 1
print(ans)

Submission status: Accepted

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

good = [1]*n

for comb in ab:
    a = comb[0]-1
    b = comb[1]-1
    if h[a] <= h[b]:
        good[a] = 0
    if h[a] >= h[b]:
        good[b] = 0

ans = sum(good)
print(ans)

Submission status: Accepted

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

print(g.count(1))

Submission status: Accepted

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

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

# NG = 0, OK = 1
count_list = [1] * N
for _ in range(M):
    A, B = map(int, input().split())
    A -= 1
    B -= 1
    if H[A] >= H[B]:
        count_list[B] = 0
    if H[A] <= H[B]:
        count_list[A] = 0
print(sum(count_list))

Submission status: Accepted

Solution code:

N, M = map(int, input().split())
Hs = list(map(int, input().split()))
ans = [1 for _ in range(N)]
for _ in range(M):
    A, B = map(int, input().split())
    if Hs[A-1] > Hs[B-1]:
        ans[B-1] = 0
    elif Hs[A-1] == Hs[B-1]:
        ans[A-1] = 0
        ans[B-1] = 0
    else:
        ans[A-1] = 0
print(sum(ans))

Submission status: Accepted

Solution code:
# abc166_c.py
'''
道でつながっている展望台のうち一番高いものを探す問題。
高さが同じ場合を考える必要があるかもしれないが、結局のところ「連結されたグラフ内で最大の値を探し出す」問題。
ということはいくつ連結グラフがあるかだけでいい…?ここがコーナーケースかな?
'''
N, M = map(int,input().split())
H = list(map(int,input().split()))
glaph = [[] for i in range(N)]
for i in range(M):
    a,b = map(int,input().split())
    glaph[a-1].append(b-1) 
    glaph[b-1].append(a-1)
highest = [False for i in range(N)]
for i in range(N):
    now = H[i]
    is_highest = True
    for neiber in glaph[i]:
        # print("now is",i,"neiber is",neiber,"Hi,Hneiber",H[i] , H[neiber])
        if highest[neiber] or H[i] <= H[neiber]:
            is_highest = False
            continue
    if is_highest:
        highest[i] = True
print(highest.count(True))

Submission status: Accepted

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

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

print(sum(win))

Submission status: Accepted

Solution code:
N,M = (int(a) for a in input().split())
H = list(map(int,input().split()))
ans = [0]*N
for i in range(M) :
    A,B = (int(a) for a in input().split())
    if H[A-1] == H[B-1] :
        ans[A-1] = 1
        ans[B-1] = 1
    elif H[A-1] < H[B-1] :
        ans[A-1] = 1
    else :
        ans[B-1] = 1
print(ans.count(0))

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
aa=list(map(int,input().split()))
tonari=[[] for i in range(n)]
for x in range(m):
  a,b=map(int,input().split())
  tonari[a-1].append(b-1)
  tonari[b-1].append(a-1)
  
auto=[0]*n



for y in range(n):
  if auto[y]>0:
    continue
  elif len(tonari[y])==0:
    continue
  for z in range(len(tonari[y])):
    v=tonari[y][z]
    if aa[y]>aa[v]:
      auto[v]+=1
    elif aa[y] == aa[v]:
      auto[y]+=1
      break
    elif aa[y] < aa[v]:
      auto[y]+=1
      break
  

print(auto.count(0))

Submission status: Accepted

Solution code:
def f(heights,roads):
	r = [True] * len(heights)
	for u,v in roads:
		if heights[u - 1] <= heights[v - 1]: r[u - 1] = False
		if heights[u - 1] >= heights[v - 1]: r[v - 1] = False
	return len([v for v in r if v])

n,m = map(int, raw_input().split(' '))
print f(map(int,raw_input().split(' ')), [map(int, raw_input().split(' ')) for _ in range(m)] )

Submission status: Accepted

Solution code:
def f(heights,roads):
	count, r =0, [True] * len(heights)
	for u,v in roads:
		if heights[u-1] <= heights[v-1]: r[u-1] = False
		if heights[u-1] >= heights[v-1]:r[v-1] = False
	for b in r:
		count += 1 if b else 0
	return count

n,m = map(int, raw_input().split(' '))
print f(map(int,raw_input().split(' ')), [map(int, raw_input().split(' ')) for _ in range(m)] )

Submission status: Accepted

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

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

ans = [True]*n

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

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

print(sum(ans))

Submission status: Accepted

Solution code:
import collections
def f(heights,roads):
	adj = collections.defaultdict(list)
	count = 0
	for u,v in roads:
		adj[u].append(v)
		adj[v].append(u)
	for i,h in enumerate(heights):
		u = i + 1
		if h > max([heights[v-1] for v in adj[u]] or [-1]): count +=1
	return count

n,m = map(int, raw_input().split(' '))
print f(map(int,raw_input().split(' ')), [map(int, raw_input().split(' ')) for _ in range(m)] )

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
H_list = list(map(int, input().split()))
conected_list = []

for n in range(N):
    conected_list.append([])

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

count = 0

for n in range(N):
    n_h = H_list[n]
    flg = True
    for i in conected_list[n]:
        if(n_h <= H_list[i]):
            flg = False
    
    if(flg):
        count += 1
        
print(count)

Submission status: Accepted

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

ans = [1] * n

for i in range(m):
    if h[pairs[i][0] - 1] < h[pairs[i][1] - 1]:
        ans[pairs[i][0] - 1] = 0
    elif h[pairs[i][0] - 1] == h[pairs[i][1] - 1]:
        ans[pairs[i][0] - 1] = 0
        ans[pairs[i][1] - 1] = 0 
    else:
        ans[pairs[i][1] - 1] = 0      

print(sum(ans))

Submission status: Accepted

Solution code:
N, M = list(map(int, input().split()))
H = list(map(int, input().split()))
H = [0] + H
judge = [True] * (N + 1)
AB = []
for _ in range(M):
    ab = list(map(int, input().split()))
    AB.append(ab)

for i in range(M):
    if H[AB[i][0]] > H[AB[i][1]]:
        judge[AB[i][1]] = False
    elif H[AB[i][0]] < H[AB[i][1]]:
        judge[AB[i][0]] = False
    elif H[AB[i][0]] == H[AB[i][1]]:
        judge[AB[i][0]] = False
        judge[AB[i][1]] = False
print(judge.count(True) - 1)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
A, B = map(int, input().split())
C = list(map(int, input().split()))

max_height = [0] * A

for i in range(B):
    a, b = map(int, input().split())
    max_height[a - 1] = max(max_height[a - 1], C[b - 1])
    max_height[b - 1] = max(max_height[b - 1], C[a - 1])

print((sum(C[i] > max_height[i] for i in range(A))))

Submission status: Accepted

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

max_height = [0]*N
for i in range(M):
    a,b = map(int,input().split())
    max_height[a-1]=max(max_height[a-1],H[b-1])
    max_height[b-1]=max(max_height[b-1],H[a-1])


print((sum(H[i] > max_height[i] for i in range(N))))

Submission status: Accepted

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

ans = 0
for i, l in enumerate(ls):
    if len(l) == 0:
        ans += 1
    else:
        ok = True
        for j in l:
            if h[i] <= h[j]:
                ok = False
                break
        if ok:
            ans += 1
print(ans)

Submission status: Accepted

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

x=[0]*n
for i in range(k):
    a,b = map(int, input().split())
    if h[a-1]>=h[b-1]:
      x[b-1] +=1
    if h[b-1]>=h[a-1]:
      x[a-1] +=1
print(x.count(0))

Submission status: Accepted

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

dp = [0]*n

for i in range(m):
    a,b = map(int, input().split())
    if h[a-1] >= h[b-1]:
        dp[b-1] = dp[b-1] + 1
    if h[b-1] >= h[a-1]:
        dp[a-1] = dp[a-1] + 1

print(dp.count(0))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
height = list(map(int, input().split()))
judge = N*[1]
for i in range(M):
	A, B = map(int, input().split())
	if(height[A-1]>=height[B-1]):
		judge[B-1] = 0
	if(height[A-1]<=height[B-1]):
		judge[A-1] = 0

ans = 0
for i in range(N):
	if judge[i]==1:
		ans += 1
print(ans)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
H = list(map(int, input().split()))
roots = [list(map(int, input().split())) for _ in range(M)]
observatories = [1] * N
for root in roots:
    a = root[0] - 1
    b = root[1] - 1
    if H[a] < H[b]:
        observatories[a] = 0
    elif H[a] > H[b]:
        observatories[b] = 0
    else:
        observatories[a], observatories[b] = 0, 0
print(observatories.count(1))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 9)
# input = sys.stdin.readline    ####
def int1(x): return int(x) - 1
def II(): return int(input())
def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())
def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def MS(): return input().split()
def LS(): return list(input())
def LLS(rows_number): return [LS() for _ in range(rows_number)]
def printlist(lst, k=' '): print(k.join(list(map(str, lst))))
INF = float('inf')
# from math import ceil, floor, log2
# from collections import deque
# from itertools import combinations as comb, combinations_with_replacement as comb_w, accumulate, product, permutations
# from heapq import heapify, heappop, heappush
# import numpy as np    # cumsum
# from bisect import bisect_left, bisect_right

def solve():
    N, M = MI()
    H = LI()
    E = [[] for _ in range(N)]
    for i in range(M):
        a, b = MI1()
        E[a].append(b)
        E[b].append(a)

    used = [-1] * N
    for v in range(N):
        if used[v] == 0: continue
        h = H[v]
        for nv in E[v]:
            nh = H[nv]
            if h > nh:
                used[nv] = 0
            elif h < nh:
                used[v] = 0
                break
            else:
                used[v] = 0
                used[nv] = 0
                break
        else:
            used[v] = 1
    print(sum(used))

if __name__ == '__main__':
    solve()

Submission status: Accepted

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

Submission status: Accepted

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

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

dic = [{0} for i in range(n)]
for i in range(m):
    a,b = list(map(int,input().split()))
    dic[a-1].add(h[b-1])
    dic[b-1].add(h[a-1])

answer = 0
for i in range(n):
    if h[i] > max(dic[i]):
        answer += 1

print(answer)

Submission status: Accepted

Solution code:
import sys
import itertools


def peeks(f):
    readline = f.readline
    n, m = map(int, readline().split())
    h = tuple(itertools.chain(
        [0],
        map(int, readline().split())))
    observatories = tuple(tuple(map(int, line.split())) for line in f)
    # print(n, m)
    # print(f'{h=}')
    # print(f'{observatories=}')

    L = [0] * (n + 1)
    for a, b in observatories:
        L[a] = max(L[a], h[b])
        L[b] = max(L[b], h[a])

    # print(f'{L=}')
    ans = sum(1 for elevation, other in zip(h[1:], L[1:]) if elevation > other)

    return ans


def main():
    ans = peeks(sys.stdin.buffer)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
import itertools

def peeks(f):
    readline = f.readline
    n, m = map(int, readline().split())
    h = tuple(itertools.chain(
        [0],
        map(int, readline().split())))
    observatories = tuple(tuple(map(int, line.split())) for line in f)
    # print(n, m)
    # print(f'{h=}')
    # print(f'{observatories=}')

    L = [0] * (n + 1)
    for a, b in observatories:
        L[a] = max(L[a], h[b])
        L[b] = max(L[b], h[a])

    # print(f'{L=}')
    ans = sum(1 for index, elevation in enumerate(L[1:], 1) if h[index] > elevation)

    return ans


def main():
    ans = peeks(sys.stdin.buffer)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#166
#Peaks

N,M=map(int,input().split())
H=list(map(int,input().split()))
L=[1]*N
R=[]
for i in range(M):
    A,B=map(int,input().split())
    R.append([A,B])

for l in R:
    a=l[0]-1
    b=l[1]-1
    if H[a]<H[b]:
        L[a]=0
    elif H[a]>H[b]:
        L[b]=0
    else:L[a]=L[b]=0
print(L.count(1))

Submission status: Accepted

Solution code:
import numpy as np

n,m = map(int, input().split())
h_list = list(map(int, input().split()))

map_ = {str(i):[] for i in range(n)}

for _ in range(m):
  a, b = map(int, input().split())
  map_[str(a-1)].append(b-1)
  map_[str(b-1)].append(a-1)
  
cnt=0
for i in range(n):
  tmp = [h_list[i]] + [h_list[j] for j in map_[str(i)]]
  hiest = max(tmp)
  if tmp.count(hiest)==1:
    if tmp.index(max(tmp))==0:
      cnt+=1
print(cnt)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-
#
# FileName: 	C_fix
# CreatedDate:  2020-06-27 13:14:18 +0900
# LastModified: 2020-06-27 13:50:05 +0900
#


def main():
    n, m = map(int, input().split())
    h = list(map(int, input().split()))
    ma = [0]*n
    for _ in range(m):
        a, b = map(int, input().split())
        ma[a-1] = max(ma[a-1], h[b-1])
        ma[b-1] = max(ma[b-1], h[a-1])
#        print(ma)
    cnt = 0
    for i in range(n):
        if ma[i] < h[i]:
            cnt += 1
    print(cnt)




if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict as dd
from collections import deque
import bisect
import heapq

def ri():
    return int(input())

def rl():
    return list(map(int, input().split()))


def solve():
    n, m = rl()
    roads = dd(set)
    heights = rl()
    for i in range(m):
        u, v = rl()
        roads[u].add(v)
        roads[v].add(u)

    good = 0
    for i in range(1, n + 1):
        for nbr in roads[i]:
            if heights[nbr - 1] >= heights[i - 1]:
                break
        else:
            good += 1

    print (good)






mode = 's'

if mode == 'T':
    t = ri()
    for i in range(t):
        solve()
else:
    solve()

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
l = [*map(int, input().split())]
adj = [[] for _ in range(n)]
for _ in range(m):
    a, b = map(int, input().split())
    adj[a - 1].append(b - 1)
    adj[b - 1].append(a - 1)
cnt = 0
for i in range(n):
    cnt += all(l[i] > l[j] for j in adj[i])
print(cnt)

Submission status: Accepted

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

A_B = [[] for _ in range(N)]
A_B.insert(0, 0)
H.insert(0, 0)

for c in range(M):
    A, B = map(int, input().split())
    A_B[A].append(B)
    A_B[B].append(A)

ans = 0

for c in range(1, N + 1):
    for co in range(len(A_B[c])):
        if H[c] <= H[A_B[c][co]]:
            break
    else:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
n, m=map(int, input().split())
h=list(map(int,input().split()))
l = [[] for _ in range(n)]
#print(l)
#print(h)
for i in range(m):
  a, b=map(int, input().split())
  l[a-1].append(b)
  l[b-1].append(a)
ans=0
for x in range(n):
  for y in range(len(l[x])):
    if h[x]<=h[l[x][y]-1]:
      break
  else:
    ans+=1
    continue
print(ans)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
h = list(map(int, input().split()))
lst = [0] * n

for i in range(m):
  a, b = map(int, input().split())
  
  lst[a - 1] = max(lst[a - 1], h[b - 1])
  lst[b - 1] = max(lst[b - 1], h[a - 1])
  
ans = 0

for i in range(n):
  if lst[i] < h[i]:
    ans += 1

print(ans)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
h=list(map(int,input().split()))
ab=[[] for nn in range(n)]
for mm in range(m):
  a,b=map(int,input().split())
  ab[a-1].append(b-1)
  ab[b-1].append(a-1)
cnt=0
for i in range(n):
  hi=0
  for ll in ab[i]:
    hi=max(hi,h[ll])
  if hi<h[i]:
    cnt+=1
print(cnt)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
H = [int(i) for i in input().split()]
adj = [[] for i in range(N)]
for i in range(M):
    a, b = map(int, input().split())
    adj[a-1].append(b-1)
    adj[b-1].append(a-1)
ans = 0
for i in range(N):
    if all(H[i] > H[neighbor] for neighbor in adj[i]):
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
def main():
    n, m = map(int, input().split())
    h = [0]+list(map(int, input().split()))
    to = [0]*(n+1)
    for _ in range(m):
        a, b = map(int, input().split())
        to[a] = max(to[a], h[b])
        to[b] = max(to[b], h[a])
    print(len([1 for hi, t in zip(h[1:], to[1:]) if hi > t]))

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
peaks=list(map(int,input().split()))
goodpeaks=[1]*N
for i in range(M):
    a,b=map(int,input().split())
    if peaks[a-1]<peaks[b-1]:
        goodpeaks[a-1]=0
    elif peaks[a-1]>peaks[b-1]:
        goodpeaks[b-1]=0
    elif peaks[a-1]==peaks[b-1]:
        goodpeaks[a-1]=0
        goodpeaks[b-1]=0
#    print(goodpeaks)
ans=0
for h in goodpeaks:
    if h != 0:
        ans+=1

print(ans)

Submission status: Accepted

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

for i in range(m):
  path.append(list(map(int, input().split())))
  
root = [[0] for i in range(n+1)]

for i in range(m):
  root[path[i][0]].append(path[i][1])
  root[path[i][1]].append(path[i][0])

count = 0

for i in range(1, n+1):
  flag = 0
  for j in range(1, len(root[i])):
    if h[i-1] <= h[root[i][j]-1]:
      flag = 1
      break
  if flag == 0:
    count += 1
  
print(count)

Submission status: Accepted

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

towers = [1] * n

for a, b in ab:
    a -= 1
    b -= 1
    a_hi = h[a]
    b_hi = h[b]
    if a_hi == b_hi:
        towers[a] = 0
        towers[b] = 0
    elif a_hi > b_hi:
        towers[b] = 0
    else:
        towers[a] = 0

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

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()))

seen = set()
checked = set()
for i in range(M):
    a, b = map(int, input().split())
    if H[a-1] < H[b-1]:
        checked.add(a)
    elif H[a-1] > H[b-1]:
        checked.add(b)   
    else:
        checked.add(a)
        checked.add(b)    
    seen.add((a,b))
print(N-len(checked))

Submission status: Accepted

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

G=[0]*N
for i in range(M):
    a,b = map(int,input().split())
    a = a-1
    b = b-1
    if H[a] > H[b]:
        G[b] = 1
    elif H[a] < H[b]:
        G[a] = 1
    else:
        G[a] = 1
        G[b] = 1

cnt = 0
for i in range(N):
    if G[i] == 0:
        cnt += 1

print(cnt)

Submission status: Accepted

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

ans = 0
for i in range(n):
    flg = True
    for child in graph[i]:
        if h[i] <= h[child]:
            flg = False
            break
    ans += flg
print(ans)

Submission status: Accepted

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

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

skip = [0 for i in range(n)]

# print(li)
ans = []
for i in range(n):
    flg = 0
    hi = h[i]
    dd = li[i]
    if len(dd) == 0:
        ans.append(i)
        continue
    if skip[i] == -1:
        continue
    for d in dd:
        if hi <= h[d]:
            flg = 1
            break
        else:
            skip[d] = -1
    if flg == 0:
        ans.append(i)
print(len(ans))
# print(ans)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
h=list(map(int,input().split()))
ans=[True for _ in range(n)]
for _ in range(m):
    a,b=map(int,input().split())
    wa,wb=h[a-1],h[b-1]
    if wa>wb:ans[b-1]=False
    elif wa<wb:ans[a-1]=False
    else : ans[a-1]=False;ans[b-1]=False
print(ans.count(True))

Submission status: Accepted

Solution code:
def dfs(v,start):
    check=a[start-1]
    for i in v[start]:
        if(a[i-1]>=check):
            return 0
    return 1
        





n,m=map(int,input().split())
a=list(map(int,input().split()))
route=[[] for i in range(n+1)]
for i in range(m):
    x,y=map(int,input().split())
    route[x].append(y)
    route[y].append(x)
ans=0
visited=[0 for i in range(n+1)]
for i in range(1,n+1):
        ans+=dfs(route,i)
        
print(ans)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
a=list(map(int,input().split()))
c=0
deg=[[] for i in range(n)]
for i in range(m):
  u,v=map(int,input().split())
  deg[u-1].append(v-1)
  deg[v-1].append(u-1)
for i in range(n):
  ff=0
  for j in deg[i]:
    if(a[i]>a[j]):
      continue
    ff=1
  if(ff==0):
    c+=1
print(c)