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:
#!/usr/bin/env python3

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

G = {}

for i in range(1, N+1):
    G[i] = []
for i in range(M):
    a, b = map(int, input().split())
    G[a].append(b)
    G[b].append(a)

ans = 0
for n, miti in G.items():
    f = True
    if len(miti)==0:
        ans += 1
        continue
    miti = list(set(miti))
    for m in miti:
        if H[n-1] <= H[m-1]:
            f = False
            break
    if f:
        ans += 1

print(ans)

Submission status: Accepted

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

N,M = map(int,input().split())
H = list(map(int,input().split()))
D = [[] for i in range(N)]
Q = deque()
Q.append(0)
visited = [-1]*N
ans = 0

for i in range(M):
    A,B = map(int,input().split())
    A -= 1
    B -= 1
    D[A].append(B)
    D[B].append(A)


for i in range(N):
    if visited[i] == -1:
        cur = H[i]
        flag = 0
        for x in D[i]:
            if H[x] > cur:
                visited[i] = 0
                flag = 1
                break
            elif H[x] < cur:
                visited[x] = 0
            else:
                flag = 1
        if flag == 0:
            ans += 1

print(ans)

Submission status: Accepted

Solution code:
n,m = map(int, input().split())
H = list(map(int, input().split()))
adjacent = {i: [] for i in range(n)}
for _ in range(m):
    a, b = map(int, input().split())
    adjacent[a-1].append(b-1)
    adjacent[b-1].append(a-1)
good = 0
for i in range(n):
    h = H[i]
    for j in adjacent[i]:
        if h <= H[j]:
            break
    else:
        good += 1
print(good)

Submission status: Accepted

Solution code:
import numpy as np

def main():
  N, M = input().split()
  N = int(N)
  M = int(M)

  # H = []
  H = [int(i) for i in input().split()]
  # arg_list = list(np.argsort(np.array(H))[::-1])
  bad_obs = set()

  for m in range(M):
    A, B = input().split()
    A = int(A)-1
    B = int(B)-1
    if H[A] < H[B]:
      bad_obs.add(A)
    elif H[A] > H[B]:
      bad_obs.add(B)
    else:
      bad_obs.add(A)
      bad_obs.add(B)

  print(len(H) - len(bad_obs))


if __name__ == "__main__":
    main()

Submission status: Accepted

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

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

for j in J:
    n1 = j[0]
    n2 = j[1]
    h1 = H[n1-1]
    h2 = H[n2-1]
    if h1 < h2:
        if res[n1]:
            res[n1] = False
    elif h2 < h1:
        if res[n2]:
            res[n2] = False
    else:
        if res[n1]:
            res[n1] = False
        if res[n2]:
            res[n2] = False

l = 0
for v in res.values():
    if v:
        l+=1
print(l)

Submission status: Accepted

Solution code:
import sys
import os

def file_input():
    f = open('../Beginner_Contest_166/input.txt', 'r')
    sys.stdin = f

def main():
    #file_input()
    # int(input())
    N,M=map(int, input().split())   #N:展望台 N:道
    H=list(map(int, input().split()))   #高さ

    c=0
    nice=[True]*N
    for i in range(M):
        A,B=map(int, input().split())
        # print("H["+str(A)+"]"+str(H[A-1])+" H["+str(B)+"]:"+str(H[B-1]))
        if H[A-1]>H[B-1]:
            if nice[B-1]:
                nice[B-1]=False
                c+=1
        elif H[A-1]<H[B-1]:
            if nice[A-1]:
                nice[A-1]=False
                c+=1
        elif H[A-1]==H[B-1]:
            if nice[B-1]:
                nice[B-1]=False
                c+=1
            if nice[A-1]:
                nice[A-1]=False
                c+=1

    print(N-c)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict
good = defaultdict(int)

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

for m in range(M):
    a, b = list(map(int, input().split(" ")))
    if height[a-1] < height[b-1]:
        good[a] += 1
    elif height[a-1] > height[b-1]:
        good[b] += 1
    else:
        good[a] += 1
        good[b] += 1

print(N-len(good))

Submission status: Accepted

Solution code:
def higher(k, v):
    for i in v:
        if h[k - 1] <= h[i - 1]:
            return 0
    return 1


n, m = [int(i) for i in input().split()]
h = [int(i) for i in input().split()]

