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:
def main():
    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
            ans[b] = 0
        elif H[a] < H[b]:
            ans[b] = 1 & ans[b]
            ans[a] = 0
        else:
            ans[b] = 0
            ans[a] = 1 & ans[a]
    cnt = ans.count(1)
    print(cnt)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N,M=[int(x) for x in input().rstrip().split()]
H=[int(x) for x in input().rstrip().split()]
ans=[[] for i in range(N)]
# print(ans)

for i in range(M):
  A,B=[int(x) for x in input().rstrip().split()]
  ans[A-1].append(H[B-1])
  ans[B-1].append(H[A-1])

now=0
cnt=0
for i in range(N):
  if len(ans[i])==0:
    now=0
  else:
    now=max(ans[i])
  if now<H[i]:
    cnt+=1

print(cnt)

Submission status: Accepted

Solution code:
import sys, bisect, math, itertools, string, queue, copy
# import numpy as np
# import scipy
from collections import Counter,defaultdict,deque
from itertools import permutations, combinations
from heapq import heappop, heappush
from fractions import gcd
# input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
def inp(): return int(input())
def inpm(): return map(int,input().split())
def inpl(): return list(map(int, input().split()))
def inpls(): return list(input().split())
def inplm(n): return list(int(input()) for _ in range(n))
def inplL(n): return [list(input()) for _ in range(n)]
def inplT(n): return [tuple(input()) for _ in range(n)]
def inpll(n): return [list(map(int, input().split())) for _ in range(n)]
def inplls(n): return sorted([list(map(int, input().split())) for _ in range(n)])

def main():
    n,m = inpm()
    h = inpl()
    g = [[] for _ in range(n)]
    for _ in range(m):
        a,b = inpm()
        a -= 1
        b -= 1
        g[a].append(b)
        g[b].append(a)
    ans = 0
    for i in range(n):
        flag = 1
        for j in range(len(g[i])):
            if h[i] <= h[g[i][j]]:
                flag = 0
        if flag:
            ans += 1
    print(ans)
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
date0=input().rstrip().split(" ")
N=int(date0[0])
M=int(date0[1])
date1=input().rstrip().split(" ")
list0=[]
for i in range(N):
    list0.append(0)
for j in range(M):
    date=input().rstrip().split(" ")
    A=int(date[0])
    B=int(date[1])
    if int(date1[A-1])==int(date1[B-1]):
        list0[A-1]=1
        list0[B-1]=1
    elif int(date1[A-1])>int(date1[B-1]):
        list0[B-1]=1
    else:
        list0[A-1]=1
print(list0.count(0))

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 ] = a
  elif H[ a - 1 ] < H[ b - 1 ]:
    L[ a - 1 ] = b
  else:
    L[ b - 1 ] = a
    L[ a - 1 ] = b
    

cnt = 0
for i in L:
  if i < 0:
    cnt += 1
print( cnt )

Submission status: Accepted

Solution code:
from collections import defaultdict


n, m = map(int, input().split())
h = list(map(int, input().split()))
e = [list(map(int, input().split())) for _ in range(m)]

graph = defaultdict(list)

for dep, dest in e:
    graph[dep].append(dest)
    graph[dest].append(dep)

cnt = 0
for node in range(1, n+1):
    if graph[node]:
        flag = True
        for v in graph[node]:
            if h[node-1] <= h[v-1]:
                flag = False
                break
        if flag:
            cnt += 1
    else:
        cnt += 1

print(cnt)

Submission status: Accepted

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

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

to = [[] for i in range(N)]

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

    to[A-1].append(B-1)
    to[B-1].append(A-1)

ans = 0
for i in range(N):
    flg = True
    if len(to[i]) == 0:
        ans += 1
        continue
    else:
        for j in to[i]:
            if H[j] >= H[i]:
                flg = False

        if flg:
            ans += 1

print(ans)

Submission status: Accepted

