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=list(map(int,input().split()))
H=list(map(int,input().split()))
ans=0
Road=[[] for _ in range(n)]
for i in range(m):
  a,b=list(map(int,input().split()))
  Road[a-1].append(b)
  Road[b-1].append(a)

for i,R in enumerate(Road):
  count=0
  for j in range(len(R)):
    if H[i] <= H[R[j]-1]:
      break
    count += 1
  if count == len(R):
    ans+=1
print(ans)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
b=list(map(int, input().split()))
h = {i: b for i, b in enumerate(b)}


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

d=set()
# ans=0
# a=[1 for i in range(n)]

for i in range(m):
    if h[ab[i][0]-1]<h[ab[i][1]-1]:
        d.add(ab[i][0]-1)
    elif h[ab[i][0]-1]>h[ab[i][1]-1]:
        d.add(ab[i][1]-1)
    elif h[ab[i][0]-1]==h[ab[i][1]-1]:
        d.add(ab[i][0]-1)
        d.add(ab[i][1]-1)
#


# print(h[ab[0][0]-1])
# #
print(n-len(d))

Submission status: Accepted

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

def main():
    N, M = map(int, input().split())
    H = dict(zip(range(1, N + 1), map(int, input().split())))
    m = dict(zip(range(1, N + 1), [[0] for _ in range(N)]))
    for _ in range(M):
        A, B = map(int, input().split())
        m[A].append(H[B])
        m[B].append(H[A])
    c = 0
    for k, v in m.items():
        if H[k] > max(v):
            c += 1
    print(c)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import collections
from collections import defaultdict
def bfs(graph, root):
    count=0
    queue=collections.deque([root])
    visited.add(root)
    while queue:
        vertex=queue.popleft()
        ok=True
        for neighbour in graph[vertex]:
            if h[neighbour-1]>=h[vertex-1]:
                ok=False
            if neighbour not in visited:
                visited.add(neighbour)
                queue.append(neighbour)
            
        if ok==True:
            count+=1
            #print(count,vertex)
    return(count)
n,m=map(int,input().split())
h=[int(i) for i in input().split()]
graph=defaultdict(list)
seta=set()
for i in range(m):
    a,b=map(int,input().split())
    seta.add(a)
    seta.add(b)
    graph[a].append(b)
    graph[b].append(a)

visited=set()
ans=0
for i in range(1,n+1):
    #print(visited,i)
    if i not in visited:
        ans+=bfs(graph,i)
        #print(ans)
print(ans)

Submission status: Accepted

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

#n = int(input())
#l = list(map(int, input().split()))

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

n, m = map(int, input().split())
h = list(map(int, input().split()))
ok = [True for i in range(n)]

for i in range(m):
    p = list(map(int, input().split()))
    if h[p[0]-1]<h[p[1]-1]:
        ok[p[0]-1]=False
    elif h[p[0]-1] > h[p[1]-1]:
        ok[p[1]-1] = False
    elif h[p[0]-1] == h[p[1]-1]:
        ok[p[1]-1] = False
        ok[p[0]-1] = False
cnt=0
for i in range(len(ok)):
    if ok[i]==True:
        cnt+=1
#print(ok)
print(cnt)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
hlist = list(map(int, input().split()))
rlist=[]
i=0
while(i<M):
  a = input().split()
  rlist.append(a)
  i+=1
anslist=[0]*N
j=0
while(j<M):
  alist=rlist[j]
  a=int(alist[0])
  b=int(alist[1])
  if(hlist[a-1]<hlist[b-1]):
    anslist[a-1]=1
  elif(hlist[b-1]<hlist[a-1]):
    anslist[b-1]=1
  elif(hlist[a-1]==hlist[b-1]):
    anslist[a-1]=1
    anslist[b-1]=1
  j+=1
print(anslist.count(0))

Submission status: Accepted

Solution code:
import numpy as np

n, m = map(int, input().split())
h = np.array(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)

good_observatories = [-1] * n
sort_idx = np.argsort(-h)
for i, idx in enumerate(sort_idx):
    if good_observatories[idx] == -1:
        if all([h[idx] > h[v] for v in g[idx]]):
            good_observatories[idx] = 1
            for v in g[idx]:
                good_observatories[v] = 0
