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:
from collections import defaultdict

n, m= list(map(int,input().split()))
h = list(map(int,input().split()))
h = [0] + h

good = [False] + [True]*n

while m:
    m -= 1
    a, b = list(map(int,input().split()))
    if h[a] < h[b]:
        good[a] = False
    elif h[a]==h[b]:
        good[a] = good[b] = False
    else:
        good[b] = False

print(good.count(True))

Submission status: Accepted

Solution code:
from sys import stdin
import math
import fractions
from collections import deque
from collections import Counter
import itertools

INF = 10 ** 10

N, M = [int(x) for x in stdin.readline().rstrip().split()]
# 展望台iの標高
H = [int(x) for x in stdin.readline().rstrip().split()]
AB = [list(map(int, stdin.readline().rstrip().split())) for _ in range(M)]

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

for A, B in AB:
    dic[A].append(B)
    dic[B].append(A)

ans = 0
i = len(dic)
while i > 0:
    key = i
    values = set(dic[i])
    near_H = [H[value-1] for value in values]
    if near_H:
        if H[key-1] > max(near_H):
            ans += 1
    else:
        ans += 1
    i -= 1

print(ans)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10**7)

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

n, m = na()
h = na()
mh = [0 for i in range(n)]
for i in range(m):
    a, b = na()
    mh[a-1] = max(mh[a-1], h[b-1])
    mh[b-1] = max(mh[b-1], h[a-1])
ans = 0  
for i in range(n):
    if h[i] > mh[i]:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
import sys

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

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

a = [None]*m
b = [None]*m
for i in range(m):
    a[i],b[i] = (int(j) for j in input().split())
    a[i]-=1
    b[i]-=1

hantei = [True]*n

for i in range(m):
    if h[a[i]] < h[b[i]]:
        hantei[a[i]] = False
    elif h[a[i]] > h[b[i]]:
        hantei[b[i]] = False
    else:
        hantei[a[i]] = hantei[b[i]] = False

ans = 0

for i in range(n):
    if hantei[i] == True:
        ans +=1

print(ans)

Submission status: Accepted

Solution code:
N, M = [ int(i) for i in input().strip().split(' ') ]
H    = [ int(i) for i in input().strip().split(' ') ]
paths = []
max_neighbor = [ 0 for _ in range(N)]

for _m in range(M):
    path = input().strip().split(' ')
    path = int(path[0]), int(path[1])
    max_neighbor[path[0]-1] = max(max_neighbor[path[0]-1], H[path[1]-1])
    max_neighbor[path[1]-1] = max(max_neighbor[path[1]-1], H[path[0]-1])
count = 0
for n in range(N):
    if max_neighbor[n] < H[n]:
        count += 1
print(count)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 6)
def input():
	return sys.stdin.readline()[:-1]

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

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

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

cnt = 0
for i in range(n):
	h = H[i]
	flag = 1
	for nxt in edge[i]:
		# print(nxt)
		# print(H)
		if H[nxt] >= h:
			flag = 0
			break
		elif H[nxt] < h: continue
	if flag: cnt += 1

print(cnt)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from collections import defaultdict
import sys
sys.setrecursionlimit(100000000)
def DFS(u,G,H,A,visited,P):
    visited[u]=True
    for v in G[u]:
        if not (min(u,v),max(u,v)) in P:
            if H[u-1]>H[v-1]:
                    A[u]+=1
            elif H[v-1]>H[u-1]:
                    A[v]+=1
            P.add((min(u,v),max(u,v)))
        if not visited[v]:
            DFS(v,G,H,A,visited,P)

def DFSUtil(G,H,N):
    visited=[False]*(N+1)
    A=[0]*(N+1)
    P=set()
    for u in G:
        if (not visited[u]):
            DFS(u,G,H,A,visited,P)
    return A
N,M=map(int,input().strip().split())
H=list(map(int,input().strip().split()))
G=defaultdict(list)

for i in range(M):
    u,v=map(int,input().strip().split())
    G[u].append(v)
    G[v].append(u)