obs = {k: [] for k in range(1, n + 1)}
for _ in range(m):
    a, b = [int(i) for i in input().split()]
    obs[a].append(b)
    obs[b].append(a)

good = 0
for k, v in obs.items():
    if len(v) == 0:
        good += 1
        continue
    good += higher(k, v)
print(good)

Submission status: Accepted

Solution code:
def main(N, M, H, AB):
    bad = []
    for A, B in AB:
        if H[A - 1] >= H[B - 1]: #pythonは一個ずれる
            bad.append(B)
        if H[B - 1] >= H[A - 1]:
            bad.append(A)
    print(N - len(list(set(bad))))

if __name__ == '__main__':
    N, M = list(map(int, input().split()))
    H = list(map(int, input().split()))
    AB = []
    for i in range(M):
        AB.append(list(map(int, input().split())))
    main(N, M, H, AB)

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
Hs=list(map(int, input().split()))
V=[[] for _ in range(N)]
for _ in range(M):
    A,B=map(int,input().split())
    V[A-1].append(B-1)
    V[B-1].append(A-1)
ans=0
for n in range(N):
    Hn=Hs[n]
    for n_adj in V[n]:
        if Hn <= Hs[n_adj]:
            break
    else:
        # good
        ans+=1
        continue
    # bad

print(ans)

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]=0
    else:
        ans[a-1]=ans[b-1]=0
print(len([i for i in ans if i%2!=0]))

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()
def main():
    n,m=map(int,input().split())
    H=[int(_) for _ in input().split()]
    HH= [0]*n

    for i in range(m):
        a,b=map(int,input().split())
        HH[a-1]=max(HH[a-1],H[b-1])
        HH[b-1]=max(HH[b-1],H[a-1])
    ans=0
    for i,hh in enumerate(HH):
        if H[i]>hh or hh==0:
            ans+=1
    print(ans)

if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
n, m = (int(x) for x in input().split())
list_h = list(map(int, input().split()))
list_n =[[-1 for i in range(1)] for j in range(n)]
count=0
for i in range(m):
    a,b = (int(x) for x in input().split())
    if list_n[a-1]==-1:
        list_n[a-1]=b
    else:
        list_n[a-1].append(b)
    if list_n[b-1]==-1:
        list_n[b-1]=a
    else:
        list_n[b-1].append(a)
for i in range(n):
    boo = True
    h = list_h[i]
    for j in range(len(list_n[i])):
        if list_n[i][j]==-1:
            pass
        else:
            k = list_n[i][j]
            if h<=list_h[k-1]:
                boo=False
    if boo:
        count+=1
print(count)

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
read = sys.stdin.buffer.read
sys.setrecursionlimit(10 ** 7)

N, M = map(int, readline().split())
H = list(map(int, readline().split()))

G = [[] for _ in range(N)]
for _ in range(M):
    A, B = map(int, readline().split())
    G[A-1].append(B)
    G[B-1].append(A)

ans = 0
for i, shimas in enumerate(G):
    is_ok = True
    height = H[i]
    for shima in shimas:
        if height <= H[shima-1]:
            is_ok = False
            break
    if is_ok:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
H = [int(i) for i in input().split()]
A = [0] * M
B = [0] * M
for i in range(M):
    A[i], B[i] = map(int, input().split())
d = {}
for i in range(M):
    if A[i] not in d:
        d[A[i]] = set()
    if B[i] not in d:
        d[B[i]] = set()
    d[A[i]].add(B[i])
    d[B[i]].add(A[i])

ans = 0
for i in range(N):
    if i+1 not in d:
        ans += 1
        continue

    val = d[i+1]
    flag = True
    for c in val:
        if H[i] <= H[c-1]:
            flag = False
            break
    if flag:
        ans += 1
print(ans)

Submission status: Accepted

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

road = [set() for _ in range(N)]
for i in range(M):
    A, B = map(int, input().split())
    road[A-1].add(B-1)
    road[B-1].add(A-1)

ans = [True] * N
for i in range(N):
    tmp = H[i]
    lis = list(road[i])
    for j in range(len(lis)):
        if tmp <= H[lis[j]]:
            ans[i] = False
            break

print(ans.count(True))

Submission status: Accepted

Solution code:
import sys


def input():
    return sys.stdin.readline().strip()


