Problem:


Score : 300 points

Problem Statement

There are N observatories in AtCoder Hill, called Obs. 1, Obs. 2, ..., Obs. N. The elevation of Obs. i is H_i.
There are also M roads, each connecting two different observatories. Road j connects Obs. A_j and Obs. B_j.

Obs. i is said to be good when its elevation is higher than those of all observatories that can be reached from Obs. i using just one road.
Note that Obs. i is also good when no observatory can be reached from Obs. i using just one road.

How many good observatories are there?

Constraints

2 \leq N \leq 10^5

1 \leq M \leq 10^5

1 \leq H_i \leq 10^9

1 \leq A_i,B_i \leq N

A_i \neq B_i

Multiple roads may connect the same pair of observatories.

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N M
H_1 H_2 ... H_N
A_1 B_1
A_2 B_2
:
A_M B_M

Output

Print the number of good observatories.

Sample Input 1

4 3
1 2 3 4
1 3
2 3
2 4

Sample Output 1

2

From Obs. 1, you can reach Obs. 3 using just one road. The elevation of Obs. 1 is not higher than that of Obs. 3, so Obs. 1 is not good.

From Obs. 2, you can reach Obs. 3 and 4 using just one road. The elevation of Obs. 2 is not higher than that of Obs. 3, so Obs. 2 is not good.

From Obs. 3, you can reach Obs. 1 and 2 using just one road. The elevation of Obs. 3 is higher than those of Obs. 1 and 2, so Obs. 3 is good.

From Obs. 4, you can reach Obs. 2 using just one road. The elevation of Obs. 4 is higher than that of Obs. 2, so Obs. 4 is good.

Thus, the good observatories are Obs. 3 and 4, so there are two good observatories.

Sample Input 2

6 5
8 6 9 1 2 1
1 3
4 2
4 3
4 6
4 6

Sample Output 2

3



Sample input:
4 3
1 2 3 4
1 3
2 3
2 4


Sample output:
2

Submission status: Accepted

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

print(ans)

Submission status: Accepted

Solution code:
from sys import stdin,stdout
inp = stdin.readline
out = stdout.write
n,m = map(int,inp().split())
h = [int(u) for u in inp().split()]
adj = [[] for _ in range(n)]
for i in range(m):
    u,v = map(int,inp().split())
    u -= 1
    v -= 1
    adj[u].append(v)
    adj[v].append(u)
marked = [False for _ in range(n)]
cnt = 0
for u in range(n):
    if marked[u]: continue
    good = True
    for v in adj[u]:
        if h[u] <= h[v]:
            good = False
            break
        else: marked[v] = True
    if good: cnt += 1
out(str(cnt))

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
H = list(map(int, input().split()))
edges = {i + 1: [] for i in range(N)}
for i in range(M):
    A, B = map(int, input().split())
    edges[A].append(H[B - 1])
    edges[B].append(H[A - 1])


ans = 0
for i in range(N):
    if len(edges[i+1]) <= 0 or H[i] > max(edges[i+1]):
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
(n, m), h, *r = [[*map(int, i.split())] for i in open(0)]
g =[] + h

for i in r:
    g[i[0]-1] *= h[i[0]-1] > h[i[1]-1]
    g[i[1]-1] *= h[i[1]-1] > h[i[0]-1]
print(len([i for i in g if i !=0]))

Submission status: Accepted

Solution code:
import sys
INF = 10**9
sys.setrecursionlimit(INF)