A=DFSUtil(G,H,N)
cnt=0
for i in range(1,N+1):
    neighbours=len(list(set(G[i])))
    if neighbours==A[i]:
        cnt+=1
print(cnt)

Submission status: Accepted

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

ans = [1] * N

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:

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

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

path = [0]
for i in range(1,N+1):
	path.append([])

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

count = 0

for i in range(1,N+1):
	if len(path[i]) == 0:
		count += 1
	elif H[i] > max(H[j] for j in path[i]):
		count += 1
	
print(count)

Submission status: Accepted

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

ans_label = [1]*len(H)

new_A_B = []

for ele in A_B:
    if H[ele[0]-1] < H[ele[1]-1]:
        new_A_B.append(ele[0])
    elif H[ele[0]-1] > H[ele[1]-1]:
        new_A_B.append(ele[1])
    else:
        new_A_B.append(ele[0])
        new_A_B.append(ele[1])

# A_B = [[ele[0],ele[1]] if H[ele[0]-1] < H[ele[1]-1] else [ele[1],ele[0]]for ele in A_B]

# A_B.sort(key=lambda x: x[0])

for ele in new_A_B:
    ans_label[ele-1] = 0

# print(ans_label)

print(sum(ans_label))

Submission status: Accepted

Solution code:
N, M = tuple(int(i) for i in input().split(" "))
height = [int(i) for i in input().split(" ")]
road = []
for i in range(N):
    road.append([])
for i in range(M):
    temp = [int(j) - 1 for j in input().split(" ")]
    road[temp[0]].append(temp[1])
    road[temp[1]].append(temp[0])

goodH = [1 for i in range(N)]
ans = 0
for i in range(N):
    if goodH[i]:
        for j in road[i]:
            if height[i] > height[j]:
                goodH[j] = 0
            elif height[i] == height[j]:
                goodH[j] = 0
                goodH[i] = 0
                break
            else:
                goodH[i] = 0
                break
        else:
            ans += 1
print(ans)

Submission status: Accepted

Solution code:
def main():
    n,m=map(int,input().split())
    h=list(map(int,input().split()))
    res=[1]*n
    for i in range(m):
        a,b=map(int,input().split())
        if h[a-1]<h[b-1]:
            res[a-1]=0
        elif h[a-1]>h[b-1]:
            res[b-1]=0
        else:
            res[a-1]=0
            res[b-1]=0
    print(sum(res))
if __name__=="__main__":
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict

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

# graph = {}
# for i in range(1, N + 1):
#     graph[i] = [0]
# for _ in range(M):
#     A, B = map(int, input().split())
#     graph[A].append(B)
#     graph[B].append(A)

graph = {}
for i in range(1, N + 1):
    graph[i] = {0}
for _ in range(M):
    A, B = map(int, input().split())
    graph[A].add(B)
    graph[B].add(A)

# [print(k, v) for k, v in graph.items()]
# print(graph[4])
cnt = 0
for i in range(1, N + 1):
    if H[i] > max(H[j] for j in graph[i]):
        cnt += 1
print(cnt)

# for _ in graph:

# # adjacent matrix
# adj_mat = [
#     [0, 1, 1, 0],
#     [0, 0, 1, 1],
#     [0, 0, 0, 1],
#     [0, 0, 0, 0]
# ]

Submission status: Accepted

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

Submission status: Accepted

Solution code:
a,b = map(int,input().split(" "))
ar = list(map(int,input().split(" ")))
br = [[] for i in range(a)]
for i in range(b):
    x,y = map(int,input().split(" "))
    br[x-1].append(y-1)
    br[y-1].append(x-1)
ans = 0
for i in range(a):
    count = 0
    for r in br[i]:
        if ar[r] >= ar[i]:
            count += 1
    if count == 0:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
N, M = list(map(int, input().split()))
H = list(map(int, input().split()))
H.insert(0,0)
L = []
C = 0
for i in range(N+1):
    L.append(list())
for i in range(M):
    A, B = list(map(int, input().split()))
    L[A].append(B)
    L[B].append(A)
for i, l in enumerate(L):
    if i == 0:
        continue
    if len(l) == 0:
        C += 1
        continue
    for n in l:
        f = True
        if H[i] <= H[n]:
            f = False
            break
    if f:
        C += 1