def main():
    N, M = map(int, input().split())
    H = list(map(int, input().split()))
    Tree = [0 for _ in range(N)]
    cnt = [0 for _ in range(N)]

    for _ in range(M):
        A, B = map(int, input().split())

        cnt[A - 1] += 1
        cnt[B - 1] += 1
        if H[A - 1] > H[B - 1]:
            Tree[A - 1] += 1
        elif H[B - 1] > H[A - 1]:
            Tree[B - 1] += 1
    answer = 0
    for i in range(N):
        if Tree[i] == cnt[i]:
            answer += 1
    print(answer)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

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

chk_l = [0 for i in range(N)]

for i in range(M):
	road_l = list(map(int, input().split()))
	left_h = road_l[0]-1
	right_h = road_l[1]-1

	if(H_l[left_h] > H_l[right_h]):
		chk_l[right_h] -= 1
	elif(H_l[left_h] < H_l[right_h]):
		chk_l[left_h] -= 1
	else:
		chk_l[left_h] -= 1
		chk_l[right_h] -= 1

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

print(cnt)

Submission status: Accepted

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

mp = {}
for v in range(1, N+1):
    mp[v] = True
for a, b in X:
    if H[a-1] <= H[b-1]:
        mp[a] = False
    if H[b-1] <= H[a-1]:
        mp[b] = False
ans = 0
for v in range(1, N+1):
    if mp[v]:
        ans += 1
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
hList = list(map(int, input().split()))
rootList = [list(map(int, input().split())) for _ in range(m)]
obsList = [1 for _ in range(n)]
for i in rootList:
    a, b = i[0]-1, i[1]-1
    aH, bH = hList[a] , hList[b]
    if aH >= bH:
        obsList[b] = 0
    if aH <= bH:
        obsList[a] = 0
print(sum(obsList))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
H=list(map(int,input().split()))
H.insert(0,0)
path=[[] for i in range(N+1)]

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

ans = 0
for i in range(1,N+1):
    if path[i] == []:
        ans += 1
    else:
        hi=H[i]
        f = True
        for t in path[i]:
            if hi <= H[t]:
                f = False
                break
        if f:
            ans += 1

print(ans)

Submission status: Accepted

Solution code:
ii = lambda : int(input())
mi = lambda : map(int,input().split())
li = lambda : list(map(int,input().split()))

n,m = mi()
h = li()
r = [[]*n]
flg = [1] * n
for i in range(m):
    a,b = mi()
    if h[a-1] < h[b-1]:
        flg[a-1] = 0
    elif h[b-1] < h[a-1]:
        flg[b-1] = 0
    else:
        flg[a-1] = 0
        flg[b-1] = 0

print(sum(flg))

Submission status: Accepted

Solution code:
n, m = map(int,input().split())
graph = {i:[] for i in range(n)}
H = list(map(int,input().split()))
for _ in range(m):
  a,b = map(int,input().split())
  a, b = a-1, b-1
  
  if H[a]<H[b]:
    graph[a].append(b)
  elif H[a]>H[b]:
    graph[b].append(a)
  else:
    graph[a].append(b)
    graph[b].append(a)
ans = 0

for i in range(n):
  if len(graph[i]) ==0:
    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 _ in range(m)]

#print("=====")
ok = [True for _ in range(n)]
for i in range(m):
    #print(h[ab[i][0]-1], h[ab[i][1]-1])
    if h[ab[i][0]-1] > h[ab[i][1]-1]:
        ok[ab[i][1]-1] = False
    elif h[ab[i][0]-1] == h[ab[i][1]-1]:
        ok[ab[i][1]-1] = False
        ok[ab[i][0]-1] = False
    else:
        ok[ab[i][0]-1] = False
#print(ok)
print(sum(ok))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

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


ans = [1] * N
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)

count = N

for i in range(N):
    tmp = H[i]
    for next_ in G[i]:
        if tmp <= H[next_]:
            count -= 1
            break

print (count)

Submission status: Accepted

Solution code:
#! /Library/Frameworks/Python.framework/Versions/3.7/bin/python3
n, m = map(int, input().split())
Hs = list(map(int, input().split()))
spots = [0] * n
for i in range(m):
    a, b = map(int, input().split())
    if (Hs[a - 1] >= Hs[b - 1]):
        spots[b-1] += 1
    if (Hs[a - 1] <= Hs[b - 1]):
        spots[a-1] += 1
