Problem:


Score : 300 points

Problem Statement

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

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

How many good observatories are there?

Constraints

2 \leq N \leq 10^5

1 \leq M \leq 10^5

1 \leq H_i \leq 10^9

1 \leq A_i,B_i \leq N

A_i \neq B_i

Multiple roads may connect the same pair of observatories.

All values in input are integers.

Input

Input is given from Standard Input in the following format:

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

Output

Print the number of good observatories.

Sample Input 1

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

Sample Output 1

2

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

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

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

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

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

Sample Input 2

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

Sample Output 2

3



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


Sample output:
2

Submission status: Accepted

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

numbers = input().split(" ")
n = int(numbers[0])
m = int(numbers[1])

numbers = input().split(" ")
h = [int(x) for x in numbers]
h.insert(0, 0)

is_good = [1] * (n + 1)

for i in range(m):
  numbers = input().split(" ")
  a = int(numbers[0])
  b = int(numbers[1])
  if h[a] <= h[b]:
    is_good[a] = 0
  if h[a] >= h[b]:
    is_good[b] = 0

print(is_good.count(1) - 1)

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
h = list(map(int,input().split()))
r = []
g = [1]*n
for i in range(m):
    ps = [int(i)-1 for i in input().split()]
    x,y = ps[0],ps[1]
    if h[x] >= h[y]:
        g[y] = 0
    if h[y] >= h[x]:
        g[x] = 0
print(sum(g))

Submission status: Accepted

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

ans = 0

#辺を取り除くことはabのセットとなっている要素から取り除くことと等価。頂点を消すのではない。
h_list = list(map(int, input().split()))
c = 0
max_list = [0]*(n+1)

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

    max_list[a] = max(max_list[a],h_list[b-1])
    max_list[b] = max(max_list[b],h_list[a-1])


for i in range(1,n+1):
    if h_list[i-1] > max_list[i]:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
n,m= map(int, input().split())
h =[0]+ [int(x) for x in input().split()]
miti=[]
for i in range(m):
    tmp = [int(x) for x in input().split()]
    miti.append(tmp)

good=[0]+[True]*n

for i in miti:
    if h[i[0]]<h[i[1]]:
        good[i[0]]=False
    elif h[i[1]]<h[i[0]]:
        good[i[1]]=False
    else:
        good[i[0]]=False
        good[i[1]]=False

print(good.count(True))

Submission status: Accepted

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

ans = 0
for i in range(1, N+1):
    cd = [H[j-1] for j in d[i]]
    v = max(cd) if cd else 0
    if H[i-1]>v:
        ans += 1

print(ans)

Submission status: Accepted

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

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

print(n - z.count(0))

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()))
data = [[] for _ in range(N+1)]
for _ in range(M):
    a,b = map(int,readline().split())
    data[a].append(b)
    data[b].append(a)
flag = [True]*(N+1)
for i in range(1,N+1):
    if flag[i] == False:
        continue
    for k in data[i]:
        if  H[i] > H[k]:
            flag[k] = False
        else:
            flag[i] = False
print(flag.count(True)-1)

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
tower = list(map(int,input().split()))
road = [list(map(int,input().split())) for i in range(M)]
aa = ['.']*N
for i in road:
  if tower[i[0]-1] > tower[i[1]-1]:
    aa[i[1]-1] = 'v'
  elif tower[i[0]-1] == tower[i[1]-1]:
    aa[i[0]-1] = aa[i[1]-1] = 'v'
  else:
    aa[i[0]-1] = 'v'
print(aa.count('.'))

Submission status: Accepted

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

Submission status: Accepted

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

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

result = 0
for i in range(n):
  if height_list[i] > heightest_list[i]:
    result += 1

print(result)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import defaultdict, Counter
from itertools import product, groupby, count, permutations, combinations
from math import pi, sqrt
from collections import deque
from bisect import bisect, bisect_left, bisect_right
from string import ascii_lowercase
from functools import lru_cache
import sys
sys.setrecursionlimit(10000)
INF = float("inf")
YES, Yes, yes, NO, No, no = "YES", "Yes", "yes", "NO", "No", "no"
dy4, dx4 = [0, 1, 0, -1], [1, 0, -1, 0]
dy8, dx8 = [0, -1, 0, 1, 1, -1, -1, 1], [1, 0, -1, 0, 1, 1, -1, -1]