Solution code:
from collections import Counter
N, M = map(int, input().split())
H = list(map(int, input().split()))
AB = [list(map(int, input().split())) for _ in range(M)]

check = [True]*N
for A, B in AB:
    A_H = H[A-1]
    B_H = H[B-1]
    if A_H > B_H:
        check[B-1] = False
    elif A_H < B_H:
        check[A-1] = False
    else:
        check[A-1] = False
        check[B-1] = False

print(Counter(check)[True])

Submission status: Accepted

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

route = [[] for i in range(N+1)]

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

count = 0
for i in range(1, N+1):
  route1 = route[i]
  flag = True
  for route2 in route1:
    if H[i-1] <= H[route2-1]:
      flag = False
  if flag:
    count += 1
#print(route)
print(count)

Submission status: Accepted

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

tmp = [0 for _ in range(N)]
for i in range(M):
  if H[Q[i][0]-1] >= H[Q[i][1]-1]:
    tmp[Q[i][1]-1] = -1
  if H[Q[i][0]-1]<= H[Q[i][1]-1]:
    tmp[Q[i][0]-1] = -1

print(N + sum(tmp))

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())
    if h[a-1] < h[b-1]:
        ans[a-1] = 0
    elif h[a-1] > h[b-1]:
        ans[b-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()))
G = [[] for _ in range(N)]
for _ in range(M):
  a, b = map(int, input().split())
  a, b = a-1, b-1
  G[a].append(b)
  G[b].append(a)

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

print(ans)

Submission status: Accepted

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

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:
import sys
import math
from collections import Counter
import itertools
import fractions
#from functools import reduce

# 入力を整数に変換して受け取る
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def MI1(): return map(int1, sys.stdin.readline().split())
# 入力全てを整数に変換したものの配列を受け取る
def LI(): return list(map(int, sys.stdin.readline().split()))
# 入力全てを整数に変換して1引いたものの配列を受け取る
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SR(): return sys.stdin.readline().rstrip()

ascii_lowercase = 'abcdefghijklmnopqrstuvwxyz'
ascii_uppercase = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
ascii_uppercase2 = 'ABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRSTUVWXYZ'

# リストを改行区切りで出力する
p2D = lambda x: print(*x, sep="\n")
p2E = lambda x: print(''.join(x))
p2S = lambda x: print(*x, sep=" ")

# ###########################################
 
N,M=MI()
H=LI()
A=LLI(M)

ansList=[0]*N
for i in range(N):
    ansList[i] = True

for a in A:
    if H[a[0]-1] > H[a[1]-1]:
        ansList[a[1]-1] = False
    elif H[a[0]-1] == H[a[1]-1]:
        ansList[a[1]-1] = False
        ansList[a[0]-1] = False
    else:
        ansList[a[0]-1] = False

print(ansList.count(True))

Submission status: Accepted

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

ans=0
lis=[1 for _ in range(n)]

for i in range(len(root)):
    a=root[i][0]
    b=root[i][1]
    if h[a-1] > h[b-1]:
        lis[b-1]=0
    elif h[a-1]< h[b-1]:
        lis[a-1]=0
    else:
        lis[a-1]=0
        lis[b-1]=0

ans=sum(lis)
print(ans)

Submission status: Accepted

Solution code:
def solve(n, m, h_list, ab_list):

    t_dict = {i:[] for i in range(1,n+1)}
    for a, b in ab_list:
        t_dict[a].append(b)
        t_dict[b].append(a)
    
    ans = 0
    for k, v in t_dict.items():
        th = h_list[k-1]
        if len([x for x in v if h_list[x-1] >= th]) == 0:
           ans += 1

    return ans

    
if __name__ == "__main__":
    n, m = [int(i) for i in input().split()]
    h_list = [int(i) for i in input().split()]
    ab_list = [[int(j) for j in input().split()] for i in range(m)]
    print(solve(n,m,h_list, ab_list))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