print(good_observatories.count(1))

Submission status: Accepted

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

ab = [map(int,input().split()) for _ in range(m)]
a,b = [list(i) for i in zip(*ab)]

ans=[]

for i in range(n):
    ans.append(1)

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


count=0
for i in range(n):
    if ans[i]==1:
        count=count+1

print(count)

Submission status: Accepted

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

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

for i in range(n):
    if cnt[i] == chk[i]:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
from collections import Counter
N, M = map(int, input().split())
H=[int(x) for x in input().split()]
list=[]
for i in range (1,M+1):
  a, b = map(int, input().split())
  if H[a-1] > H[b-1]:
    list.append(b)
  elif  H[a-1] < H[b-1]:
    list.append(a)
  elif  H[a-1] == H[b-1]:
    list.append(a)
    list.append(b)
c = Counter(list)
print(N-len(c))

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)]
Alist = [1]*N
for i in range(M):
    if H[AB[i][0]-1] >= H[AB[i][1]-1]:
        Alist[AB[i][1]-1] = 0
    if H[AB[i][0]-1] <= H[AB[i][1]-1]:
        Alist[AB[i][0]-1] = 0
print(Alist.count(1))

Submission status: Accepted

Solution code:
N, M = (int(x) for x in input().split())
H = [int(x) for x in input().split()]
#AB = []
Nn = []
for i in range(1,N+1):
  Nn.append(i)
for i in range(M):
  A,B = (int(x) for x in input().split())
  if H[A-1] == H[B-1]:
      Nn[A-1] = 0
      Nn[B-1] = 0
  elif H[A-1] > H[B-1]:
      Nn[B-1] = 0
  else:
      Nn[A-1] = 0
n = set(Nn)
n.remove(0)
print(len(n))

Submission status: Accepted

Solution code:
import heapq

N, M = [int(i) for i in input().split()]
H = [int(i) for i in input().split()]

NG = []

for i in range(M):
  a, b = [int(j) for j in input().split()]
  if H[a-1] < H[b-1]:
    NG.append(a)
  elif H[a-1] > H[b-1]:
    NG.append(b)
  else:
    NG.append(a)
    NG.append(b)
NG = set(NG)
#print(NG)
print(N - len(NG))

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

res = [set() for _ in range(n)]

for i,j in a:
    res[i-1].add(j-1)
    res[j-1].add(i-1)
ans = 0
res = [j if j != set() else set([i]) for i,j in enumerate(res)]
for i in range(n):
    for j in res[i]:
        if i == j:
            ans += 1
            break
        if h[i] <= h[j]:
            break
    else:
        ans += 1
print(ans)

Submission status: Accepted

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

f = [0] * 10 ** 5
c = {}
for i in range(m):
    a, b = map(int, input().split())
    if b < a:
        a, b = b, a
    if a not in c:
        c[a] = [b]
    else:
        c[a].append(b)


for k, v in c.items():

    for i in v:
        if h[k-1] < h[i-1]:
            f[k-1] = 1
        elif h[k-1] > h[i-1]:
            f[i-1] = 1
        else:
            f[k-1] = 1
            f[i-1] = 1

ans = 0
for i in range(n):
    if f[i] == 0:
        ans += 1

print(ans)

Submission status: Accepted

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

cnt = 0
d = {}
for i in range(n):
    d[i] = 1
for i in range(m):
    if h[a[i]-1] > h[b[i]-1]:
        d[b[i]-1] = 0
    elif h[a[i]-1] < h[b[i]-1]:
        d[a[i]-1] = 0
    else:
        d[a[i]-1] = 0
        d[b[i]-1] = 0

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

print(cnt)

Submission status: Accepted

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

s=0
for x in range(1,n+1):
    if A[x]==[]:s+=1
    else:
        f=True
        for y in A[x]:
            if h[x-1]<=h[y-1]:f=False
        if f==True:s+=1
print(s)

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
H=list(map(int,input().split()))
S=set()
for i in range(N):
  S.add(i+1)
