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()))
Ans = [True] * (N+1)
for _ in range(M):
    a, b = map(int, input().split())
    Ha, Hb = H[a], H[b]
    if Ha <= Hb:
        Ans[a] = False
    if Ha >= Hb:
        Ans[b] = False
print(sum(Ans)-1)

Submission status: Accepted

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

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

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

ans = 0
for j in range(n):
    if not e[j]:
        ans += 1
        continue
    hs = [h[k] for k in e[j]]
    if h[j] > max(hs):
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
def solve():
    N, M = list(map(int, input().split()))
    H = list(map(int, input().split()))
    R = []
    for _ in range(M):
        R.append(list(map(int, input().split())))
    Check_array = [1 for _ in range(N)]
    for r in R:
        if(H[r[0]-1] < H[r[1]-1]):
            Check_array[r[0] - 1] = 0
        elif (H[r[0]-1] > H[r[1]-1]):
            Check_array[r[1] - 1] = 0
        else:
            Check_array[r[0] - 1] = 0
            Check_array[r[1] - 1] = 0
    print(sum(Check_array))


if __name__ == "__main__":
    solve()

Submission status: Accepted

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

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

print(t.count(n+1))

Submission status: Accepted

Solution code:
from collections import defaultdict
N, M = map(int, input().split())
heights = list(map(int, input().split()))
d = defaultdict(list)
for i in range(M):
    A, B = map(int, input().split())
    d[A].append(B)
    d[B].append(A)
ans_cnt = 0
for i in range(1, N + 1):
    if d[i] == []:
        ans_cnt += 1
    else:
        my_height = heights[i - 1]
        flag = True
        for j in d[i]:
            if heights[j - 1] >= my_height:
                flag = False
                break
        if flag:
            ans_cnt += 1
print(ans_cnt)

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
from collections import defaultdict

def main():
    n, m = map(int, input().split())
    h_list = list(map(int, input().split()))
    d = defaultdict(list)
    for i in range(m):
        a, b = map(int, input().split())
        d[a].append(h_list[b-1])
        d[b].append(h_list[a-1])
    
    count = 0
    for i, h in enumerate(h_list):
        if len(d[i+1]) == 0:
            count += 1
            continue
        max_h = max(d[i+1])
        if max_h < h:
            count += 1
    
    print(count)
    
main()

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
H = list(map(int, input().split()))
Flags = [1]*N
cnt = N
for _ in range(M):
    A, B = map(int, input().split())
    if H[A-1] <= H[B-1] and Flags[A-1]:
        cnt -= 1; Flags[A-1] = 0
    if H[A-1] >= H[B-1] and Flags[B-1]:
        cnt -= 1; Flags[B-1] = 0

print(cnt)

Submission status: Accepted

Solution code:
def solve():
    N,M = [int(i) for i in input().split()]
    H = [int(i) for i in input().split()]
    ans = set([i for i in range(1, N+1)])
    for i in range(M):
        A,B = [int(i) for i in input().split()]
        if H[A-1] < H[B-1]:
            if A in ans:
                ans.remove(A)
        elif H[B-1] < H[A-1]:
            if B in ans:
                ans.remove(B)
        else:
            if A in ans:
                ans.remove(A)
            if B in ans:
                ans.remove(B)
    print(len(ans))

if __name__ == "__main__":
    solve()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
H_list = list(map(int,input().split()))
A_list = [0] * M
B_list = [0] * M
C_list = [0] * N
for i in range(M):
    A_list[i],B_list[i] = map(int,input().split())
for a,b in zip(A_list,B_list):
    if H_list[a-1] < H_list[b-1]:
        C_list[a-1] = -1
    elif H_list[a-1] > H_list[b-1]:
        C_list[b-1] = -1
    elif H_list[a-1] == H_list[b-1]:
        C_list[a-1] = C_list[b-1] = -1
print(C_list.count(0))

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
H=list(map(int,input().split()))
G={i+1 for i in range(N)}
for _ in range(M):
  a,b=map(int,input().split())
  if H[a-1]>H[b-1]:
    G-={b}
  elif H[b-1]>H[a-1]:
    G-={a}
  else:
    G-={a,b}
print(len(G))

Submission status: Accepted

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

Submission status: Accepted

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

dest = [[] for i in range(N)]
for i in range(M):
  tmp = input().split(" ")
  dest[int(tmp[0]) - 1].append(int(tmp[1]) - 1)
  dest[int(tmp[1]) - 1].append(int(tmp[0]) - 1)