ans = 0
for spot in spots:
    if(spot == 0):
        ans += 1
print(ans)

Submission status: Accepted

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

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

ans = 0
for i in range(N):
    height = H[i]
    nx_nodes = graph[i]
    if len(nx_nodes) == 0:
        ans += 1
    else:
        if any([height <= H[nx] for nx in nx_nodes]):
            continue
        else:
            ans += 1
print(ans)

Submission status: Accepted

Solution code:
def mips():
    return map(int,input().split())
def msps():
    return map(str,input().split())
N,M = mips()
H = [el for el in mips()]
G = dict()
ans = 0
no = 0
for i in range(1,N+1):
    G[i] = set()
for i in range(M):
    a,b = mips()
    G[a].add(b)
    G[b].add(a)
for i in range(1,N+1):
    if G[i] == set():
        ans += 1
        continue
    else:
        for el in G[i]:
            if H[el-1] >= H[i-1]:
                no = 1
                break
    if no == 0:
        ans += 1
    no = 0
print(ans)

Submission status: Accepted

Solution code:


def solve():
    ans = 0
    for i in range(n):
        ans += check(i)
    print(ans)
    return

def check(i):
    for adj in r[i]:
        if h[adj] >= h[i]:
            return 0
    return 1




n, m = [int(s) for s in input().split(" ")]
h = [int(s) for s in input().split(" ")]
r = [[] for i in range(n)]
for i in range(m):
    a, b = ([int(s) for s in input().split(" ")])
    r[a-1].append(b-1)
    r[b-1].append(a-1)
solve()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n, m = map(int,input().split())
h = list(map(int,input().split()))
h.insert(0, -1)
g = set(range(1, n+1))
for _ in range(m):
    a, b = map(int, input().split())
    if h[a] <= h[b]:
        g.discard(a)

    if h[b] <= h[a]:
        g.discard(b)

print(len(g))

Submission status: Accepted

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

ans = 0
for i in range(N):
    if not G[i]:
        ans += 1
    elif H[i] > max(G[i]):
        ans += 1

print(ans)

Submission status: Accepted

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

del_ = []

for m in range(M):
    A, B = map(int, input().split())
    if H[A-1] < H[B-1]:
        del_.append(A)
    elif H[A-1] > H[B-1]:
        del_.append(B)
    else:
        del_.append(A)
        del_.append(B)
print(N - len(list(set(del_))))

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)]
c=0
pair = [[] for _ in range(n)]
for i in a:
    pair[i[0]-1].append(i[1]-1)
    pair[i[1]-1].append(i[0]-1)
for i in range(n):
    for hi in pair[i]:
        if h[i]<=h[hi]:
            break
    else:
        c+=1
print(c)

Submission status: Accepted

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

path=h[:]
for i in range(m):
    a,b=map(int,input().split(' '))
    if path[a-1]<=h[b-1]:
        path[a-1]=0
    if path[b-1]<=h[a-1]:
        path[b-1]=0
x=[0 for x in path if x!=0]
print(len(x))

Submission status: Accepted

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

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

res = 0
for u in range(n):
    flag = True
    h = hl[u]
    for v in e[u]:
        if hl[v]>=h:
            flag = False
            break
    # print(u,flag)
    if flag:
        res += 1
print(res)

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
H = [0] + list(map(int,input().split()))
G = dict([(i,[]) for i in range(1,N+1)])
for i in range(M):
  A,B = map(int,input().split())
  G[A].append(B)
  G[B].append(A)

cnt = 0
for i in range(1,N+1):
  det = 0
  for v in G[i]:
    if H[i] <= H[v]:
      det = 1
  if det == 0:
    cnt += 1
print(cnt)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

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

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

s = set()

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

print(n-len(s))

Submission status: Accepted

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

dicts = {i:True for i in range(N)}
for i in range(M):
    a, b = map(lambda x:int(x) - 1, input().split())
    if H[a] < H[b]:
        dicts[a] = False
    elif H[a] == H[b]:
        dicts[a] = False
        dicts[b] = False
    else:
        dicts[b] = False

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

print(ans)

Submission status: Accepted

Solution code:
N, M = [int(x) for x in input().split()]
H = [int(x) for x in input().split()]
A = [0]*M
B = [0]*M
for m in range(M):
    A[m],B[m] = [int(x) for x in input().split()]