def main():
    n, m, *hab = map(int, open(0).read().split())
    h = hab[:n]
    ab = hab[n:]
    ab = [[ab[2 * i] - 1, ab[2 * i + 1] - 1] for i in range(m)]

    ans_set = set(range(n))
    not_ans_set = set()
    # print(h)
    for a, b in ab:
        if h[a] >= h[b]:
            ans_set.discard(b)
            not_ans_set.add(b)
        if h[a] <= h[b]:
            ans_set.discard(a)
            not_ans_set.add(a)
        # print(a, b, ans_set, not_ans_set)

    ans = len(ans_set)
    print(ans)
    return(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

n_set = set()
for i in range(1,n+1):
    n_set.add(i)

for ele in m_list:
    if h[ele[0]-1] - h[ele[1]-1] > 0:
        n_set -= {ele[1]}
    elif h[ele[0]-1] == h[ele[1]-1]:
        n_set -= {ele[0], ele[1]}
    else:
        n_set -= {ele[0]}

print(len(n_set))

Submission status: Accepted

Solution code:

# import copy
from sys import stdin
input = stdin.readline

n,m = map(int,input().split())
h = list(map(int,input().split()))
# p = copy.copy(h)
p = [0]*n
# path = list(list(map(int,input().split())) for x in range(m))
for i in range(m):
    x,y = map(int,input().split())
    if h[x-1] > h[y-1]:
        p[y-1] = 1
    elif h[x-1] < h[y-1]:
        p[x -1] = 1
    elif  h[x-1] == h[y-1]:
        p[y-1] = 1
        p[x-1] = 1


print(p.count(0))

Submission status: Accepted

Solution code:

import copy
from sys import stdin
input = stdin.readline

n,m = map(int,input().split())
h = list(map(int,input().split()))
p = copy.copy(h)
# path = list(list(map(int,input().split())) for x in range(m))
for i in range(m):
    x,y = map(int,input().split())
    if h[x-1] > h[y-1]:
        p[y-1] = 0
    elif h[x-1] < h[y-1]:
        p[x -1] = 0
    elif  h[x-1] == h[y-1]:
        p[y-1] = 0
        p[x-1] = 0
cnt = 0
for k in p:
    if k != 0:
        cnt += 1
# print(h)
print(cnt)

Submission status: Accepted

Solution code:

import copy

n,m = map(int,input().split())
h = list(map(int,input().split()))
p = copy.copy(h)
# path = list(list(map(int,input().split())) for x in range(m))
for i in range(m):
    x,y = map(int,input().split())
    if h[x-1] > h[y-1]:
        p[y-1] = 0
    elif h[x-1] < h[y-1]:
        p[x -1] = 0
    elif  h[x-1] == h[y-1]:
        p[y-1] = 0
        p[x-1] = 0
cnt = 0
for k in p:
    if k != 0:
        cnt += 1
# print(h)
print(cnt)

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

Submission status: Accepted

Solution code:
from sys import stdin
input = stdin.readline
N,M = map(int, input().split())
H = [0] + list(map(int, input().split()))
L = [0] + [1]*N
for m in range(M):
    A,B = map(int, input().split())
    if H[A] > H[B]:
        L[B] = 0
    elif H[A] < H[B]:
        L[A] = 0
    else:
        L[A], L[B] = 0, 0
print(sum(L))

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
h = list(map(int, input().split()))
# h = [[i, h[i-1]] for i in range(1, n+1)]
# path = [list(map(int, input().split())) for i in range(m)]
# conn = {key: [] for key in range(1, n+1)}
tower = list(range(1, n+1))
ma = [0]*n

for i in range(m):
    p = list(map(int, input().split()))
    ma[p[0]-1] = max(ma[p[0]-1], h[p[1]-1])
    ma[p[1]-1] = max(ma[p[1]-1], h[p[0]-1])
    """
    # h0 > h1
    if h[p[0]-1] == h[p[1]-1]:
        if p[0] in tower:
            tower.remove(p[0])
        if p[1] in tower:
            tower.remove(p[1])
    elif h[p[0]-1] > h[p[1]-1]:
        if p[1] in tower:
            tower.remove(p[1])
    else:
        if p[0] in tower:
            tower.remove(p[0])
    """
cnt = 0
for i in range(n):
    cnt += (h[i] > ma[i])
print(cnt, end="")

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):
  ab=list(map(int,input().split()))
  if h[ab[0]-1]==h[ab[1]-1]:
    ans[ab[0]-1],ans[ab[1]-1]=0,0
  elif h[ab[0]-1]<h[ab[1]-1]:
    ans[ab[0]-1]=0
  elif h[ab[0]-1]>h[ab[1]-1]:
    ans[ab[1]-1]=0
print(sum(ans))

Submission status: Accepted

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

pair=[]
for _ in range(M):
    inp=list(map(int,input().split()))
    pair.append(inp)

loser=[]
for i in range(M):
    if h[pair[i][0]-1]<h[pair[i][1]-1]:
        loser.append(pair[i][0])
    elif h[pair[i][0]-1]>h[pair[i][1]-1]:
        loser.append(pair[i][1])
    else:
        loser.append(pair[i][0])
        loser.append(pair[i][1])

set_loser=set(loser)
ans=N-int(len(set_loser))
print(ans)

Submission status: Accepted

Solution code:
from sys import stdin
input = stdin.readline
N,M = map(int, input().split())
H = [0] + list(map(int, input().split()))
L = [0] + [1]*N
for m in range(M):
    A,B = map(int, input().split())
    if H[A] > H[B]:
        L[B] = 0
    elif H[A] < H[B]:
        L[A] = 0
    else:
        L[A], L[B] = 0, 0