good = 0
for i in range(len(dest)):
  d = dest[i]
  if len(list(filter(lambda j: H[i] - H[j] <= 0, d))) == 0:
    good += 1

print(good)

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
H=list(map(int,input().split()))
graph=[[] for _ in range(N)]
for i in range(M):
	A,B=map(int,input().split())
	graph[A-1].append(B)
	graph[B-1].append(A)
answer=0
for i in range(N):
	count=0
	for j in graph[i]:
		if H[i]<=H[j-1]:
			count+=1
			break
	if count==0:
		answer+=1
print(answer)

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):
    a,b=map(int,input().split())
    a-=1;b-=1
    A[a].append(b)
    A[b].append(a)
ans=0
for i in range(n):
    for j in A[i]:
        if H[j]>=H[i]:break
    else:
        ans+=1
print(ans)

Submission status: Accepted

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

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

rank_hlist = sorted(hlist)
rank_dict = dict()
for i in range(n):
    rank_dict[rank_hlist[i]] = i

ab_list = []
for i in range(m):
    a, b = map(int,input().split())
    if rank_dict[hlist[a-1]] < rank_dict[hlist[b-1]]:
        a,b = b,a
    ab_list.append([a,b])

good_n = [1]*n

ab_list.sort(key=lambda x:x[0], reverse=True)

for i in range(m):
    ab = ab_list[i]
    if rank_dict[hlist[ab[0]-1]] > rank_dict[hlist[ab[1]-1]]:
        good_n[ab[1]-1] = 0
    elif rank_dict[hlist[ab[0]-1]] == rank_dict[hlist[ab[1]-1]]:
        good_n[ab[0]-1] = 0
        good_n[ab[1]-1] = 0
    
print(good_n.count(1))

Submission status: Accepted

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

Submission status: Accepted

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

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

res = sum([H[i] > A[i] for i in range(N)])
print(res)

Submission status: Accepted

Solution code:
ini = lambda : int(input())
inm = lambda : map(int,input().split())
inl = lambda : list(map(int,input().split()))
gcd = lambda x,y : gcd(y,x%y) if x%y else y
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])
    if temp!=1:
        arr.append([temp, 1])
    if arr==[]:
        arr.append([n, 1])
    return arr
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    divisors.sort()
    return divisors

n,m = inm()
h = inl()
p = [True] * n
for i in range(m):
    a,b = inm()
    a -= 1
    b -= 1
    if h[a] >= h[b]:
        p[b] = False
    if h[b] >= h[a]:
        p[a] = False
ans = sum(p)
print(ans)

Submission status: Accepted

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

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[b-1] > h[a-1]:
        l[a-1] = 0
    else:
        l[a-1] = l[b-1] = 0
        
print(sum(l))

Submission status: Accepted

Solution code:
N, M, *HAB = map(int, open(0).read().split())
H, AB = [0] + HAB[:N], HAB[N:]
good = [False] + [True] * N
for a, b in zip(*[iter(AB)] * 2):
  if H[a] >= H[b]:
    good[b] = False
  if H[b] >= H[a]:
    good[a] = False
print(sum(good))

Submission status: Accepted

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

for m in range(M):
  A,B = map(int,input().split())
  if H[A]<=H[B]:
    S.add(A)
  if H[A]>=H[B]:
    S.add(B)

print(N-len(S))

Submission status: Accepted

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

cnt = 0
for i in range(n):
    mx = -1
    for j in g[i]:
        mx = max(mx, h[j])
    cnt += h[i] > mx

print(cnt)

Submission status: Accepted

Solution code:
n, m = map(int,input().split())
h = list(map(int, input().split()))
e = [[] for _ in range(n)]
for i in range(m):
    u, v = map(int,input().split())
    u -= 1
    v -= 1
    e[u].append(h[u]- h[v])
    e[v].append(h[v]- h[u])

cnt = 0
for i in range(n):
    if not e[i]:
        cnt += 1
    elif min(e[i]) > 0:
        cnt += 1
print(cnt)

Submission status: Accepted

Solution code:
n,m = list(map(int, input().split()))
h = list(map(int, input().split()))
nice = list(1 for i in range(n))
def chk_nice(x,y): 
    global nice
    if nice[x] != 0:
        nice[x] = (h[x] > h[y])
for i in range(m):
    a,b = list(map(int, input().split()))
    chk_nice(a-1, b-1)
    chk_nice(b-1, a-1)
print(sum(nice))

Submission status: Accepted

Solution code:
def mapt(fn, *args):
    return tuple(map(fn, *args))