for i in range(M):
  A,B=map(int, input().split())
  if H[A-1]>H[B-1] and B in S:
    S.remove(B)
  if H[A-1]<H[B-1] and A in S:
    S.remove(A)
  if H[A-1]==H[B-1]:
    if A in S:
      S.remove(A)
    if B in S:
      S.remove(B)
print(len(S))

Submission status: Accepted

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

c = []
d = []
g = []
s = [1]*n

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

g = c + d
g.sort()

for j in range(2*m):
    k = g[j][0]-1
    l = g[j][1]-1
    if h[k] <= h[l]:
        s[k] = 0

x = s.count(1)
print(x)

Submission status: Accepted

Solution code:
# import numpy as np
# import collections

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

ab = []
#not_f = []
for i in range(m):
    a,b = map(int,input().split())
    ab.append(sorted([a,b]))
    #not_f = not_f + [a,b]

# c = collections.Counter(not_f)   #m*2要素
# c = sorted(c.items(), key=lambda x:x[1])

# count = 0
# for j in c:
#     if j[1] == 0:
#         count += 1
#     else:
#         break

ans = 0

# height_rank = np.zeros(n)

make = []

for i in ab:
    if h[i[0]-1] < h[i[1]-1]:
        #height_rank[i[1]-1] +=  1
        #height_rank.pop(i[0]-1)
        #np.delete(height_rank,i[0]-1,axis = 1)
        make.append(i[0])
    elif h[i[0]-1] > h[i[1]-1]:
        make.append(i[1])
        #height_rank[i[0]-1] +=  1
        #height_rank.pop(i[1]-1)
        #np.delete(height_rank,i[1]-1,axis = 1)

    elif h[i[0]-1] == h[i[1]-1]:
        make.append(i[0])
        make.append(i[1])
        # height_rank.pop(i[0]-1)
        # height_rank.pop(i[1]-1)
        #np.delete(height_rank,i[0]-1,axis = 1)
        #np.delete(height_rank,i[1]-1,axis = 1)

ans = n - len(set(make))
print(ans)

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
H=list(map(int,input().split()))
ls=[list(map(int,input().split())) for _ in range(M)]#1から
C=[0 for _ in range(N)]
for i in range(M):#O(M)でいけるはず
  if H[ls[i][0]-1]>H[ls[i][1]-1]:
    C[ls[i][1]-1]=-1
  elif H[ls[i][0]-1]<H[ls[i][1]-1]:
    C[ls[i][0]-1]=-1
  elif H[ls[i][0]-1]==H[ls[i][1]-1]:
    C[ls[i][0]-1]=-1
    C[ls[i][1]-1]=-1
print(C.count(0))

Submission status: Accepted

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

    me = B[i]-1
    t = A[i]-1
    if H[me] <= H[t]:
        G[me] = 0
print(G.count(1))

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
ListH = list(map(int, input().split()))
ListAB = [list(map(int, input().split())) for i in range(M)]

Cnt=[0]*N

for i in range(M):
  if ListH[ListAB[i][0]-1]==ListH[ListAB[i][1]-1]:
    Cnt[ListAB[i][0]-1] = 1
    Cnt[ListAB[i][1]-1] = 1  
  else :
    if ListH[ListAB[i][0]-1] > ListH[ListAB[i][1]-1]:
      Cnt[ListAB[i][1]-1]=1
    if ListH[ListAB[i][0]-1] < ListH[ListAB[i][1]-1]:
      Cnt[ListAB[i][0]-1]=1

print(Cnt.count(0))

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
hyoko = list(map(int, input().split()))
result = {}

for i in range(1, n+1):
    result[i] = result.get(i, set())

for i in range(0, m):
    michi = list(map(int, input().split()))
    result[michi[0]].add(michi[1])
    result[michi[1]].add(michi[0])

count = 0

for key, value in result.items():
    flg = 0
    if len(value) == 0:
        count += 1
        continue
    for i in value:
        if hyoko[key-1] <= hyoko[i-1]:
            flg = 1
    
    if flg == 0:
        count += 1
        
print(count)

Submission status: Accepted

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