print(sum(L))

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

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

x = [set() for _ in range(n)]
for a, b in ab:
    x[a-1].add(b-1)
    x[b-1].add(a-1)
    
ans = 0
for i, xx in enumerate(x):
    for xxx in xx:
        if h[i] <= h[xxx]:
            break
    else:
        ans += 1
        
print(ans)

Submission status: Accepted

Solution code:
import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N, M = map(int, readline().split())
H = [0] + list(map(int, readline().split()))
A = [0]*(N+1)

m = map(int, read().split())
for a,b in zip(m,m):
	for _ in range(2):
		A[a] = max(A[a], H[b])
		a,b = b,a

print(sum(x>y for x,y in zip(H, A)))

Submission status: Accepted

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

adj = {i:[] for i in range(N)}
for _ in range(M):
	A, B = map(int, input().split())
	adj[A-1].append(H[B-1])
	adj[B-1].append(H[A-1])

cnt = 0
for v in range(N):
	if not adj[v]:
		cnt += 1
		continue
	if H[v] > max(adj[v]):
		cnt += 1

print(cnt)

Submission status: Accepted

Solution code:
n, m = map(int, input().split()) #n: 展望台の数, m: 道の数
height = list(map(int, input().split())) #高さリスト.nコある.
ans_set = set(range(1, n+1))

for i in range(m):
  a, b = map(int, input().split())
  if height[a-1] >= height[b-1]:
    ans_set.discard(b)	#setのdiscardは存在しない場合は何もしない.
  if height[a-1] <= height[b-1]:
    ans_set.discard(a)
    
print(len(ans_set))

Submission status: Accepted

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

t = [0]*n
for _ in range(m):
    a, b = map(int, input().split())
    t[a - 1] = max(t[a -1], H[b -1])
    t[b - 1] = max(t[b -1], H[a -1])
    
result = 0
for i in range(n):
    if H[i] > t[i]:
        result += 1
print(result)

Submission status: Accepted

Solution code:
from collections import defaultdict, deque


N, M = map(int, input().split())
heights = [None] + [int(x) for x in input().split()]

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

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


# 連結する枝をすべて調べて良い展望台があれば True
def is_good(tower):
  return heights[tower] > max([heights[t] for t in G[tower]], default=0)


print(sum([is_good(t) for t in range(1, N + 1)]))

Submission status: Accepted

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

base = np.ones(n)

for i in range(m):
  a,b =  map(int,input().split())
  if h[a-1] > h[b-1]:
    base[b-1] = 0
  elif h[a-1] < h[b-1]:
    base[a-1] = 0
  elif h[a-1] == h[b-1]:
    base[a-1] = 0
    base[b-1] = 0
    
print(int(np.sum(base)))

Submission status: Accepted

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

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

print(sum(li))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
Hs = list(map(int, input().split()))
Bs = [False]*N
for i in range(M):
  A, B = map(int, input().split())
  A, B = A-1, B-1
  if Hs[A] <= Hs[B]:
    Bs[A] = True
  if Hs[B] <= Hs[A]:
    Bs[B] = True
r = Bs.count(False)
print(r)

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

obs = {i+1: {
    'height': H[i],
    'neighbor_height_max': 0
} for i in range(N)}

for i in range(M):
    obs[A[i]]['neighbor_height_max'] = max(obs[B[i]]['height'], obs[A[i]]['neighbor_height_max'])
    obs[B[i]]['neighbor_height_max'] = max(obs[A[i]]['height'], obs[B[i]]['neighbor_height_max'])


ans = 0
for k, v in obs.items():
    if v['height'] > v['neighbor_height_max']:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
elevations=[0]+[x for x in map(int,input().split())]
connections={x:[] for x in range(1,N+1)}

roads=list()
for i in range(M):
    roads.append(tuple(map(int,input().split())))

for i in roads:
    connections[i[0]].append(i[1])
    connections[i[1]].append(i[0])

notgood=0   
for i in connections:
    if len(connections[i])>0:
        for j in connections[i]:
            if elevations[i]<=elevations[j]:
                notgood+=1
                break

print(N-notgood)

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
Height = list(map(int,input().split()))
ans = N
Data = [0]*(N+1)
for i in range(M):
    a,b = map(int,input().split())
    ha = Height[a-1]
    hb = Height[b-1]
    if ha <= hb:
        if Data[a] == 0:
            ans -= 1
            Data[a] = 1
    if ha >= hb:
        if Data[b] == 0:
            ans -= 1
            Data[b] = 1