def main():
    n, m = mapt(int, input().split(" "))
    h = mapt(int, input().split(" "))
    ok = [True for i in range(n)]
    for i in range(m):
        a, b = mapt(int, input().split(" "))
        a = a-1
        b = b-1
        if h[a] <= h[b]: ok[a] = False
        if h[b] <= h[a]: ok[b] = False

    print(sum(ok))

main()

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def resolve():
    N, M = map(int, input().split())
    H = list(map(int, input().split()))
    higher_peeks = [0] * N

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

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

if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
h=list(map(int,input().split()))
a,b=[],[]
for i in range(m):
    c,d=map(int,input().split())
    a.append(c)
    b.append(d)
s=[]
for i in range(m):
    if h[a[i]-1]<h[b[i]-1]:
        s.append(a[i])
    elif h[a[i]-1]>h[b[i]-1]:
        s.append(b[i])
    else:
        s.append(a[i])
        s.append(b[i])
d=len(set(s))
print(n-d)

Submission status: Accepted

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

print(sum(H))

Submission status: Accepted

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

Submission status: Accepted

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

for _ in range(M):
    a, b = map(int, input().split())
    g[a].append(b)
    g[b].append(a)

cnt = 0
for n in range(1,N+1):
    for i in g[n]:
        if H[n-1] <= H[i-1]:
            break
    else:
        cnt += 1

print(cnt)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
h=list(map(int,input().split()))
flag=[True for _ in range(n)]
for i in range(m):
  a,b=map(int,input().split())
  if h[a-1] >= h[b-1]:
    flag[b-1] = False 
  if h[b-1] >= h[a-1]:
    flag[a-1] = False 
print(flag.count(True))

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.read
readlines = sys.stdin.readlines
def main():
    n, m = map(int, input().split())
    h = tuple(map(int, input().split()))
    edges = {e:[] for e in range(n)}
    for _ in range(m):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        edges[a].append(h[b])
        edges[b].append(h[a])
    r = 0
    for i, he in enumerate(h):
        if not edges[i]:
            r += 1
        else:
            r += he > max(edges[i])

    print(r)
if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

route={i:[] for i in range(1,N+1)}

for i in range(M):
    array=tuple(map(int,input().split()))
    route[array[0]].append(array[1])
    route[array[1]].append(array[0])

Obs=[True for i in range(N)]

for i in range(1,N+1):
    if Obs[i-1]==True:
        for j in route[i]:
            if H[i-1]>H[j-1]:
                Obs[j-1]=False
            else:
                Obs[i-1]=False

ans=0
for i in range(len(Obs)):
    if Obs[i]:
        ans+=1

print(ans)

Submission status: Accepted

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

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

for i in range(n):
    my_height = h[i]
    neighbor_height = neighbor[i]
    if all(my_height > x for x in neighbor_height):
        good += 1

print(good)

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,b,=a-1,b-1
    if h[a]==h[b]:
        ans[a],ans[b]=0,0
    elif h[a]>h[b]:
        ans[b]=0
    else:
        ans[a]=0
print(ans.count(1))

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
H = list(map(int, input().split()))
ans = M
counted = []
appeared = set()


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

ans = len(H) - len(appeared)
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 _ in range(m)]


point = [0]*n
app = [0]*n
cnt = []

for i in ab:
    app[i[0]-1] += 1
    app[i[1]-1] += 1
    if h[i[0]-1] > h[i[1]-1]:
        point[i[0]-1] += 1
    elif h[i[0]-1] < h[i[1]-1]:
        point[i[1]-1] += 1
for i in range(n):
    if app[i] == point[i]:
        cnt.append(i+1)
print(len(cnt))

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-
#
# FileName: 	C_fix_2
# CreatedDate:  2020-08-08 01:59:29 +0900
# LastModified: 2020-08-08 02:11:36 +0900
#


import os
import sys
# import numpy as np
# import pandas as pd


def main():
    n, m  = map(int, input().split())
    h = [0] + list(map(int, input().split()))
    path = [[] for _ in range(n+1)]
    for _ in range(m):
        a, b = map(int, input().split())
        path[a].append(h[b])
        path[b].append(h[a])
    ans = 0
    for index in range(1, n+1):
        if path[index] and h[index] > max(path[index]):
            ans += 1
        elif not path[index]:
            ans += 1

    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

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

#print(N,M,H)

bad=set()
for ln in sys.stdin:
    A,B=map(int,ln.split())
    x,y=H[A-1],H[B-1]
    if x>y:
        bad.add(B)
    elif x<y:
        bad.add(A)
    else:
        bad.add(A)
        bad.add(B)