H = list(map(int, input().split()))
D = {i: [] for i in range(N)}
for i in range(M):
    A, B = map(int, input().split())
    if H[A-1] > H[B-1]:
        D[B-1].append(A-1)
    elif H[A-1] < H[B-1]:
        D[A-1].append(B-1)
    elif H[A-1] == H[B-1]:
        D[B-1].append(A-1)
        D[A-1].append(B-1)
cnt = 0
for i in range(N):
    if D[i] == []:
        cnt += 1
print(cnt)

Submission status: Accepted

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

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

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

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

ans = 0

for i in range(n):
    flag = True
    for j in range(len(road[i])):
        if h[i] <= h[road[i][j]]:
            flag = False
            break
    if flag is True:
        ans += 1

print(ans)

Submission status: Accepted

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

import numpy as np
h_array = np.array(list(map(int, input().split())))
# print(h_array)

p_dict = {i:[0] for i in range(n)}
for i in range(m):
  a, b = map(int, input().split())
  a, b = a-1, b-1
  p_dict[a].append(h_array[b])
  p_dict[b].append(h_array[a])
  
# print(p_dict)
num_good = 0
for i in range(n):
#   print(i, p_dict[i] , h_array[i])
  if max(p_dict[i]) < h_array[i]:
    num_good += 1

print(num_good)

Submission status: Accepted

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

a, b = [], []

for i in range(m):
    aa, bb = map(int, input().split())
    a.append(aa)
    b.append(bb)

res = [0] * n

for i in range(m):
    if h[a[i]-1] > h[b[i]-1]:
        res[b[i]-1] = -1
    elif h[a[i]-1] < h[b[i]-1]:
        res[a[i]-1] = -1
    else:
        res[b[i]-1] = -1
        res[a[i]-1] = -1

count = 0

for i in range(len(res)):
    if res[i] == 0:
        count += 1

print(count)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n, m = list(map(int, input().split(" ")))
h_list = list(map(int, input().split(" ")))
t = [[0] for _ in range(n)]
for i in range(m):
    a, b = list(map(int, input().split(" ")))
    t[a - 1].append(h_list[b - 1])
    t[b - 1].append(h_list[a - 1])
cnt = 0
for h, others in zip(h_list, t):
   if h > max(others):
       cnt += 1
print(cnt)

Submission status: Accepted

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


def main():
    N, M = map(int, input().split())
    H = list(map(int, input().split()))
    road = []

    for m in range(M):
        road.append(list(map(int, input().split())))
    
    ans = [True]*N

    for r in road:
        if H[r[0]-1] > H[r[1]-1]:
            ans[r[1]-1] = False
        elif H[r[0]-1] < H[r[1]-1]:
            ans[r[0]-1] = False
        else:
            ans[r[0]-1] = False
            ans[r[1]-1] = False
    
    print(sum(ans))


if __name__ == '__main__':
    main()

Submission status: Accepted

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

for j in range(m):
  a, b = map(int, input().split())
  if h[a-1] <= h[b-1]:
    data[a-1] = 0
  if h[a-1] >= h[b-1]:
    data[b-1] = 0

result = 0

for i in data:
  if i == 1:
    result += 1

print(result)

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def S(): return input().rstrip()
def LS(): return S().split()
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float("INF")

#solve
def solve():
    n, m = LI()
    h = LI()
    ab = LIR_(m)
    ans = [1] * n
    for a, b in ab:
        if h[a] < h[b]:
            ans[a] = 0
        if h[b] < h[a]:
            ans[b] = 0
        if h[b] == h[a]:
            ans[a] = 0
            ans[b] = 0
    print(sum(ans))
    return


#main
if __name__ == '__main__':
    solve()

Submission status: Accepted

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

tembo = [True]*n

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

print(tembo.count(True))

Submission status: Accepted

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

# class UnionFind():
#     def __init__(self, n):
#         self.parents = [-1] * n

#     def find(self, x):
#         if self.parents[x] < 0:
#             return x
#         else:
#             self.parents[x] = self.find(self.parents[x])
#             return self.parents[x]