print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

P = [[] for _ in range(N)]

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

good = 0
for n in range(N):
    if len(P[n]) == 0 or H[n] > max(P[n]):
        good += 1
print(good)

Submission status: Accepted

Solution code:
num_of_observatory, num_of_road = map(int, input().split())
elevations = list(map(int, input().split()))
road_unions = []
for _ in range(num_of_road):
    road_unions.append(list(map(int, input().split())))

# つながっている展望台のリスト
to_observatorys = [[] for i in range(num_of_observatory)]

for road_union in road_unions:
    to_observatorys[road_union[0] - 1].append(elevations[road_union[1] - 1])
    to_observatorys[road_union[1] - 1].append(elevations[road_union[0] - 1])

num_of_good = 0
for i in range(num_of_observatory):
    # つながっている展望台がない または つながっている展望台よりも高い場合
    if len(to_observatorys[i]) == 0 or elevations[i] > max(to_observatorys[i]):
        num_of_good = num_of_good + 1

print(num_of_good)

Submission status: Accepted

Solution code:
n,m = list(map(int, input().split()))
h = [0] + list(map(int, input().split()))
from collections import defaultdict
d = defaultdict(list)
for _ in range(1, m+1):
    a,b = list(map(int, input().split()))
    d[a].append(h[b])
    d[b].append(h[a])

ans=n-len(d)
for k,v in d.items():
    if h[k] > max(v):
        ans+=1
print(ans)

Submission status: Accepted

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

for i in range(m):
    a, b = map(int,input().split())
    if h[a-1] <= h[b-1] and n_ans[a-1] == 1:
        n_ans[a-1] = 0
    if h[b-1] <= h[a-1] and n_ans[b-1] == 1:
        n_ans[b-1] = 0
print(sum(n_ans))

Submission status: Accepted

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

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

print(sum(n_list))

Submission status: Accepted

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

graph = [[] for _ in range(N + 1)]
for a, b in AB:
    graph[a].append(b)
    graph[b].append(a)
#print(graph)

answer = 0
for i in range(1, N + 1):
    if len(graph[i]) == 0:
        answer += 1
    else:
        flag = 1
        for ni in graph[i]:
            if H[ni] >= H[i]:
                flag = 0
                break
        if flag:
            answer += 1

print(answer)

Submission status: Accepted

Solution code:
N,M = list(map(int,input().split()))
H = list(map(int,input().split()))
AB = [list(map(int,input().split())) for _ in range(M)]
MAX = [0 for _ in range(N)]
for ab in AB:
    MAX[ab[0]-1] = max(MAX[ab[0]-1],H[ab[1]-1])
    MAX[ab[1]-1] = max(MAX[ab[1]-1],H[ab[0]-1])
count = 0
for i,h in enumerate(H):
    if h > MAX[i]:
        count += 1
print(count)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

(N, M) = map(lambda x: int(x), input().split(' '))
H = [i for i in map(lambda x: int(x), input().split(' '))]
dest_max = [0] * len(H)

for i in range(M):
    (a, b) = map(lambda x: int(x), input().split(' '))
    dest_max[a-1] = max(dest_max[a-1], H[b-1])
    dest_max[b-1] = max(dest_max[b-1], H[a-1])

#print(H)
#print(dest_max)
print(len([1 for i in range(len(H)) if H[i] > dest_max[i] ]))

Submission status: Accepted

Solution code:
import numpy as np
argList = list(map(int, input().split())) 
heights = list(map(int, input().split())) 

#いい展望台フラグ
check = np.array([1]*argList[0])

for n in range(argList[1]):
    #どことどこをつないでいるか
    con = list(map(int, input().split())) 
    #低かったらいい展望台ではない
    if heights[con[0]-1] <= heights[con[1]-1]:
        check[con[0]-1] = 0
    if heights[con[0]-1] >= heights[con[1]-1]:
        check[con[1]-1] = 0
print(np.sum(check))

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
h = list(map(int, input().split()))
p = [ set(map(int, input().split())) for _ in range(m) ]
d = [ 0 for _ in range(n)]
for i,j in p:
    d[i-1] = max(d[i-1], h[j-1])
    d[j-1] = max(d[j-1], h[i-1])