print(C)

Submission status: Accepted

Solution code:
N,M = [int(x) for x in input().split()]
H = [int(x) for x in input().split()]
from collections import defaultdict

P = defaultdict(set)
for _ in range(M):
    a,b = [int(x) for x in input().split()]
    P[a-1].add(b-1)
    P[b-1].add(a-1)

ans = 0
for i in range(N):
    h = [H[j] for j in P[i]]
    m = max(h) if len(h) > 0 else 0
    if H[i] > m:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**7)

# 1 ✕ N
N, M = list(map(int, input().rstrip().split()))

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

A = tuple(map(int, input().rstrip().split()) for _ in range(M))


items = dict((i + 1, []) for i in range(N))

for k, v in A:
    items[k].append(H[v - 1])
    items[v].append(H[k - 1])

# print(items)

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

    found = False
    for item in items[i + 1]:
        if item >= H[i]:
            found = True
            continue

    if not found:
        ans += 1
        continue

    # if len(list(filter(lambda hx: H[i] >= hx, items[i + 1]))) == 0:
    #     print(i + 1)
    #     ans += 1
    #     continue
        #     # if len(items[i + 1]) == 0:
        #     #     ans += 1
        #     #     continue

        #     print("------------")
        #     print(items[i + 1])
        #     tmp = list(filter(lambda x: H[i] >= H[x - 1], items[i + 1]))
        #     print(tmp)

        #     if len(list(filter(lambda x: H[i] >= H[x - 1], items[i + 1]))) == 0:
        #         ans += 1
        #         continue

print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
temp = input()
temp = temp.split()
N = int(temp[0])
M = int(temp[1])

temp = input()
temp = temp.split()
height = [int(s) for s in temp]
bridge = [0] * N
data = [0] * N

for i in range(M):
  temp = input()
  temp = temp.split()
  A = int(temp[0])
  B = int(temp[1])
  if height[A-1] > height[B-1]:
    data[B-1] = 1
  elif height[A-1] < height[B-1]:
    data[A-1] = 1
  else:
    data[A-1] = data[B-1] = 1
    
  bridge[A-1] = 1
  bridge[B-1] = 1

count = 0
for i in range(N):
  if data[i] == 0 or bridge[i] == 0:
    count += 1
print(count)

Submission status: Accepted

Solution code:
N_ko, M_hon = map(int, input().split())
Height = list(map(int, input().split()))

Low = []
ans = 0

for i in range(M_hon):
    a, b = map(int, input().split())
    
    h_a = Height[a - 1]
    h_b = Height[b - 1]

    
    if (h_a != h_b):
        
        if (h_a > h_b):
            Low.append(b)
        else:
            Low.append(a)
    else:
        Low.append(a)
        Low.append(b)

ans = N_ko - len(set(Low))


print(ans)

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
H=[int(h) for h in input().split()]
cnt=[0]*N
for i in range(M):
    a,b=map(int,input().split())
    if H[a-1]>H[b-1]:
        cnt[b-1]+=1
    elif H[a-1]==H[b-1]:
        cnt[a-1]+=1
        cnt[b-1]+=1
    else:
        cnt[a-1]+=1
print(cnt.count(0))

Submission status: Accepted

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

print(array.count(0))

Submission status: Accepted

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

print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# C
# Peaks

import numpy as np

N, M = map(int, input().split())
H_list = [int(x) for x in input().split()]
N_list = np.arange(1,N+1,1)
Max_list = np.zeros(N)
for i in range(M):
    A, B = map(int, input().split())
    Max_list[A-1] = max(Max_list[A-1],H_list[B-1])
    Max_list[B-1] = max(Max_list[B-1],H_list[A-1])
    
ans = 0
for i in range(len(Max_list)):
    ans += H_list[i] > Max_list[i]

print(ans)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
h = list(map(int, input().split()))
h_dict = {}
for i, name in enumerate(h, 1):
    h_dict[i] = name

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