def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W


def ceil(a, b):
    return (a + b - 1) // b


def sum_of_arithmetic_progression(s, d, n):
    return n * (2 * s + (n - 1) * d) // 2


def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)


def lcm(a, b):
    g = gcd(a, b)
    return a / g * b


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

    ok = [1] * N
    for _ in range(M):
        A, B = map(int, input().split())
        A -= 1
        B -= 1

        if H[A] <= H[B]:
            ok[A] = 0
        if H[B] <= H[A]:
            ok[B] = 0

    print(sum(ok))

def main():
    solve()


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
a_list = list(map(int,input().split()))
list_n = [0]*(N+1)
for i in range(M):
  
  a,b = map(int,input().split())
  a_n = a_list[a-1]
  b_n = a_list[b-1]
  if a_n == b_n:
    list_n[a]-=10000
    list_n[b]-=10000
  elif a_n>b_n:
    list_n[a] +=1
    list_n[b] -= 10000
  elif a_n<b_n:
    list_n[b] +=1
    list_n[a] -= 10000
count =0
for i in range(1,N+1):
  if list_n[i]>=0:
    count+=1
print(count)

Submission status: Accepted

Solution code:
from collections import defaultdict
d=defaultdict(list)
n ,m =list(map(int,input().split()))
h=list(map(int,input().split()))
for i in range(m):
    a,b=list(map(int,input().split()))
    d[a].append(b)
    d[b].append(a)
s=0
for c in d:
    k=0
    for v in d[c]:
        if h[c-1]<=h[v-1]:
            k=1
            break
    #print(c,k,d)
    if k==0:
        s+=1
s+=n-len(d)
print(s)

Submission status: Accepted

Solution code:
import bisect,collections,copy,heapq,itertools,math,string
import sys
def S(): return sys.stdin.readline().rstrip()
def M(): return map(int,sys.stdin.readline().rstrip().split())
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def LS(): return list(sys.stdin.readline().rstrip().split())
n, m = M()
h_list = LI()
ans_list = [1] * n
for _ in range(m):
    a, b = M()
    if h_list[a-1] < h_list[b-1]:
        ans_list[a-1] = 0
    elif h_list[a-1] == h_list[b-1]:
        ans_list[a-1] = 0
        ans_list[b-1] = 0
    else:
        ans_list[b-1] = 0
print(sum(ans_list))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def resolve():
  n, m = map(int, input().split())
  h = list(map(int, input().split()))
  ans = {i for i in range(n)}

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

  print(len(ans))
  return

if __name__ == "__main__":
  resolve()

Submission status: Accepted

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

tenbo = [[] for j in range(N + 1)]

for a, b in AB:
    tenbo[a].append(b)
    tenbo[b].append(a)

ans = 0
for i in range(1, N + 1):
    x = H[i - 1]
    f = True
    for t in tenbo[i]:
        if x > H[t - 1]:
            continue
        else:
            f = False
            break
    if f:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush
from bisect import bisect_left,bisect_right 
import sys,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

n,m = inpl()
h = inpl()
g = [[] for _ in range(n)]
for _ in range(m):
    a,b = inpl()
    a,b = a-1,b-1
    g[a].append(b)
    g[b].append(a)
res = 0
for i in range(n):
    for j in g[i]:
        if h[j] >= h[i]:
            break
    else:
        res += 1
print(res)

Submission status: Accepted

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

es = [[] for _ in range(N)]
for a,b in AB:
    a,b = a-1,b-1
    es[a].append(b)
    es[b].append(a)
ans = 0
for i in range(N):
    for to in es[i]:
        if H[to] >= H[i]:
            break
    else:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

N,M=map(int,input().split())
h=list(map(int,input().split()))
edge=[[] for _ in range(N)]
for _ in range(M):
    a,b=map(int1,input().split())
    edge[a].append(b)
    edge[b].append(a)
ans=0
for i in range(N):
    for nv in edge[i]:
        if h[nv]>=h[i]:
            break
    else:
        ans+=1
print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict, deque, Counter
import math

# import copy
from bisect import bisect_left, bisect_right
import heapq