c = [ 1 for i,j in enumerate(d) if j < h[i] ]
print(sum(c))

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
h = list(map(int, input().split()))
p = [ set(map(int, input().split())) for _ in range(m) ]
d = [ 0 ] * n
for i,j in p:
    d[i-1] = max(d[i-1], h[j-1])
    d[j-1] = max(d[j-1], h[i-1])
c = [ 0 for i in range(n) if d[i] < h[i] ]
print(len(c))

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
h = [int(x) for x in input().split()]

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

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

ans = 0



for j in range(n):
    flag = 1
    for k in range(len(mem[j])):
        if h[j] <= h[mem[j][k]]:
            flag = 0
    if flag ==  1:
        ans += 1

print(ans)

Submission status: Accepted

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

lower_set = set()
for road in road_list:
    if h[road[0]-1] >= h[road[1]-1]:
        lower_set.add(road[1]-1)
        
    if h[road[0]-1] <= h[road[1]-1]:
        lower_set.add(road[0]-1)

count = 0
for i in range(n):
    if not i in lower_set:
        count += 1

print(count)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
H = list(map(int, input().split()))
bridge = [[] for i in range(n)]
for i in range(m):
    a, b = map(int, input().split())
    bridge[a - 1].append(b - 1)
    bridge[b - 1].append(a - 1)
s = 0
#print(bridge)
for i in range(len(bridge)):
    if not(bridge[i]):
        s += 1
    elif H[i] > max([H[j] for j in bridge[i]]):
        s += 1
print(s)

Submission status: Accepted

Solution code:
N, M = map(int, input().split(' '))
H = tuple(map(int, input().split(' ')))
one_hops = [0] * N

for _ in range(M):
    a, b = map(int, input().split(' '))
    a -= 1
    b -= 1
    one_hops[a] = max(one_hops[a], H[b])
    one_hops[b] = max(one_hops[b], H[a])

print(len([0 for i in range(N) if H[i] > one_hops[i]]))

Submission status: Accepted

Solution code:
from collections import defaultdict

N, M = map(int, input().split(' '))
H = tuple(map(int, input().split(' ')))
edges = defaultdict(set)

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

count = 0
for i in range(N):
    hi = H[i]
    for j in edges[i]:
        if hi <= H[j]:
            break
    else:
        count += 1

print(count)

Submission status: Accepted

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

Submission status: Accepted

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

import collections
G=collections.defaultdict(list)
for _ in range(M):
    A,B=map(int,input().split())
    G[A].append(B)
    G[B].append(A)

i=1
j=0
while i <=N:
    J=[0]
    for a in G[i]:
        J.append(H[a-1])
    if H[i-1] > max(J):
            j+=1
    i+=1
    
print(j)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
N, M = map(int, sys.stdin.readline().rstrip().split())
H = list(map(int, sys.stdin.readline().rstrip().split()))
Route =[list(map(int, sys.stdin.readline().rstrip().split())) for i in range(M)]
cnt=0
l =[[] for i in range(N)]
for r in Route:
	l[r[0]-1].append(r[1])
	l[r[1]-1].append(r[0])
for i in range(N):
	for j in l[i]:
		if H[i]<= H[j-1]:break
	else:
		cnt+=1
print(cnt)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
import math
import itertools

n, m = map(int, input().split())
h = list(map(int, input().split()))
ans = [True] * n
lis = [0] * n
for i in range(m):
    a, b = map(int, input().split())
    lis[a - 1] = max(lis[a - 1], h[b - 1])
    lis[b - 1] = max(lis[b - 1], h[a - 1])
ans = 0
for i in range(n):
    if lis[i] < h [i]:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
N, M  = [int(n) for n in input().split(' ')]
H = [int(n) for n in input().split(' ')]
dic = {}
for i in range(M):
  A,B = [int(n) for n in input().split(' ')]
  if H[A-1]>H[B-1]:
    dic[B]=A
  elif H[A-1]<H[B-1]:
    dic[A]=B
  else:
    dic[B]=A
    dic[A]=B
cnt = 0
for i in range(1,N+1):
  if i not in  dic.keys():
    cnt += 1

print(cnt)

Submission status: Accepted

Solution code:
n, m = tuple(map(int, input().split(' ')))
h = list(map(int, input().split(' ')))
adj = [[] for i in range(n)]
for i in range(m):
  a, b = tuple(map(int, input().split(' ')))
  a -= 1
  b -= 1
  adj[a].append(b)
  adj[b].append(a)
ans = 0
for i in range(n):
  if len(adj[i]) == 0:
    ans += 1
  else:
    ok = True
    for j in adj[i]:
      if h[i] <= h[j]:
        ok = False
    if ok:
      ans += 1