flg_bad = set()
for j in ab:
    if h_dict[j[0]] < h_dict[j[1]]:
        flg_bad.add(j[0])
    elif h_dict[j[0]] > h_dict[j[1]]:
        flg_bad.add(j[1])
    elif h_dict[j[0]] == h_dict[j[1]]:
        flg_bad.add(j[0])
        flg_bad.add(j[1])

print(len(h) - len(flg_bad))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
# 標準入力の取得
N, M = list(map(int, input().split()))
H = list(map(int, input().split()))
A, B = [], []
for m in range(M):
    A_m, B_m = list(map(int, input().split()))
    A.append(A_m)
    B.append(B_m)


def main() -> None:
    """Entry point
    """
    # 求解処理
    # 道ごとに「良い展望台」ではない展望台を削除し、残りの展望台の数を計算する。
    observatory = [True for n in range(N)]  # 初期状態はすべて「良い展望台」
    for A_m, B_m in zip(A, B):
        A_m -= 1  # インデックス番号に変換
        B_m -= 1  # インデックス番号に変換
        if H[A_m] < H[B_m]:
            observatory[A_m] = False
        elif H[A_m] > H[B_m]:
            observatory[B_m] = False
        else:
            observatory[A_m] = False
            observatory[B_m] = False

    result = sum(observatory)

    # 結果出力
    print(result)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
H = list(map(int, input().split()))
a = [True] * N
for i in range(M):
  ai, bi = map(int, input().split())
  if H[ai-1] <= H[bi-1] :
    a[ai-1] = False
  if H[ai-1] >= H[bi-1]:
    a[bi-1] = False
print(sum(a))

Submission status: Accepted

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

Submission status: Accepted

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

ans = 0
for j in range(N):
  if g[j] == r[j]:
    ans += 1
print(ans)

Submission status: Accepted

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

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

ans = sum([c == 0 for c in check])
print(ans)
#print(check)

Submission status: Accepted

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

Submission status: Accepted

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

not_good=set(not_good)
print(n-len(not_good))

Submission status: Accepted

Solution code:
# N個のTrueの展望台リストを作り、隣り合うペアのうち標高が低いほうをFalseにしていく

import sys
readline = sys.stdin.readline

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

ans = [True] * N

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

print(sum(ans))

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
p_list = [1 for _ in range(N)]
e_list = list(map(int, input().split()))
for _ in range(M):
   a, b = map(int, input().split())
   if e_list[a - 1] <= e_list[b - 1]:
       p_list[a - 1] = 0
   if e_list[b - 1] <= e_list[a - 1]:
       p_list[b - 1] = 0
print(sum(p_list))

Submission status: Accepted

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

for i in range(m):
    a, b = list(map(int, input().split()))
    a -= 1
    b -= 1

    t[a].add(b)
    t[b].add(a)

ans = 0
for i in range(n):
    tmp = 1
    for v in t[i]:
        if h[i] <= h[v]:
            tmp = 0
            False

    ans += tmp

print(ans)

Submission status: Accepted

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

tenbodai = [0] * n
for i in range(m):
    a, b = map(int, input().split())
    tenbodai[a-1] = max(tenbodai[a-1], high[b-1])
    tenbodai[b-1] = max(tenbodai[b-1], high[a-1])

res = sum([high[i] > tenbodai[i] for i in range(n)])
print(res)

Submission status: Accepted

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

for i in range(M):
    a, b = list(map(int, input().split()))
    a -= 1; b -= 1
    
    g[a].add(b)
    g[b].add(a)
    
ans = 0
for i in range(N):
    f = True
    
    for v in g[i]:
        if H[i] <= H[v]:
            f = False
            break
    ans += f

print(ans)

Submission status: Accepted

Solution code:
n, m = list(map(lambda x: int(x), input().split(' ')))
hs = [int(i) for i in input().split(' ')]
is_higher = [1] * len(hs)

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

print(sum(is_higher))

Submission status: Accepted

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


A_list = []
B_list = []
Remove_list = []

for _ in range(M):
  A, B = map(int, input().split())
  A_list.append(A - 1)
  B_list.append(B - 1)