result = [True]*N
#print(result)
for m in range(M):
    #print(H[A[m]-1],H[B[m]-1])
    if H[A[m]-1]==H[B[m]-1]:
        result[A[m]-1] = False
        result[B[m]-1] = False
    elif H[A[m]-1] < H[B[m]-1]:
        result[A[m]-1] = False
    else:
        result[B[m]-1] = False
count = 0
#print(result)
for r in result:
    if r:
        count+=1
print(count)

Submission status: Accepted

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

for _ in range(m):
  a,b = map(int, input().split())
  d[a].append(b)
  d[b].append(a)
  
count = 0  
  
for k,v in d.items():
  if not v:
    count += 1
  else:
    flg = True
    for v_i in v:
      if H[k-1]<=H[v_i-1]:
        flg = False
        break
    if flg:
      count += 1
    
print(count)

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline

N,M=(int(x) for x in input().rstrip('\n').split())
Hs = [int(x) for x in input().rstrip('\n').split()]
nums = [1 for x in Hs]
for i in range(M):
  roads = [int(x) for x in input().rstrip('\n').split()]
  if Hs[roads[0]-1] < Hs[roads[1]-1]:
    nums[roads[0]-1] = 0
  elif Hs[roads[0]-1] > Hs[roads[1]-1]:
    nums[roads[1]-1] = 0
  else:
    nums[roads[0]-1] = 0
    nums[roads[1]-1] = 0
print(sum(nums))

Submission status: Accepted

Solution code:
from collections import defaultdict
N,K=map(int,input().split())
L=list(map(int,input().split()))
Hash=defaultdict(lambda:list())
for i in range(K):
    x,y=map(int,input().split())
    Hash[x-1].append(y-1)
    Hash[y-1].append(x-1)
count=0
for i in range(N):
    FLAG=0
    for k in Hash[i]:
        if L[k]>=L[i]:
            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()))
ans = [1 for _ in range(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] = 0
    else:
       ans[a-1] = 0
       ans[b-1] = 0
cnt = 0
for i in range(n):
    if ans[i] == 0:
        cnt += 1
print(n-cnt)

Submission status: Accepted

Solution code:
def c_peaks():
    N, M = [int(i) for i in input().split()]
    H = [int(i) for i in input().split()]
    Roads = [[int(i) for i in input().split()] for j in range(M)]

    graph = [[] for _ in range(N)]
    for a, b in Roads:
        graph[a - 1].append(b - 1)
        graph[b - 1].append(a - 1)

    ans = 0
    for v, neighbor in enumerate(graph):
        if not neighbor:
            ans += 1
            continue

        height = H[v]
        for to in neighbor:
            if height <= H[to]:
                break
        else:
            ans += 1
    return ans

print(c_peaks())

Submission status: Accepted

Solution code:
n, m = list(map(int, input().split()))
H = list(map(int, input().split()))
d = {i: [] for i in range(1, n + 1)}
for _ in range(m):
    a, b = list(map(int, input().split()))
    d[a].append(b)
    d[b].append(a)
cnt = 0
for i in range(1, n + 1):
    cmps = d[i]
    is_good = True
    for cmp in cmps:
        if H[i - 1] <= H[cmp - 1]:
            is_good = False
            break
    if is_good:
        cnt += 1
print(cnt)

Submission status: Accepted

Solution code:
from collections import defaultdict

def main():
    N, M = map(int, input().split())
    heights = list(map(int, input().split()))
    d = defaultdict(set)
    mous = set()
    for i in range(M):
        a, b = map(int, input().split())
        d[a-1].add(heights[b-1])
        d[b-1].add(heights[a-1])
        mous.add(a)
        mous.add(b)
    num_good = 0
    for k in set(d.keys()):
        is_good = True
        if heights[k] <= max(d[k]):
            is_good = False
        if is_good:
            num_good += 1
    num_good += N - len(mous)

    print(num_good)

if __name__ == "__main__":
    main()

Submission status: Accepted

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

Submission status: Accepted

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

matrix = [[] for _ in range(n)]
for a, b in edges:
    matrix[a - 1].append(b - 1)
    matrix[b - 1].append(a - 1)

good = 0
for a in range(n):
    bs = matrix[a]
    h = hs[a]
    highest = all([hs[b] < h for b in bs])
    if len(bs) == 0 or highest:
        good += 1

print(good)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
height = list(map(int, input().split()))
roads = [[] for _ in range(n)]
checked = [1] * n

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

ans = 0
for i in range(n):
    if checked[i] == 0:
        continue
    for road in roads[i]:
        if height[i] > height[road]:
            checked[road] = 0
        else:
            checked[i] = 0

print(sum(checked))

Submission status: Accepted

Solution code:
# coding: utf-8


def solve(*args: str) -> str:
    n, m = map(int, args[0].split())
    H = list(map(int, args[1].split()))
    AB = [tuple(map(int, ab.split())) for ab in args[2:]]

    R = [set() for _ in range(n)]
    for a, b in AB:
        R[a-1].add(b-1)
        R[b-1].add(a-1)

    ret = 0
    for i, D in enumerate(R):
        if len(D) == 0 or max([H[d] for d in D]) < H[i]:
            ret += 1

    return str(ret)


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
h_base=list(map(int,input().split()))
h={}
road={}
for i in range(1,n+1):
    h[i]=h_base[i-1]
    road[i]=[]

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

ans=0
for i in road.keys():
    if len(road[i])==0:
        ans+=1
    else:
        count=0
        for each in road[i]:
            if h[i]<=h[each]:
                count+=1
        if count==0:
            ans+=1
print(ans)

Submission status: Accepted

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

tembo = [1]*n

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

print(sum(tembo))

Submission status: Accepted

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

H = [None] + list(map(int, input().split()))

good = [None] + [True for _ in range(N)]

for _ in range(M):
    a, b = map(int, input().split())
    if H[a] == H[b]:
        good[a] = False
        good[b] = False
    elif H[a] < H[b]:
        good[a] = False
    else:
        good[b] = False


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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 6)