print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
tall = [int(e) for e in input().split()]

is_best = [True]*n

for i in range(m):
    c = [int(f)-1 for f in input().split()]
    a,b = c[0],c[1]
    if tall[a] < tall[b]:
        is_best[a] = False

    elif tall[b] < tall[a]:
        is_best[b] = False

    else:
        is_best[a],is_best[b] = False,False

print(is_best.count(True))

Submission status: Accepted

Solution code:
#　N：展望台の数、M:道の数
N,M=list(map(int,input().split()))
H = list(map(int,input().split()))

ad_list = [[] for n in range(N)]
for m in range(M):
    load=list(map(int,input().split()))
    ad_list[load[0]-1].append(load[1])
    ad_list[load[1]-1].append(load[0])
    
cnt=0
for n in range(N):
    heith = H[n]
    for ad_p_idx in range(len(ad_list[n])+1):
#         print(ad_p_idx)
        if ad_p_idx == len(ad_list[n]):
            cnt+=1
#             print(cnt)
            break
            
        ad_p = ad_list[n][ad_p_idx]
        heith_ad = H[ad_p-1]
#         print(heith,heith_ad)
        if heith <= heith_ad:
            break
        if ad_p_idx == ad_list[n]:
            cnt+=1
print(cnt)

Submission status: Accepted

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

count = 0
for j in range(n):
    if target[j] == win[j]:
        count += 1

print(count)

Submission status: Accepted

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

obs = [0]*n

for _ in range(m):
    a, b = map(lambda x: int(x)-1, input().split())
    if h[a] > h[b]:
        obs[b] = 1;
    elif h[b] > h[a]:
        obs[a] = 1;
    else:
        obs[a] = 1;
        obs[b] = 1;

print(obs.count(0))

Submission status: Accepted

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

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

J={x:[] for x in range(1,N+1)}

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

S=0
for x in J:
    f=1
    for y in J[x]:
        if H[x]<=H[y]:
            f=0
    S+=f

print(S)

Submission status: Accepted

Solution code:
#import bisect,collections,copy,heapq,itertools,math,numpy,string
#from operator import itemgetter
import sys
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())
N,M = LI()
H = LI()
AB = [LI() for _ in range(M)]
path = [[] for _ in range(N+1)]
chk = [True] * (N+1)
nice = 0

for ab in AB:
	a = ab[0]
	b = ab[1]
	path[a].append(b)
	path[b].append(a)

for i in range(1,N+1):
	if chk[i]:
		chk[i] = False
		if not path[i]:
			#print(i)
			nice+=1
		else:
			flg = 0
			for j in path[i]:
				if H[i-1] > H[j-1]:
					chk[j] = False
				else:
					flg = 1
			if flg == 0:
				#print(i)
				nice+=1
print(nice)

Submission status: Accepted

Solution code:
import copy
n,m = map(int,input().split())
tall = [int(e) for e in input().split()]

bridge = copy.copy(tall)

for i in range(m):
    c = [int(f)-1 for f in input().split()]
    a,b = c[0],c[1]
    if bridge[a] < tall[b]:
        bridge[a] = tall[b]
    elif bridge[a] == tall[b]:
        bridge[a] = 10**10
    if bridge[b] < tall[a]:
        bridge[b] = tall[a]
    elif bridge[b] == tall[a]:
        bridge[b] = 10**10

cnt = 0
for j in range(n):
    if tall[j] == bridge[j]:
        cnt += 1

print(cnt)

Submission status: Accepted

Solution code:
n,m = (int(x) for x in input().split())
edge = [[] for x in range(n)]
hight = [int(x) for x in input().split()]
highest = [True]*n
ans = 0

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

for i in range(n):
    if(highest[i] == False):
        continue
    high = hight[i]
    flag =True
    for v in edge[i]:
        if hight[v-1] >= high:
            flag=False
            break
        else:
            highest[v-1] = False
    if(flag):
        ans +=1


print(ans)

Submission status: Accepted

Solution code:


n, m = map(int, input().split())
h = [] * n

h[:] = map(int, input().split())
dic={}
for i in range(len(h)):
    dic[i+1] = h[i]

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

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


count = 0

for i in range(n):
    more = 0
    n_h = dic[i+1]
    next = graph[i]
    
    for n in next:
        o_h = dic[n]
        if o_h >= n_h:
            more+=1
    
    if more == 0:
        count+=1

print(count)

Submission status: Accepted

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

Submission status: Accepted

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