# sys.setrecursionlimit(1000000)

# input aliases
input = sys.stdin.readline

getS = lambda: input().strip()
getN = lambda: int(input())
getList = lambda: list(map(int, input().split()))
getZList = lambda: [int(x) - 1 for x in input().split()]

INF = 10 ** 20
MOD = 10**9 + 7
divide = lambda x: pow(x, MOD-2, MOD)


def nck(n, k, kaijyo):
    return (npk(n, k, kaijyo) * divide(kaijyo[k])) % MOD


def npk(n, k, kaijyo):
    if k == 0 or k == n:
        return n % MOD
    return (kaijyo[n] * divide(kaijyo[n-k])) % MOD


def kaijyo(n):
    ret = [1]
    for i in range(1, n + 1):
        ret.append((ret[-1] * i)% MOD)
    return ret


def solve():
    n, m = getList()
    nums = getList()
    peaks = [[] for i in range(n)]

    for i in range(m):
        a,b = getZList()
        peaks[a].append(b)
        peaks[b].append(a)
    ans = 0
    for i, num in enumerate(nums):
        flg = True
        for p in peaks[i]:
            if nums[p] >= num:
                flg = False

        if flg:
            ans += 1

    print(ans)


def main():
    n = getN()
    for _ in range(n):
        solve()


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

Submission status: Accepted

Solution code:
import collections

n,m = list(map(int,input().split()))
n_list = list(map(int,input().split()))
eliminate_list = []

for i in range(0,m):
  a,b = list(map(int,input().split()))
  if n_list[a-1] > n_list[b-1]:
    eliminate_list.append(b-1)
  elif n_list[a-1] < n_list[b-1]:
    eliminate_list.append(a-1)
  else:
    eliminate_list.append(a-1)
    eliminate_list.append(b-1)

print(n - len(collections.Counter(eliminate_list)))

Submission status: Accepted

Solution code:
# C Peaks

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

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

print(goods.count(0))

Submission status: Accepted

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

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

print(cnt.count(1))

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
H=list(map(int,input().split()))
AB=[]
ans = [True]*N
for i in range(M):
    ls1=list(map(int,input().split()))
    AB.append(list(ls1))
    ls1.clear()
    #print(AB)
    if H[AB[i][0]-1] <= H[AB[i][1]-1]:
        ans[AB[i][0]-1] = False
    if H[AB[i][0]-1] >= H[AB[i][1]-1]:
        ans[AB[i][1]-1] = False
print(sum(ans))

Submission status: Accepted

Solution code:
import numpy as np
N, M = map(int, input().split())
H = list(map(int, input().split()))
A = list(map(int, input().split()) for _ in range(M))
A = list(map(list, set(map(tuple, A))))
#print(A)
#1本の道を辿っていける展望台の標高の最大値を求める
h = np.ones((N))

ans = 0
tmp = 0
for i in range(len(A)):
    if H[A[i][0]-1] > H[A[i][1]-1]:
        h[A[i][1]-1] = 0
    elif H[A[i][0]-1] < H[A[i][1]-1]:
        h[A[i][0]-1] = 0
    elif H[A[i][0]-1] == H[A[i][1]-1]:
        h[A[i][0]-1] = 0
        h[A[i][1]-1] = 0
#print(h)       
for i in range(N):
    if h[i]==1:
        ans+=1
print(ans)

Submission status: Accepted

Solution code:
#166_C
n, m = map(int, input().split())
h = list(map(int, input().split())) 
a = [0] * m
b = [0] * m

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

ans = 0
for i in range(n):
    if v[i] == []:
        ans += 1
    else:
        v[i].sort(reverse=True)
        if h[i] > v[i][0]:
            ans += 1
            
print(ans)

Submission status: Accepted

Solution code:
import numpy as np
n,m = map(int, input().split())
h = np.array([int(i) for i in input().split()])
h_i = np.ones((n))
for i in range(m):
    a,b = map(int, input().split())
    if h[a-1] < h[b-1]:
        h_i[a-1] = 0
    elif h[b-1] < h[a-1]:
        h_i[b-1] = 0
    elif h[a-1] == h[b-1]:
        h_i[a-1] = 0
        h_i[b-1] = 0
ans = (h_i > 0).sum()
print(ans)