not_good = []
for i in range(m):
    a,b = list(map(int,input().split()))
    if h[a-1] <= h[b-1]:
        not_good.append(a)
    if h[a-1] >= h[b-1]:
        not_good.append(b)
print(n-len(set(not_good)))

Submission status: Accepted

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

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

H3 = H2.count(False)

print(len(H) - H3)

Submission status: Accepted

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

ans = [0] * N
for i in range(M):
    if H[AB[i][0]-1] > H[AB[i][1]-1]:
        ans[AB[i][1]-1] += 1
    if H[AB[i][0]-1] < H[AB[i][1]-1]:
        ans[AB[i][0]-1] += 1
    if H[AB[i][0]-1] == H[AB[i][1]-1]:
        ans[AB[i][0]-1] += 1
        ans[AB[i][1]-1] += 1
print(ans.count(0))

Submission status: Accepted

Solution code:
s = list(map(int,input().split()))
n=s[0]
m=s[1]
h = list(map(int, input().split()))
p={}
for i in range(n+1):
    p[i]=0
for i in range(m):
    s = list(map(int, input().split()))
    if p[s[0]]==0:
        p[s[0]]=1
    if p[s[1]]==0:
        p[s[1]]=1
    if h[s[0]-1]>h[s[1]-1] and p[s[0]]!=3:
        p[s[0]]=2
    else:
        p[s[0]] = 3
    if h[s[0]-1] < h[s[1]-1] and p[s[1]] != 3:
        p[s[1]] = 2
    else:
        p[s[1]] = 3
ans=-1
for i in p:
    if p[i]==0 or p[i]==2:
        ans+=1
print(ans)

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
H = list(map(int,input().split()))
AB = []
ans = 0

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

AB = sorted(AB)
    
import collections
que = collections.deque()

for i in AB:
    que.append(i)

for i in range(n):
    compare = []
    
    while que:
        if que[0][0] == i:
            ab = que.popleft()
        else:
            break
            
        if ab[0] == i:
            compare.append(H[ab[1]])
    
    c = len(compare)
    
    if c > 0 and H[i] > max(compare):
        ans += 1
    
    if c == 0:
        ans += 1
        
print(ans)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
l = [1] * N
A = list(map(int, input().split()))

for i in range(K):
  R = list(map(int, input().split()))
  if A[R[0]-1]==A[R[1]-1]:
    l[R[0]-1]=0
    l[R[1]-1]=0
  elif A[R[0]-1]>A[R[1]-1]:
    l[R[1]-1]=0
  else:
    l[R[0]-1]=0
  
print(sum(l))

Submission status: Accepted

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

# 10**5回
for m in range(M):
    MICHI.append(tuple(map(int, input().split(' '))))

# 展望台接続関係マップ
# setsuzokumap = [[0 for i in range(N)] for j in range(N)]
setsuzokumap_d = {}
setsuzokumap_me = [[] for j in range(N)]

# 10**5回
for m in MICHI:
    # setsuzokumap[m[0] - 1][m[1] - 1] = 1
    # k = (m[0] - 1, m[1] - 1)

    setsuzokumap_me[m[0] - 1].append(m[1] - 1)
    setsuzokumap_me[m[1] - 1].append(m[0] - 1)

    # setsuzokumap_d.update({k: 1})

# print(setsuzokumap_d)

good_tenboudai = [None] * N

# すべての展望台を調べる
# 10**5
for n in range(N):
    # 未判断の展望台を調べる
    if good_tenboudai[n] is None:
        # すべての接続パターンを調べる
        if setsuzokumap_me[n]:
            # 最大10**5
            for setsuzokusaki in setsuzokumap_me[n]:

                m = setsuzokusaki

                # 接続先が良い展望台ならば、この展望台は自動的によくない
                if good_tenboudai[m] == 1:
                    good_tenboudai[n] = 0
                else:
                    # 接続先の高さが自分以下だったら接続先は必ずよくない
                    if H[m] <= H[n]:
                        good_tenboudai[m] = 0

                    # 自分の高さが接続先以下だったらよくない
                    if H[n] <= H[m]:
                        good_tenboudai[n] = 0