#     def union(self, x, y):
#         x = self.find(x)
#         y = self.find(y)

#         if x == y:
#             return

#         if self.parents[x] > self.parents[y]:
#             x, y = y, x

#         self.parents[x] += self.parents[y]
#         self.parents[y] = x

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

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

for a, b in ab:
    memo[a-1] = max(memo[a-1], h[b-1])
    memo[b-1] = max(memo[b-1], h[a-1])

ans = 0
for memoi, hi in zip(memo, h):
    if hi > memoi:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
H = list(map(int, input().split()))
P = [1] * N
ans = N
for i in range(M):
    a, b = map(int, input().split())
    h_a = H[a - 1]
    h_b = H[b - 1]
    if ((h_a > h_b) and (P[b - 1] == 1)):
        ans = ans - 1
        P[b - 1] = 0
    elif ((h_b > h_a) and (P[a - 1] == 1)):
        ans = ans - 1
        P[a - 1] = 0
    elif (h_a == h_b):
        if (P[a - 1] == 1):
            ans = ans - 1
            P[a - 1] =  0
        if (P[b - 1] == 1):
            ans = ans - 1
            P[b - 1] =  0
print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8

N, M = map(int,input().split())
H = list(map(int,input().split()))
flg = [True] * (N+1)

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

ans = 0
#print(flg)
for i in flg:
    if i:
        ans += 1
ans -= 1
print(ans)

Submission status: Accepted

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

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

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

ans=sum(S)

print(ans)

Submission status: Accepted

Solution code:
import heapq

N, M = map(int, input().split())
H = [int(h) for h in input().split()]
AB = [tuple(map(int, input().split())) for _ in range(M)]

neighbor_heights = [[] for _ in range(N)]
for i in range(N):
    heapq.heapify(neighbor_heights[i])

for a, b in AB:
    heapq.heappush(neighbor_heights[a - 1], -H[b - 1])
    heapq.heappush(neighbor_heights[b - 1], -H[a - 1])

good = 0
for i, a in enumerate(neighbor_heights):
    if len(a) == 0 or H[i] > -heapq.heappop(a):
        good += 1

print(good)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
H = list(map(int, input().split()))
loser = set()
for _ in range(M):
    A, B = map(int, input().split())
    if H[A-1] > H[B-1]:
        loser.add(B)
    elif H[A-1] < H[B-1]:
        loser.add(A)
    else:
        loser.add(A)
        loser.add(B)
print(N - len(loser))

Submission status: Accepted

Solution code:
n,m=[int(_) for _ in input().split()]
h=[int(_) for _ in input().split()]
p=[[int(_)-1 for _ in input().split()] for __ in range(m)]
f=[1 for _ in range(n)]
for i in range(m):
    if h[p[i][0]]>h[p[i][1]]:
        f[p[i][1]]=0
    elif h[p[i][0]]<h[p[i][1]]:
        f[p[i][0]]=0
    else:
        f[p[i][0]]=0
        f[p[i][1]]=0
print(f.count(1))

Submission status: Accepted

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

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

adjacent_heights = {i:[0] for i in range(H)}

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

is_good = [1 if heights[i] > max(adjacent_heights[i]) else 0 for i in range(H)]

print(sum(is_good))

Submission status: Accepted

Solution code:
# input
N, M = map( int, input().split() )
H    = [ int(x) for x in input().split() ]
L    = dict()
for nn in range( N ):
    L[nn+1] = list()

for mm in range( M ):
    Am, Bm = map( int, input().split() )
    L[Am].append( Bm )
    L[Bm].append( Am )
            
##
ans = 0
for ii in range( N ):
    if( len(L[ii+1]) == 0 ):
        ans += 1
    else:
        Hi   = H[ii]
        flag = True
        for jj in range( len(L[ii+1]) ):
            if( Hi <= H[ L[ii+1][jj]-1 ] ):
                flag = False
        if(flag):
            ans += 1
            