print(N-len(bad))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
def main():
    import sys

    input = sys.stdin.readline

    N, M = map(int, input().split())
    H = [0] + [int(x) for x in input().split()]
    graph = [[] for _ in [0] * (N + 1)]
    for i in range(M):
        a, b = map(int, input().split())
        graph[a].append(b)
        graph[b].append(a)
    
    res = N
    for i in range(1, N + 1):
        if graph[i]:
            for j in graph[i]:
                if H[j] >= H[i]:
                    res -= 1
                    break
    print(res)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
f=lambda:map(int,input().split())
N,M=f()
*H,=f()

g = [[] for _ in range(N)]
    
for _ in range(M):
 a,b=f()
 g[a-1].append(b-1)
 g[b-1].append(a-1)
print(sum(all(H[j]<H[i]  for j in g[i]) for i in range(N)))

Submission status: Accepted

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

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

print(sum(all(H[j]<H[i]  for j in graph[i]) for i in range(N)))

Submission status: Accepted

Solution code:

N, M = map(int, input().split())
H = list(map(int, input().split()))
X = [list(map(int, input().split())) for _ in range(M)]

ok = [True] * (N + 1)
for a, b in X:
    ok[a] &= H[a - 1] > H[b - 1]
    ok[b] &= H[a - 1] < H[b - 1]

print(sum(ok[1:]))

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

H=[]
H=list(map(int,input().split()))
C=[]
for i in range(n):
    C.append(1)

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

print( C.count(1))

Submission status: Accepted

Solution code:
class tower:
    def __init__(self, H):
        self.H = H
        self.neighbors = []
        self.checked = False
    def add_path(self, a):
        self.neighbors.append(a)
N, M = [int(i) for i in input().split()]
Hs = [int(i) for i in input().split()]
T = {}
for i in range(N):
    T[i+1] = tower(Hs[i])
for i in range(M):
    A, B = [int(i) for i in input().split()]
    T[A].add_path(B)
    T[B].add_path(A)
items_sorted = sorted(T.items(), key = lambda x : x[1].H, reverse=1)
counter = 0
for each in items_sorted:
    i = each[0]
    t = each[1]
    if t.checked:
        continue
    else:
        t.checked = True
        flag = True
        for a in t.neighbors:
            T[a].checked = True
            if t.H <= T[a].H:
                flag = False

        if flag:
            counter += 1
print(counter)

Submission status: Accepted

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

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

mj = []

for i in range(m):
    mj.append(list(map(int,input().split())))

cnt_w = [0 for _ in range(n)]
cnt = [0 for _ in range(n)]

for i in range(m):
    cnt[mj[i][0]-1] += 1
    cnt[mj[i][1]-1] += 1
    if h[mj[i][0]-1] > h[mj[i][1]-1]:
        cnt_w[mj[i][0]-1] += 1
    elif h[mj[i][0]-1] < h[mj[i][1]-1]:
        cnt_w[mj[i][1]-1] += 1

tower = 0
for i in range(n):
    if cnt[i] == cnt_w[i]:
        tower += 1
print(tower)

Submission status: Accepted

Solution code:
# import itertools
# import math
# import sys
# import numpy as np

# K = int(input())
# S = input()
# n, *a = map(int, open(0))
N, M = map(int, input().split())
H = list(map(int, input().split()))
# Q = list(map(int, input().split()))
# S = input()

# d = sorted(d.items(), key=lambda x:x[0]) # keyでsort
# all_cases = list(itertools.permutations(P))
# a = list(itertools.combinations_with_replacement([i for i in range(1, M + 1)], N))
# print(a[0][0])
# print(conditions[0])

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

Submission status: Accepted

Solution code:
from heapq import heappush, heappop
def readinput():
    n,m=map(int,input().split())
    h=list(map(int,input().split()))
    nList=[]
    for i in range(n+1):
        nList.append([])
    for i in range(m):
        a,b=map(int,input().split())
        heappush(nList[a],-h[b-1])
        heappush(nList[b],-h[a-1])

    return n,m,h,nList

def main(n,m,h,nList):
    count=0
    for i in range(1,n+1):
        if len(nList[i])==0:
            count+=1
        else:
            hi=-heappop(nList[i])
            if h[i-1]>hi:
                count+=1
    return count

if __name__=='__main__':
    n,m,h,nList=readinput()
    ans=main(n,m,h,nList)
    print(ans)

Submission status: Accepted

Solution code:
word = list(map(int,input().split()))
hyoko = list(map(int,input().split()))
road = [0]*word[1]
for i in range(word[1]):
    road[i] = list(map(int,input().split()))