# 最後まで良くないと判定されなかったのが良いの
# 10**5
for n in range(N):
    if good_tenboudai[n] is None:
        good_tenboudai[n] = 1

# print(good_tenboudai)
print(sum(good_tenboudai))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
import os

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

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

#print(h)
#print(ab)

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

#1つの展望台から行ける展望台を全部書く
for j in range(m):
    a,b = ab[j]

    tenbo[a-1].append(h[b-1])
    tenbo[b-1].append(h[a-1])

#print(tenbo)

#各展望台を検索
kazu = 0
for i in range(n):
    
    if len(tenbo[i]) == 0:
        kazu += 1
        #print("Y", h[i], tenbo[i], 0)
    elif h[i] > max(tenbo[i]):
        kazu += 1
        #print("Y", h[i], tenbo[i], max(tenbo[i]))

print(kazu)

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
h = list(map(int,input().split()))
load = {x : [] for x in range(1,n+1)}
ans = h[:]
cnt = 0
for i in range(m):
    a,b = map(int,input().split())
    if b in load[a]:
        pass
    else:
        load[a].append(b)
        load[b].append(a)
        if ans[a - 1] == 0:
            pass
        else:
            if h[a-1] > h[b-1]:
                pass
            else:
                ans[a-1] = 0
                
        if ans[b - 1] == 0:
            pass
        else:
            if h[b-1] > h[a-1]:
                    pass
            else:
                ans[b-1] = 0
                
                
for i in ans:
    if i:
        cnt += 1
print(cnt)

Submission status: Accepted

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

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

ans = N

# print(H)
# print(R)

for i in range(1,N+1):
  for j in R[i]:
    if H[i] <= H[j]:
      ans = ans - 1
      break


print(ans)

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[A-1]=0
        L[B-1]=0
    elif H[A-1]>H[B-1]:
        L[B-1]=0
    else:
        L[A-1]=0
AAA=sum(L)
print(AAA)

Submission status: Accepted

Solution code:
(n, m) = tuple(map(int, input().split(" ")))
h = list(map(int, input().split(" ")))
l = [-1 for i in range(n)]
for i in range(m):
    (a, b) = tuple(map(int, input().split(" ")))
    if l[a - 1] < h[b - 1]:
        l[a - 1] = h[b - 1]
    if l[b - 1] < h[a - 1]:
        l[b - 1] = h[a - 1]
c = 0
for i in range(n):
    if l[i] == -1 or l[i] < h[i]:
        c += 1
print(c)

Submission status: Accepted

Solution code:
import queue
import copy
import math
from collections import deque
import bisect
from decimal import Decimal

# そのまま入力文字列の入力
n, m = map(int, input().split())

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

candidate = set()

for i in range(n):
    candidate.add(i + 1)

roads = []
# 空白区切りの数値をリスト化
for i in range(0, m):
    road = list(map(int, input().split()))
    roads.append(road)

exists_road = set()
lower = set()
ans_set = set()

for road in roads:
    h0 = heights[road[0] - 1]
    h1 = heights[road[1] - 1]

    exists_road.add(road[0])
    exists_road.add(road[1])

    if h0 > h1:
        ans_set.add(road[0])
        lower.add(road[1])

    elif h0 < h1:
        ans_set.add(road[1])
        lower.add(road[0])

    else:
        ans_set.add(road[0])
        lower.add(road[0])
        ans_set.add(road[1])
        lower.add(road[1])

unvisited = candidate - exists_road
heighest = ans_set - lower

print(len(unvisited) + len(heighest))

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=[i+1 for i in range(N)]
C=[]
for i in range(M):

    if(H[A[i]-1]>H[B[i]-1]):

        C.append(B[i])

    elif(H[A[i]-1]<H[B[i]-1]):

        C.append(A[i])
    else:

        C.append(A[i])
        C.append(B[i])

G=list(set(D)-set(C))
print(len(G))

Submission status: Accepted

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

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

A=[0]*NM[0]
for i in range (NM[1]):
    AB=list(map(int,input().split()))
    if Hlist[AB[0]-1]<=Hlist[AB[1]-1]:
        A[AB[0]-1]=1
    if Hlist[AB[1]-1]<=Hlist[AB[0]-1]:
        A[AB[1]-1]=1