for A, B in zip(A_list, B_list):
  A_height = H[A]
  B_height = H[B]
  
  if A_height <= B_height:
    Remove_list.append(A)
  
  if B_height <= A_height: 
    Remove_list.append(B)
  
S = set(range(N))
S = S - set(Remove_list)

print(len(S))

Submission status: Accepted

Solution code:
from __future__ import annotations

from dataclasses import dataclass, field
from typing import List
from typing import Tuple


@dataclass
class Tour:
    height: int
    connected_other_tours: List[Tour] = field(default_factory=list)

    def connect(self, other_tour: Tour) -> None:
        self.connected_other_tours.append(other_tour)

    def is_good(self) -> bool:
        """
        展望台 i が良い展望台であるとは、
            ・展望台 i から一本の道を使って辿り着けるどの展望台よりも展望台 i の方が標高が高いことをいいます。
            ・展望台 i から一本の道を使って辿り着ける展望台が存在しない場合も、展望台 i  は良い展望台であるといいます。
        """
        for other_tour in self.connected_other_tours:
            if self.height <= other_tour.height:
                return False

        return True


@dataclass
class Tours:
    values: List[Tour] = field(default_factory=list)

    def add(self, tour: Tour) -> None:
        self.values.append(tour)  # メモリ重視して破壊的変更

    def register_routes(self, ab_list: List[Tuple[int, int]]) -> None:
        for a, b in ab_list:
            tour_a = self.values[a - 1]
            tour_b = self.values[b - 1]

            tour_a.connect(tour_b)
            tour_b.connect(tour_a)

    def count_good_tours(self) -> int:
        return sum([tour.is_good() for tour in self.values])

    @classmethod
    def create(cls, height_list: List[int]) -> Tours:
        return Tours([Tour(height) for height in height_list])


def answer(height_list: List[int], ab_list: List[Tuple[int, int]]) -> int:
    tours = Tours.create(height_list)

    tours.register_routes(ab_list)

    return tours.count_good_tours()


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

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

# print(N, M)
# print(h_list)
# print(ab_list)

print(answer(h_list, ab_list))

Submission status: Accepted

Solution code:
import sys
from io import StringIO
import unittest

def resolve():
    n, m = map(int, input().split())
    heights = list(map(int, input().split()))
    bridges = [list(map(int, input().split())) for i in range(m)]

    # 結果を保持する配列
    bests = [True for i in range(n)]

    # 処理開始
    for bridge in bridges:

        bridge[0] -= 1
        bridge[1] -= 1

        if heights[bridge[0]] > heights[bridge[1]]:
            bests[bridge[1]] = False
        elif heights[bridge[0]] < heights[bridge[1]]:
            bests[bridge[0]] = False
        else:
            bests[bridge[1]] = False
            bests[bridge[0]] = False

    print(bests.count(True))


class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)
    def test_入力例_1(self):
        input = """4 3
1 2 3 4
1 3
2 3
2 4"""
        output = """2"""
        self.assertIO(input, output)
    def test_入力例_2(self):
        input = """6 5
8 6 9 1 2 1
1 3
4 2
4 3
4 6
4 6"""
        output = """3"""
        self.assertIO(input, output)

if __name__ == "__main__":
    # unittest.main()
    resolve()

Submission status: Accepted

Solution code:
from __future__ import annotations

from dataclasses import dataclass
from dataclasses import field
from typing import List, Tuple


@dataclass
class Tour:
    height: int
    routes: List[Tour] = field(default_factory=list)

    def add_tour(self, tour: Tour) -> None:
        self.routes.append(tour)

    def is_good(self) -> bool:
        for other_tour in self.routes:
            if self.height <= other_tour.height:
                return False

        return True


@dataclass
class Actual:
    h_list: List[int]
    ab_list: List[Tuple[int, int]]
    tours: List[Tour] = field(default_factory=list)

    def answer(self) -> int:
        self.create_tours()

        self.register_routes()

        return self.count_good_tours()

    def count_good_tours(self) -> int:
        is_good_list = [tour.is_good() for tour in self.tours]

        return sum(is_good_list)

    def register_routes(self) -> None:
        for a, b in self.ab_list:
            tour_a = self.tours[a - 1]
            tour_b = self.tours[b - 1]

            tour_a.add_tour(tour_b)
            tour_b.add_tour(tour_a)

    def create_tours(self) -> None:
        for h in self.h_list:
            tour = Tour(height=h)
            self.tours.append(tour)


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

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