Submission status: Accepted

Solution code:
#import numpy as np
#import math
#from decimal import *
#from numba import njit

#@njit
def main():
    N,M = map(int, input().split())
    H = list(map(int, input().split()))
    edges = []
    for i in range(M):
        A,B = map(int, input().split())
        edges += (A,B),
    
    good = [True]*N
    for A,B in edges:
        if H[A-1] > H[B-1]:
            good[B-1] = False
        elif H[A-1] < H[B-1]:
            good[A-1] = False
        else:
            good[A-1] = False
            good[B-1] = False
    print(len(list(filter(lambda b: b, good))))

main()

Submission status: Accepted

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

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

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

descending = list()
observatorys = [[None, []] for _ in range(N)]
for i in range(N):
  heapq.heapify(observatorys[i][1])

for i in range(M):
  
  if observatorys[A[i]-1][0] == None:
    observatorys[A[i]-1][0] = H[A[i]-1] * -1
    heapq.heappush(observatorys[A[i]-1][1], H[B[i]-1] * -1)
  else:
    heapq.heappush(observatorys[A[i]-1][1], H[B[i]-1] * -1)

  if observatorys[B[i]-1][0] == None:
    observatorys[B[i]-1][0] = H[B[i]-1] * -1
    heapq.heappush(observatorys[B[i]-1][1], H[A[i]-1] * -1)
  else:
    heapq.heappush(observatorys[B[i]-1][1], H[A[i]-1] * -1)

    
count = 0
for observatory in observatorys:
  if observatory[0] is None or observatory[0] < observatory[1][0]:
    count += 1

print(count)

Submission status: Accepted

Solution code:
#n=int(input())
n,m=map(int,input().split())
hl=list(map(int,input().split()))
#l=[list(map(int,input().split())) for i in range(n)]
dic={}
for i in range(m):
    a,b=map(int,input().split())
    if hl[a-1]<=hl[b-1]:
        dic[a]=False
    if hl[b-1]<=hl[a-1]:
        dic[b]=False

print(n-len(dic))

Submission status: Accepted

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

# それぞれの道の端点をgに記録
g = [[] for _ in range(N + 1)]
for _ in range(M):
    A, B = map(int, input().split())
    g[A].append(B)
    g[B].append(A)

ans = 0

for i in range(1, N + 1):

    # i番目の展望台について繋がっている展望台全てと順番に高さ比較
    # 一つでも勝てないものがあったらその展望台について考えるのは終わり、次に行く

    # 良いか悪いか
    tf = True

    for j in g[i]:
        if H[j] >= H[i]:
            tf = False
            break

    # 全てに勝ったらそれは「良い展望台」
    if tf == True:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
def getInts():
    return [ int(x) for x in input().split() ]

[N,M] = getInts()
H = getInts()
G = {}
for i in range(1,N+1):
    G[i] = set()
As = []
Bs = []
for i in range(M):
    [A,B] = getInts()
    G[A].add(B)
    G[B].add(A)

goodCount = 0
for i in range(1,N+1):
    if all([ H[nei-1] < H[i-1] for nei in G[i] ]):
        goodCount += 1