ans=NM[0]-sum(A)
print(ans)

Submission status: Accepted

Solution code:
import sys
import math
from collections import deque

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

mydict = {}
for i in AB:
    if i[0] not in mydict:
        mydict[i[0]] =[i[1]]
    else:
        mydict[i[0]].append(i[1])

    if i[1] not in mydict:
        mydict[i[1]] =[i[0]]
    else:
        mydict[i[1]].append(i[0])


cnt = 0
for i in range(1,N+1):
    if i not in mydict.keys():
        cnt += 1
        continue

    top_flag = True
    for k in list(set(mydict[i])):
        if i == k:
            continue
        if H[i-1] <= H[k-1]:
            top_flag = False
            break
    if top_flag == True:
        cnt += 1

print(cnt)

Submission status: Accepted

Solution code:
N,M = map(int, input().split())
H = list(map(int, input().split()))
A = [ list(map(int,input().split(" "))) for i in range(M)]
C = []
for i in range(N):
	C.append(0)
for i in range(M):
	x = A[i][0]
	y = A[i][1]
	if H[x-1] > H[y-1]: 
		C[y-1] += -1
	elif H[x-1] < H[y-1]:
		C[x-1] += -1
	elif H[x-1] == H[y-1]:
		C[x-1] += -1
		C[y-1] += -1
print(C.count(0))

Submission status: Accepted

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

print(len(H))

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
H = list(map(int,input().split()))
memo = [[] for _ in range(N+1)]
for i in range(M):
    a,b = map(int,input().split())
    memo[a].append(b)
    memo[b].append(a)
    
count = 0
for i in range(1,N+1):
    mini = set(memo[i])
    if len(mini) > 0:
        for j in mini:
            if H[i-1] <= H[j-1]:
                break
        else:
            count += 1
    else:
        count += 1

print(count)

Submission status: Accepted

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

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

ans = 0
cnt = 0
for i in d:
    if i != []:
        cntF = True
        for j in i:
            if H[cnt] <= H[j]:
                cntF = False
                break
        if cntF:
            ans += 1
    else:
        ans += 1
    cnt += 1

print(ans)

Submission status: Accepted

Solution code:
# import numpy as np
# import queue
# import heapq



def main():
    N, M = map(int, input().split())
    heights = list(map(int, input().split()))
    towers = [True for _ in range(N)]

    pathes = (list(map(int, input().split())) for _ in range(M))

    for path in pathes:

        a = path[0] - 1
        b = path[1] - 1

        ha = heights[a]
        hb = heights[b]

        if ha > hb:
            towers[b] = False
        elif ha < hb:
            towers[a] = False
        else:
            towers[a] = False
            towers[b] = False

    print(sum(towers))


if __name__ == "__main__":
    main()

Submission status: Accepted

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


for d in range(0,M):
    if H[AB[d][0]-1] < H[AB[d][1]-1]:
        AB[d].pop(1)
    elif H[AB[d][0]-1] > H[AB[d][1]-1]:
        AB[d].pop(0)


bad = [e for row in AB for e in row]
badsingle = list(set(bad))
print(N - len(badsingle))

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

road_list = []
for _ in range(N):
    road_list.append([])
    
for i in range(M):
    a, b = list(map(int, input().split()))
    
    H_a, H_b = [H_list[a - 1], H_list[b - 1]]
    
    if H_a <= H_b:
        road_list[a - 1].append(b)

    if H_b <= H_a:
        road_list[b - 1].append(a)

ans = 0
for road in road_list:
    if len(road) == 0:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
import collections
n,m = (int(i) for i in input().split())
h = [int(i) for i in input().split()]
ab =[[0]]*n

for _ in range(m):
	a,b = (int(i) for i in input().split())
	if h[a-1]-h[b-1]>0:
		ab[b-1]=["a"]

	elif h[a-1]-h[b-1]<0:
		ab[a-1]=["a"]

	else:
		ab[a-1]=["a"]
		ab[b-1]=["a"]


print(ab.count([0]))