print(ans)

Submission status: Accepted

Solution code:
import sys
import numpy as np

#n=int(sys.stdin.readline())
n,m=map(int,sys.stdin.readline().split())
h=np.array(sys.stdin.readline().split(),dtype='int64')

l=[1]*n

for _ in range(m):
    a,b=map(int,sys.stdin.readline().split())
    if h[a-1]<h[b-1]:
        l[a-1]=0
    elif h[b-1]<h[a-1]:
        l[b-1]=0
    else:
        l[a-1]=0
        l[b-1]=0
cnt=0
for i in range(n):
    if l[i]==1:
        cnt+=1
print(cnt)

Submission status: Accepted

Solution code:
import bisect
import copy
import heapq
import sys
import itertools
import math
import queue
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
mod = 10 ** 9 + 7

def read_values(): return map(int, input().split())
def read_index(): return map(lambda x: int(x) - 1, input().split())
def read_list(): return list(read_values())
def read_lists(N): return [read_list() for n in range(N)]
def init_dp1(init, N): return [init for _ in range(N)]
def init_dp2(init, N, M): return [[init for _ in range(M)] for _ in range(N)]


class V:
    def __init__(self, f, v=None):
        self.f = f
        self.v = v
 
    def __str__(self):
        return str(self.v)
 
    def ud(self, n):
        if n is None:
            return

        if self.v is None:
            self.v = n
            return
        self.v = self.f(self.v, n) 


def main():
    N, M = read_values()
    H = read_list()

    F = [True] * N
    for _ in range(M):
        A, B = read_index()
        if H[A] >= H[B]:
            F[B] = False
        if H[A] <= H[B]:
            F[A] = False

    print(F.count(True))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def m():
    N, M = map(int, input().split())
    H = list(map(int, input().split()))
    graph = [[] for _ in range(N + 1)]
    for _ in range(M):
        a, b = map(int, input().split())
        graph[a].append(b)
        graph[b].append(a)
    ans = 0
    for i in range(1, N+1):
        current = H[i-1]
        p = 1
        for x in graph[i]:
            if current <= H[x-1]:
                p = 0
                break
        ans += p
    return ans


print(m())

Submission status: Accepted

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

# print(cnt)
ans = 0
for i in range(1,n+1):
    if cnt[i] == 0:
        ans += 1
print(ans)

Submission status: Accepted

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

A=[0]*M
B=[0]*M

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

for i in range(M):
    if H[A[i]-1]>=H[B[i]-1]:
        flags[B[i]-1] = 0
    if H[B[i]-1]>=H[A[i]-1]:
        flags[A[i]-1] = 0    
print(sum(flags))

Submission status: Accepted

Solution code:
def main():
    n, m = map(int, input().split())
    *h, = map(int, input().split())
    l = [True for _ in range(n)]
    for _ in range(m):
        a, b = map(int, input().split())
        if h[a - 1] == h[b - 1]:
            l[a - 1] = False
            l[b - 1] = False
        elif h[a - 1] > h[b - 1]:
            l[b - 1] = False
        else:
            l[a - 1] = False
    ans = sum(l)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
import itertools
if sys.platform =='ios':
    sys.stdin=open('input_file.txt')
    
n,m=map(int,input().split())

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

p=[1]*n

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

Submission status: Accepted

Solution code:
import heapq

N,M = map(int, raw_input().split())
H = map(int, raw_input().split())
Height = {i+1:h for i,h in enumerate(H)}

G = {i+1:[] for i in range(N)}
for _ in range(M):
    a,b = map(int, raw_input().split())
    heapq.heappush(G[a], (-Height[b], b))
    heapq.heappush(G[b], (-Height[a], a))

# print G

ans = 0
for h,hs in G.items():
    if len(hs) == 0:
        ans += 1
        continue
    maxh = -heapq.heappop(hs)[0]
    if Height[h] > maxh:
        ans += 1