tenbo = [1]*word[0]

for j in range(word[1]):
    if hyoko[road[j][0]-1] > hyoko[road[j][1]-1]:
        tenbo[road[j][0]-1] *= 1
        tenbo[road[j][1]-1] = 0
    elif hyoko[road[j][0]-1] < hyoko[road[j][1]-1]:
        tenbo[road[j][0]-1] = 0
        tenbo[road[j][1]-1] *= 1
    else:
        tenbo[road[j][0]-1] = 0
        tenbo[road[j][1]-1] = 0
answer = word[0] - tenbo.count(0)
print(answer)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**5 + 5)
N, M = map(int, input().split())
H = [0] + list(map(int, input().split()))
Graph = [[] for _ in range(N+1)]
is_good = [False] + [True] * N
seen = [True] + [False] * N

def dfs(cur):
    global Graph, seen, H
    seen[cur] = True
    for nex in Graph[cur]:
        if H[nex] >= H[cur]:
            is_good[cur] = False
        if seen[nex]:
            continue
        dfs(nex)


for _ in range(M):
    a, b = map(int, input().split())
    Graph[a].append(b)
    Graph[b].append(a)

for i in range(1, N+1):
    if not seen[i]:
        dfs(i)

print(is_good.count(True))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n, m= map(int, input().split())
high = list(map(int, input().split()))
ans = [1]*n

for i in range(m):
    a, b = map(int, input().split())
    if high[a-1] > high[b-1]:
        ans[b-1] = 0
    elif high[a-1] < high[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=list(map(int,input().split()))
a=[0 for i in range(m)]
b=[0 for i in range(m)]
for i in range(m):
  a[i],b[i]=map(int,input().split())

count=0
c=[[] for i in range(n)]
for i in range(m):
  c[a[i]-1].append(b[i]-1)
  c[b[i]-1].append(a[i]-1)
  
for i in range(n):
  max_h=0
  for j in range(len(c[i])):
    max_h=max(max_h, h[c[i][j]])
  if max_h < h[i]:
    count+=1
print(count)

Submission status: Accepted

Solution code:
n, m = list(map(int, input().split()))
h = list(map(int, input().split()))
routes = [[] for _ in range(len(h) + 1)]
for _ in range(m):
    a, b = list(map(int, input().split()))
    routes[a].append(b)
    routes[b].append(a)
good = 0
for i in range(1, len(routes)):
    if len(routes[i]) == 0:
        good += 1
        continue
    if h[i - 1] > max([h[j - 1] for j in routes[i]]):
        good += 1
print(good)

Submission status: Accepted

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

"""
0: 初期値
1: highest
-1: not highest
"""
for i in range(m):
    a, b = map(int, input().split())
    a, b = a - 1, b - 1
    if h[a] > h[b]:
        if res[a] == 0:
            res[a] = 1
        res[b] = -1
    elif h[a] < h[b]:
        res[a] = -1
        if res[b] == 0:
            res[b] = 1
    elif h[a] == h[b]:
        res[a] = -1
        res[b] = -1

print(res.count(1) + res.count(0))

Submission status: Accepted

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

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

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

ans = 0
for i in range(n):
    flg = True
    for j in d[i]:
        if h[i] <= h[j]:
            flg = False
            break
    if flg:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
import math
def facts(n):
    ans = []
    for  i in range(1, int(math.sqrt(n)+1)):
        if(n%i==0):
            ans.append(i)
            ans.append(n//i)
    ans = sorted(ans)
    return ans


n,m = map(int, input().split())
hs = list(map(int, input().split()))
state = [1 for i in range(n)]
for i in range(m):
    a,b = map(int, input().split())
    if(hs[a-1]>=hs[b-1]):
        state[b-1] =0
    if(hs[a-1]<= hs[b-1]):
        state[a-1]= 0
ans = 0
for i in range(n):
    if(state[i]==1):
        ans+=1
print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

ans = 0
for i in range(n):
	ans += h[i] > ma[i]

print(ans)

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)]
flag = [0]*n
for i in range(m):
  if H[a[i][0]-1] > H[a[i][1]-1]:
    flag[a[i][1]-1] = 2
  elif H[a[i][0]-1] == H[a[i][1]-1]:
    flag[a[i][0]-1] = 2
    flag[a[i][1]-1] = 2
  else:
    flag[a[i][0]-1] = 2
cnt = 0
for j in range(n):
  if flag[j] == 0:
    cnt += 1
print(cnt)