# print(N, M)
# print(h_list)
# print(ab_list)

print(Actual(h_list, ab_list).answer())

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
Hlist = list(map(int, input().split()))
badSign = set()
oldroute = []

for i in range(M):
  nowRoute = list(map(int, input().split()))
  if nowRoute == oldroute:
    badSign.add(nowRoute[0])
    badSign.add(nowRoute[1])
  else:
    if Hlist[nowRoute[0]-1] < Hlist[nowRoute[1]-1]:
      badSign.add(nowRoute[0])
    elif Hlist[nowRoute[0]-1] > Hlist[nowRoute[1]-1]:
      badSign.add(nowRoute[1])
    else:
      badSign.add(nowRoute[0])
      badSign.add(nowRoute[1])
    oldroute = nowRoute
print(N-len(badSign))

Submission status: Accepted

Solution code:
def is_good_obs(num,obs_height,linked_num):
  for e in linked_num[num-1]: 
    if(obs_height[i-1] <= obs_height[e]):
      return False
  return True
      

N,M = (int(x) for x in input().split())
obs_height = [int(x) for x in input().split()]
linked_num = [[] for i in range(N)]
good_obs_num = 0

for i in range(M):
  a,b = (int(x) for x in input().split())
  linked_num[a-1].append(b-1)
  linked_num[b-1].append(a-1)
  
for i in range(N):
    if(is_good_obs(i,obs_height,linked_num)):
      good_obs_num += 1
  
print(good_obs_num)

Submission status: Accepted

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


def main():
    import sys
    input = sys.stdin.readline

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

    for i in range(m):
        ai, bi = map(int, input().split())

        ai -= 1
        bi -= 1

        p[ai].append(h[bi])
        p[bi].append(h[ai])

    ans = 0

    for index, pi in enumerate(p):
        p_count = len(pi)

        if p_count == 0:
            ans += 1
            continue

        pmax = max(pi)

        if h[index] > pmax:
            ans += 1

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from __future__ import division, print_function
import sys
if sys.version_info[0] < 3:
    from __builtin__ import xrange as range
    from future_builtins import ascii, filter, hex, map, oct, zip

import os, sys, bisect, copy
from collections import defaultdict, Counter, deque
#from functools import lru_cache   #use @lru_cache(None)
if os.path.exists('in.txt'): sys.stdin=open('in.txt','r')
if os.path.exists('out.txt'): sys.stdout=open('out.txt', 'w')
#
def input(): return sys.stdin.readline()
def mapi(arg=0): return map(int if arg==0 else str,input().split())
#------------------------------------------------------------------


n,m = mapi()
h = list(mapi())
g = defaultdict(list)
for i in range(m):
    x,y= mapi()
    g[x].append(y)
    g[y].append(x)
res = 0
for i in range(1,n+1):
    tmp = h[i-1]
    f = 1
    for j in g[i]:
        if tmp<=h[j-1]:
            f =0
            break
    if f:res+=1
print(res)

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())
	a, b = A-1, B-1
	if H[a] >= H[b]:
		L[b] = 0
	if H[b] >= H[a]:
		L[a] = 0
print(sum(L))

Submission status: Accepted

Solution code:
from collections import defaultdict
import sys

ip = lambda : sys.stdin.readline()
ipl = lambda : sys.stdin.readline().split()

n, m = map(int, ipl())
elevation = list(map(int, ipl()))
elevation.insert(0, 0)
# construct graph
Graph = defaultdict(list)
for i in range(m):
	s, e = map(int, ipl())
	Graph[s].append(e)
	Graph[e].append(s)
c = 0
for i in range(1, n+1):
	f = 1
	for j in Graph[i]:
		if elevation[j] >= elevation[i]:
			f = 0
			break
	if f:
		c += 1
print(c)

Submission status: Accepted

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