Submission status: Accepted

Solution code:
import numpy as np
n,m  = [int(k) for k in input().split()]
h = [int(k) for k in input().split()]
j = []
for i in range(n):
    j.append([-1])
r = 0
for i in range(m):
    a,b = [int(k) - 1 for k in input().split()]
    j[a].append(b)
    j[b].append(a)
for i in range(n):
    
    j[i] = list(set(j[i][1:]))
    is_good = False if not len(j) >= 1 else True
    for l in j[i]:
        if h[i] > h[l]:
            is_good = True
        else:
            is_good = False
            break
    if is_good:
        r += 1
print(r)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
H = list(map(int, input().split()))
K = [[] for i in range(n)]
for i in range(m):
    a, b = map(int, input().split())
    K[a - 1].append(H[b - 1])
    K[b - 1].append(H[a - 1])
ans = 0
for i, k in enumerate(K):
    if len(k) != 0 and H[i] > max(k):
        ans += 1
    elif len(k) == 0:
        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()]
nodes = [1 for i in range(N)]
for j in range(M):
    a, b = [int(x) for x in input().split()]
    if H[a - 1] <= H[b - 1]:
        nodes[a - 1] = 0
    if H[b - 1] <= H[a - 1]:
        nodes[b - 1] = 0
print(sum(nodes))

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())
    if h[A-1] < h[B-1]:
      l[A-1] +=1
    elif h[B-1] < h[A-1]:
      l[B-1] +=1
    else:
      l[A-1] +=1
      l[B-1] +=1
print(l.count(0))

Submission status: Accepted

Solution code:
number_of_observatory, number_of_road = map(int, input().split())
height_list = [0]  # 1始まりで合わせるため
height_list.extend(list(map(int, input().split())))

road_list = []
for i in range(number_of_road):
    li = list(map(int, input().split()))
    road_list.append(li)  # start・end の順に格納
counta = 0

not_good_list = []
# 良い展望台でない展望台をリストに詰める
for road in road_list:
    if height_list[road[0]] < height_list[road[1]]:
        not_good_list.append(road[0])
    elif height_list[road[0]] > height_list[road[1]]:
        not_good_list.append(road[1])
    else:
        not_good_list.extend(road)

not_good_set = set(not_good_list)
observatory_set = set(range(1, number_of_observatory+1))

print(len(observatory_set - not_good_set))

Submission status: Accepted

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


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

obvs = list(range(1,N+1,1))
obvs_height = list(map(int, input().split()))
#print(obvs)

obvs = {}
i = 1
for h in obvs_height:
    obvs[i] = h
    i += 1

obvs_remain = obvs.copy()

while True:
    path = list(map(int, input().strip().split()))
    if path==[]:
        break
    if obvs[path[0]] == obvs[path[1]]:
        obvs_remain.pop(path[0], None)
        obvs_remain.pop(path[1], None)
    elif obvs[path[0]] > obvs[path[1]]:
        obvs_remain.pop(path[1], None)
    elif obvs[path[0]] < obvs[path[1]]:
        obvs_remain.pop(path[0], None)

print(len(obvs_remain))

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
h = list(map(int,input().split()))  #hの要素はn個
#全て良い道にしておく
li = [1 for i in range(n)]

for i in range(m):
    a,b = map(int,input().split())
    if(h[a-1] < h[b-1]):
        li[a-1] = 0
    elif(h[b-1] < h[a-1]):
        li[b-1] = 0
    elif(h[a-1] == h[b-1]):
        li[a-1] = 0
        li[b-1] = 0
    
c=0
for i in range(len(li)):
    if(1 == li[i]):
        c += 1

print(c)

Submission status: Accepted

Solution code:
import copy
N,M=(int(x) for x in input().split())
H=[]
H.extend((int(x) for x in input().split()))
h=copy.copy(H)
for i in range(M):
    A,B=(int(x) for x in input().split())
    a=A-1
    b=B-1
    if H[a]<H[b]:
        h[a]=0
    elif H[a]>H[b]:
        h[b]=0
    else:
        h[a]=0
        h[b]=0
print(len([i for i in h if i!=0]))