print(goodCount)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
arr=[0]+list(map(int,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)
ans=0
for v in range(1,n+1):
 for u in g[v]: #i番目の展望台から1本の道を通っていけるすべての展望台と高さを比較する
   if arr[u]>=arr[v]:
     break
 else: #i番目の展望台の高さが他のすべての展望台の高さより真に大きければ答えを1増やす
   ans+=1
print(ans)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
H = list(map(int, input().split()))
good_towers = [True] * n
for i in range(m):
    a, b = map(int, input().split())
    a_height = H[a-1]
    b_height = H[b-1]
    if a_height > b_height:
        good_towers[b-1] = False
    elif a_height < b_height:
        good_towers[a-1] = False
    else:
        good_towers[a-1] = False
        good_towers[b-1] = False
print(good_towers.count(True))

Submission status: Accepted

Solution code:
def II(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

N,M=MI()
H=LI()
ans=0
Michi=[[] for i in range(N)]
Ten=[1] *N
for i in range(M):
  a,b=MI()
  a-=1
  b-=1
  Michi[a].append(b)
  Michi[b].append(a)
for j in range(N):  
  for k in Michi[j]:
    if H[k]>=H[j]:
      Ten[j]=0
      break
ans=sum(Ten)
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
N,M=MI()
Ten=[1 for _ in range(N)]
Michi=[[] for _ in range(N)]
H=LI()
for i in range(M):
  a,b=MI()
  a-=1
  b-=1
  Michi[a].append(b)
  Michi[b].append(a)  
for i in range(N):
  for j in Michi[i]:
    if H[i]<=H[j]:
      Ten[i]=0
      break
ans=sum(Ten)
print(ans)

Submission status: Accepted

Solution code:
def main():
    n, m = map(int, input().split())
    to = [0]*(n+1)
    h = [None] + list(map(int, input().split()))
    for _ in range(m):
        a, b = map(int, input().split())
        to[a] = max(to[a], h[b])
        to[b] = max(to[b], h[a])
    ans = 0
    for i in range(1, n+1):
        if h[i] > to[i]:
            ans += 1
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def main():
    import sys
    def input(): return sys.stdin.readline().rstrip()
    n, m = map(int, input().split())
    h = list(map(int, input().split()))
    height = [0]*n
    for i in range(m):
        a, b = map(lambda x: int(x)-1, input().split())
        height[a] = max(height[a], h[b])
        height[b] = max(height[b], h[a])
    
    count = 0
    for i, j in zip(h, height):
        if i > j:
            count += 1
    print(count)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

print(sum(ok))

Submission status: Accepted

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

bad = []
for i in range(m):
  if h[l[i][0] - 1] > h[l[i][1] - 1]:
    bad.append(l[i][1])
  elif h[l[i][0] - 1] < h[l[i][1] - 1]:
    bad.append(l[i][0])
  else:
    bad.append(l[i][0])
    bad.append(l[i][1])

print(n - len(set(bad)))

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
def main():
    n, m = (int(i) for i in input().split())
    h = [int(i) for i in input().split()]
    roads = [(int(i) - 1 for i in input().split()) for _ in range(m)]

    nbors = [[] for _ in range(n)]
    for a, b in roads:
        nbors[a].append(b)
        nbors[b].append(a)

    ngood = 0
    for o in range(n):
        if all(h[o] > h[nb] for nb in nbors[o]):
            ngood += 1

    print(ngood)

main()

Submission status: Accepted

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

for x in range(M):
    if H[AB[x][0] -1] > H[AB[x][1] -1]:
        flag[AB[x][1] -1] = 0
    elif H[AB[x][0] -1] < H[AB[x][1] -1]:
        flag[AB[x][0] -1] = 0
    elif H[AB[x][0] -1] == H[AB[x][1] -1]:
        flag[AB[x][0] -1] = 0
        flag[AB[x][1] -1] = 0

print(flag.count(1))

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 i in range(m)]

good_list = [1]*n

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

print(good_list.count(1))

Submission status: Accepted

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

C = [1 for _ in range(N)]

for i in range(M):
  A, B = map(int, input().split())
  A -= 1
  B -= 1
  if H[A] >= H[B]:
    C[B] = 0
  if H[A] <= H[B]:
    C[A] = 0
  #print(C)
    
print(sum(C))

Submission status: Accepted

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

Submission status: Accepted

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

class Graph:
    def __init__(self, n, dictated=False, decrement=True, destroy=False, edge=[]):
        self.n = n
        self.dictated = dictated
        self.decrement = decrement
        self.destroy = destroy
        self.edge = [set() for _ in range(self.n)]
        self.parent = [-1]*self.n
        self.info = [-1]*self.n
        for x, y in edge:
            self.add_edge(x,y)

    def add_edge(self, x, y):
        if self.decrement:
            x -= 1
            y -= 1
        self.edge[x].add(y)
        if self.dictated == False:
            self.edge[y].add(x)

    def add_adjacent_list(self, i, adjacent_list):
        if self.decrement:
            self.edge[i] = set(map(lambda x:x-1, adjacent_list))
        else:
            self.edge[i] = set(adjacent_list)

    def bfs(self, start, goal=-1, time=0, save=False):
        """
        :param start: スタート地点
        :param goal: ゴール地点
        :param save: True = 前回の探索結果を保持する
        :return: （ループがあっても）最短距離。存在しなければ -1
        """
        if self.decrement:
            start -= 1
            goal -= 1
        p, t = start, time
        for q in self.edge[p]:
            if H[q] >= H[p]:
                return 0
        return 1

    def connection_counter(self):
        """
        :return: 連結成分の個数。有効グラフではあまり意味がない。
        """
        cnt = 0
        for start in range(self.n):
            cnt += self.bfs(start + self.decrement, save=False)
        return cnt


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

graph = Graph(N,dictated=False,decrement=True,destroy=False)

for _ in range(M):
    a, b = map(int, input().split())
    graph.add_edge(a,b)

print(graph.connection_counter())

Submission status: Accepted

Solution code:
n,m = map(int, input().split())
h = [0]
h.extend([int(i) for i in input().split()])
bld = [0]*(n+1)

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

print(bld.count(0)-1)

Submission status: Accepted

Solution code:
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

N,M=MI()
H=LI()
Michi=[[] for i in range(N)]
OK=[1]*N
for _ in range(M):
  a,b=MI()
  Michi[a-1].append(b-1)
  Michi[b-1].append(a-1)
for i in range(N):
  for j in Michi[i]:
    if H[j]>=H[i]:
      OK[i]=0
      break
ans=sum(OK)
print(ans)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
h = list(map(int, input().split()))
p = [False] + [True]*n
A = []
B = []
for i in range(m):
    a, b = map(int,input().split())
    A.append(a)
    B.append(b)

for i in range(m):
    if h[A[i] - 1] > h[B[i] - 1]:
        p[B[i]] = False
    elif h[A[i] - 1] < h[B[i] - 1]:
        p[A[i]] = False
    else:
        p[A[i]] = False
        p[B[i]] = False
    
ans = [i for i in range(n + 1) if p[i]]

print(len(ans))

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
h = list(map(int, input().split()))
p = [False] + [True]*n
A = []
B = []
for i in range(m):
    a, b = map(int,input().split())
    A.append(a)
    B.append(b)

for i in range(m):
    if h[A[i] - 1] > h[B[i] - 1]:
        p[B[i]] = False
    if h[A[i] - 1] < h[B[i] - 1]:
        p[A[i]] = False
    if h[A[i] - 1] == h[B[i] - 1]:
        p[A[i]] = False
        p[B[i]] = False
    
ans = [i for i in range(n + 1) if p[i]]

print(len(ans))

Submission status: Accepted

Solution code:
N,M=map(int, input().split())
H=list(map(int, input().split()))
G={}
for i in range(M):
  a,b=map(int,input().split())
  try:
    G[a].append(b)
  except:
    G[a] = [b]
  try:
    G[b].append(a)
  except:
    G[b] = [a]

count = 0
for i in range(N):
  h = H[i]
  if G.get(i+1):
  	g = G[i+1]
  else:
    continue
  for j in range(len(g)):
    if H[g[j]-1] >= h:
      count += 1
      break

print(N-count)

Submission status: Accepted

Solution code:
from sys import stdin
nii=lambda:map(int,stdin.readline().split())
lnii=lambda:list(map(int,stdin.readline().split()))

n,m=nii()
h=lnii()

tree=[[] for i in range(n)]
for i in range(m):
  a,b=nii()
  a-=1
  b-=1
  tree[a].append(h[b])
  tree[b].append(h[a])

ans=0
for i in range(n):
  if tree[i]:
    if  h[i]>max(tree[i]):
      ans+=1
  else:
    ans+=1

print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

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())
  l[a-1] = max(l[a-1], h[b-1])
  l[b-1] = max(l[b-1], h[a-1])

ans = 0
for i in range(n):
  if(h[i] > l[i]):
    ans += 1
print(ans)

Submission status: Accepted

Solution code:
def main():
    n, m = map(int, input().split())
    h = [None]+list(map(int, input().split()))
    to = [0]*(n+1)
    for _ in range(m):
        a, b = map(int, input().split())
        to[a] = max(to[a], h[b])
        to[b] = max(to[b], h[a])
    ans = [1 for i in range(1, n+1) if h[i] > to[i]]
    print(len(ans))
            
        

if __name__ == "__main__":
    main()