print ans

Submission status: Accepted

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

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

for j in range(n):
    if len(li[j])==0:
        ans+=1
    elif h[j]>max(li[j]):
        ans+=1

print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
n, m = map(int, input().split())
H = list(map(int, input().split()))
edges = [[] for _ in range(n)]
for _ in range(m):
    a, b = list(map(lambda x: int(x)-1, input().split()))
    edges[a].append(b)
    edges[b].append(a)


ans = [0]*n


def dfs(v, parent):
    if visited[v]:
        return 0
    visited[v] = 1
    if not edges[v]:
        ans[v] = 1
    elif all(H[v2] < H[v] for v2 in edges[v]):
        ans[v] = 1
    for v2 in edges[v]:
        if v2 == parent:
            continue
        dfs(v2, v)


visited = [0]*n

for v in range(n):
    if visited[v]:
        continue
    dfs(v, -1)

print(sum(ans))

Submission status: Accepted

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

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

active = [True] * N

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

print(len(list(filter(lambda x:x, active))))

Submission status: Accepted

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

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

for j in range(len(ab_list)):
    index_from = ab_list[j][0]
    index_to = ab_list[j][1]
    if h_list[index_from - 1] < h_list[index_to - 1]:
        count_list[index_from - 1] += 1
    elif h_list[index_from - 1] > h_list[index_to - 1]:
        count_list[index_to - 1] += 1
    else:
        count_list[index_from - 1] += 1
        count_list[index_to - 1] += 1

print(count_list.count(0))

Submission status: Accepted

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

Submission status: Accepted

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

from collections import defaultdict
group = defaultdict(int)
for i in range(m):
  a,b = map(int, input().split())
  if h[a-1] > h[b-1]:
    group[b-1] = 1
  elif h[a-1] == h[b-1]:
    group[a-1] = 1
    group[b-1] = 1
  else:
    group[a-1] = 1
cnt = 0
for i in range(n):
  if group[i] == 0:
    cnt += 1
print(cnt)

Submission status: Accepted

Solution code:
p=0
n,m=map(int,input().split())
d = {i:[] for i in range(n)}
h=list(map(int,input().split()))
for i in range(m):
    a,b=map(int,input().split())
    d[a-1].append(b-1)
    d[b-1].append(a-1)
#print(d)
for i,j in d.items():
    hi=h[i]
    if set([hi-h[k]>0 for k in j])==set([True]):
        p+=1
    elif j==[]:
        p+=1
print(p)

Submission status: Accepted

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

s = l = [n-1] * n
cnt = 0

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

for i in range(n):
    if s[i] == n-1:
        cnt = cnt + 1 

print(cnt)

Submission status: Accepted

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

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

# 展望台から行ける展望台の高さを格納しておく
from collections import defaultdict
d = defaultdict(int)
for i in range(M):
  A,B = list(map(int,input().split()))
  A -= 1
  B -= 1
  if d[A] < H[B]:
    d[A] = H[B]
  if d[B] < H[A]:
    d[B] = H[A]
cnt = 0
for idx,h in enumerate(H):
  if d[idx] == 0 or h > d[idx]:
    cnt += 1
else:
  print(cnt)

Submission status: Accepted

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

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

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

edge = [[] for i in range(n)]

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


for i in range(n):
    flag = True
    for e in edge[i]:
        if h[i] <= h[e]:
            flag = False
    if flag:
        res += 1
print(res)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
Hs = list(map(int, input().split()))
As = [list(map(int, input().split())) for _ in range(M)]
rlt = [1]*N

for a in As:
  if Hs[a[0]-1] < Hs[a[1]-1]:
    rlt[a[0]-1] = 0
  elif Hs[a[0]-1] > Hs[a[1]-1]:
    rlt[a[1]-1] = 0
  else:
    rlt[a[0]-1] = 0
    rlt[a[1]-1] = 0
    
print(sum(rlt))