def main():
    N, M = map(int, input().split())
    H = list(map(int, input().split()))
    T = [True] * N
    for _ in range(M):
        A, B = map(int, input().split())
        if H[A-1] <= H[B-1]:
            T[A-1] = False
        if H[B-1] <= H[A-1]:
            T[B-1] = False
    print(len([1 for t in T if t]))

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
H = list(map(int,input().split()))
H.insert(0,0)
G = {i:[] for i in range(1,N+1)}
for _ in range(M):
    a,b = map(int,input().split())
    G[a].append(b)
    G[b].append(a)
cnt = 0
for i in range(1,N+1):
    flag = 0
    for j in G[i]:
        if H[j]>=H[i]:
            flag=1
            break
    if flag==0:
        cnt += 1
print(cnt)

Submission status: Accepted

Solution code:

N,M = map(int,input().split())
H = list(map(int,input().split()))
ans = [0]*N


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

ans = [i for i in range(N) if ans[i]==0]
print(len(ans))

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
h = list(map(int, input().split()))
l = [1 for _ in range(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
  else:
    l[a - 1] = 0
    l[b - 1] = 0

cnt = 0
for i in l:
  if i == 1:
    cnt += 1

print(cnt)

Submission status: Accepted

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

visited = [False] * (N + 1)

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

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

ans = 0
for n in range(1, N + 1):

    if visited[n]:
        continue

    visited[n] = True

    if len(g[n]) == 0:
        ans += 1
    else:
        ok = True
        for c in g[n]:
            if H[n - 1] <= H[c - 1]:
                ok = False
            else:
                visited[c] = True
        if ok:
            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(n)]
ans = 0
for i in range(m):
    a, b = map(int, input().split())
    path[a - 1].append(b - 1)
    path[b - 1].append(a - 1)

for i in range(n):
    if len(path[i]) == 0:
        ans += 1
    for j in range(len(path[i])):
        if h[path[i][j]] >= h[i]:
            break
        if j == len(path[i]) - 1:
            ans += 1
print(ans)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
list_H = list(map(int, input().split()))
list_AB = [ list(map(int,input().split(" "))) for i in range(m)]
list_ANS = [1]*n

for i, j in list_AB:
    if list_H[i-1] > list_H[j-1]:
        list_ANS[j-1] = 0
    elif list_H[j-1] > list_H[i-1]:
        list_ANS[i-1] = 0
    else:
        list_ANS[i-1] = 0
        list_ANS[j-1] = 0

print(sum(list_ANS))