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:
import math
from sys import stdin,stdout
#% 998244353
from heapq import heapify,heappop,heappush

import collections
# T = int(stdin.readline())
# for i in range(T):
    #N=int(stdin.readline())
N,M=list(map(int,stdin.readline().split()))
hill=list(map(int,stdin.readline().split()))

dc=collections.defaultdict(list)
#vis=set()
for m in range(M):
    A,B=list(map(int,stdin.readline().split()))
    dc[A].append(B)
    dc[B].append(A)

ans=0
for k,ls in dc.items():

    f=0
    z=0
    for h in ls:

        if hill[k-1]<=hill[h-1]:
            f=1
            break

    if not f:
      #  print(k)
        ans+=1  
#print(ans)
ans+=(N-len(dc.keys()))
print(ans)

Submission status: Accepted

Solution code:
import bisect
import collections
import sys

sys.setrecursionlimit(100000)
input = sys.stdin.readline
ACMOD = 1000000007
INF = 1 << 62


def lmi():
    return list(map(int, input().split()))


def llmi(n):
    return [lmi() for _ in range(n)]


N, M = lmi()
H = lmi()

AB = llmi(M)
flag = [1] * N
for a, b in AB:
    a = a - 1
    b = b - 1
    ha = H[a]
    hb = H[b]
    if ha >= hb:
        flag[b] = 0
    if hb >= ha:
        flag[a] = 0
print(sum(flag))

Submission status: Accepted

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

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

path = [[] for i in range(n)]
for pair in path_:
    path[pair[0]-1].append( pair[1])
    path[pair[1]-1].append( pair[0])

count = 0
for i in range(n):
    flag = 1
    if path[i] != []:
        for j in path[i]:
            if hight[i] <= hight[j-1]:
                flag = 0
                break
    if flag:
        count += 1

print(count)

Submission status: Accepted

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

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

cnt = 0
flag = {}
for i in range(N):
    flag[i] = True

for i in d:
    A = i[0]
    B = i[1]
    if not(H[A] > H[B] and flag[A] == True):
        flag[A] = False
    if not(H[B] > H[A] and flag[B] == True):
        flag[B] = False
print(list(flag.values()).count(True))

Submission status: Accepted

Solution code:
def main():
    N, M = map(int, input().split())
    Hn_list = [A for A in input().split()]
    Hn_list = list(map(int, Hn_list))
    count_list = [1] * N
    #print(count_list)
    Hn_pop_list = []
    for i in range(M):
        A, B = map(int, input().split())
        temp_a = int(A - 1)
        temp_b = int(B - 1)
        if Hn_list[temp_a] > Hn_list[temp_b]:
            count_list[temp_b] = 0
        elif Hn_list[temp_b] > Hn_list[temp_a]:
            count_list[temp_a] = 0
        elif Hn_list[temp_b] == Hn_list[temp_a]:
            count_list[temp_a] = 0
            count_list[temp_b] = 0
    #print(Hn_list)
    #print(count_list)
    #print(count_list.count(0))
    print(len(Hn_list)-count_list.count(0))
    #print(Hn_list)
    #print(Hn_pop_list)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
h = [int(x) for x in input().split()]
ans = [True] * n
for i in range(m):
    a, b = map(int, input().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] = False
        ans[b-1] = False
print(ans.count(True))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import numpy as np

n, m = map(int, input().split())
h = np.array(input().split(), dtype='int')
bad_tower = []

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

    if ha > hb:
        bad_tower.append(b)
    elif ha < hb:
        bad_tower.append(a)
    elif ha == hb:
        bad_tower.append(a)
        bad_tower.append(b)

bad_tower = np.unique(bad_tower)

ans = n - len(bad_tower)

print(ans)

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

Submission status: Accepted

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

Submission status: Accepted

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

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

all_l = list(range(1,N+1))
lose_l = []
while M > 0:
    a,b = map(int, input().split())
    if h_l[a-1] > h_l[b-1]:
        lose_l.append(b)
    elif h_l[a-1] < h_l[b-1]:
        lose_l.append(a)
    else:
        lose_l.append(b)
        lose_l.append(a)
    M -= 1

result = list(set(all_l) - set(lose_l))
print(len(result))

Submission status: Accepted

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

AB_unique=list(map(list, set(map(tuple, AB))))

AB_road=[[] for i in range(N)]
for AB in AB_unique:
    if H[AB[0]-1] > H[AB[1]-1]:
        AB_road[AB[1]-1].append(AB[0])
    elif H[AB[0]-1] < H[AB[1]-1]:
        AB_road[AB[0]-1].append(AB[1])
    else:
        AB_road[AB[1]-1].append(AB[0])
        AB_road[AB[0]-1].append(AB[1])

print(AB_road.count([]))

Submission status: Accepted

Solution code:
import collections

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

z = zip(a,b)
lis = [0]*n

for i,j in z:

    if h[i-1] > h[j-1]:
        lis[j-1] = 1
    elif h[i-1] < h[j-1]:
        lis[i-1] = 1
    else:
        lis[i-1]=1
        lis[j-1]=1

print(collections.Counter(lis)[0])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
def main():
    N,M = map(int, input().split())
    H = list(map(int, input().split()))
    ans = []
    for _ in range(N):
        ans.append(1)
    for i 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[B-1] = 0
            ans[A-1] = 0
    print(sum(ans))

if __name__ == '__main__':
    main()

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

Submission status: Accepted

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

par = [0 for i in range(N)]

for i in range(M):
    A, B = map(int, input().split())
    if H_li[B-1]>H_li[A-1]:
        par[A-1] = 1
    elif H_li[A-1]>H_li[B-1]:
        par[B-1] = 1
    else:
        par[A-1] = 1
        par[B-1] = 1

print(N-sum(par))

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
h = list(map(int, input().split()))
l = [1] * n
for i in range(m):
    a, b = map(int, input().split())
    if h[a - 1] < h[b - 1] and l[b - 1] != 0:
        l[b - 1] += 1
        l[a - 1] = 0
    elif h[a - 1] > h[b - 1] and l[a - 1] != 0:
        l[a - 1] += 1
        l[b - 1] = 0
    else:
        l[a - 1] = 0
        l[b - 1] = 0
c = 0        
for i in range(n):
    if l[i] != 0:
        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()]

route=[1]*n

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

    if h[b]>=h[a]:
        route[a]=0
    if h[a]>=h[b]:
        route[b]=0



print(sum(route))

Submission status: Accepted

Solution code:
def get_unique_list(seq):
    seen = []
    return [x for x in seq if x not in seen and not seen.append(x)]

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

AB_unique=list(map(list, set(map(tuple, AB))))

AB_road=[True]*N
for AB in AB_unique:
    if H[AB[0]-1] > H[AB[1]-1]:
        AB_road[AB[1]-1]=False
    elif H[AB[0]-1] < H[AB[1]-1]:
        AB_road[AB[0]-1]=False
    else:
        AB_road[AB[1]-1]=False
        AB_road[AB[0]-1]=False

print(AB_road.count(True))

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

Submission status: Accepted

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

# create graph
g = []
for i in range(n):
    g.append(set())

for i in range(m):
    g[l[i][0]-1].add(l[i][1]-1)
    g[l[i][1]-1].add(l[i][0]-1)

# search
ans = 0
for i in range(n):
    if len(g[i]) == 0:
        ans += 1
        continue
    else:
        flag = True
        gt = tuple(g[i])
        for j in range(len(g[i])):
            if h[i] <= h[gt[j]]:
                flag = False
                break
        if flag:
            ans += 1

print(ans)

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

ans = [1] * (n)
route = [1] * (n)
for i in range(len(ab)):
    a, b = ab[i]
    if H[a-1] <= H[b-1]:
      ans[a-1] = 0

    if H[b-1] <= H[a-1]:
      ans[b-1] = 0
    
print(sum(ans))

Submission status: Accepted

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

A = []
B = []

for i in range(m):
    a, b = input().split()
    A.append(int(a))
    B.append(int(b))
    
    
for j in range(m):
    if h[A[j]-1] > h[B[j]-1]:
        s[B[j]-1] = 0
    elif h[A[j]-1] < h[B[j]-1]:
        s[A[j]-1] = 0
    elif h[A[j]-1] == h[B[j]-1]:
        s[A[j]-1] = 0
        s[B[j]-1] = 0
        
print(sum(s))

Submission status: Accepted

Solution code:
f=lambda:map(int,input().split())
n, m = map(int, input().split())
l=list(map(int, input().split()))
t=[1]*n
for _ in range(m):
  a,b = map(int, input().split())
  if l[a-1]<=l[b-1]:
    t[a-1]=0
  if l[b-1]<=l[a-1]:
    t[b-1]=0
print(sum(t))

Submission status: Accepted

Solution code:


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

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

# a = [0] * m
# b = [0] * m

ma = [0]*n


for i in range(m):
    a, b = map(int,input().split())
    a -= 1; b -= 1
    ma[a] = max(ma[a],h[b])
    ma[b] = max(ma[b],h[a])

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

print(ans)

Submission status: Accepted

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

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

ans = 0
for i in range(N):
  f = True
  for j in range(len(s[i])):
    if H[i] <= H[s[i][j]]:
      f = False
    
  if f:
    ans += 1
    
print(ans)

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 = map(list, zip(*ab))

cnt = 0
removeList = []

for i in range(len(a)):
  if (H[a[i]-1] > H[b[i]-1]):
    removeList.append(b[i])
  elif (H[a[i]-1] < H[b[i]-1]):
    removeList.append(a[i])
  else:
    removeList.append(a[i])
    removeList.append(b[i])

set(removeList)
print(N - len(set(removeList)))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
N, M = [int(str) for str in input().strip().split()]
H = [int(str) for str in input().strip().split()]
AB = [[int(str) - 1 for str in input().strip().split()] for _ in range(M)]


def solve():
    G = [0] * N
    for a, b in AB:
        G[a] = max(G[a], H[b])
        G[b] = max(G[b], H[a])

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

    print(ans)


solve()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import numpy as np

n, m = map(int, input().split())
h = np.array(input().split(), dtype='int')
bad_tower = np.zeros((n), dtype='int')

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

    if ha > hb:
        bad_tower[b-1] = 1
    elif ha < hb:
        bad_tower[a-1] = 1
    elif ha == hb:
        bad_tower[a-1] = 1
        bad_tower[b-1] = 1

ans = n - np.sum(bad_tower)

print(ans)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
h=list(map(int,input().split()))
good=[True]*n
for i in range(m):
    a,b=map(int,input().split())
    a-=1;b-=1
    if h[a]<h[b]:
        good[a]=False
    elif h[b]<h[a]:
        good[b]=False
    elif h[b]==h[a]:
        good[a]=False
        good[b]=False
print(good.count(True))

Submission status: Accepted

Solution code:
from sys import stdin,stdout
n,m=map(int,stdin.readline().split())
H=list(map(int,stdin.readline().split()))
L=[0]*n
for i in range(m):
	a,b=map(int,stdin.readline().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
		
stdout.write(str(ans))

Submission status: Accepted

Solution code:
def resolve():
    n, m = map(int, input().split())
    hhh = list(map(int, input().split()))
    nice = [1] * n

    for _ in range(m):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        ha = hhh[a]
        hb = hhh[b]
        if ha <= hb:
            nice[a] = False
        if ha >= hb:
            nice[b] = False

    print(sum(nice))


resolve()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7 # 998244353
input=lambda:sys.stdin.readline().rstrip()
def resolve():
    n, m = map(int,input().split())
    H = list(map(int,input().split()))
    E = [[] for _ in range(n)]
    for _ in range(m):
        u, v = map(int,input().split())
        u -= 1; v -= 1
        E[u].append(v)
        E[v].append(u)

    res = [None] * n
    for v in range(n):
        res[v] = all(H[v] > H[nv] for nv in E[v])
    print(sum(res))
resolve()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
H = list(map(int, input().split()))
A = []
B = []
for i in range(M):
  a, b = (map(int, input().split()))
  A.append(a)
  B.append(b)

flg = [1] * N
for i in range(M):
  if flg[A[i]-1] == 1 and H[A[i]-1] <= H[B[i]-1]:
    flg[A[i]-1] = 0

for i in range(M):
  if flg[B[i]-1] == 1 and H[A[i]-1] >= H[B[i]-1]:
    flg[B[i]-1] = 0

print(sum(flg))

Submission status: Accepted

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

# from collections import deque

def linput(_t=int):
    return list(map(_t, input().split()))

def gcd(n,m):
    while m: n,m = m, n%m
    return n

def lcm(n,m): return n*m//gcd(n,m)

def main():
    # N = int(input())
    N,M = linput()
    vH = linput()
    vE = [linput() for _ in [0,]*M]

    vH = [0,] + vH
    vV = [0,] + [1,]*N

    # res = 0
    # for s in S.split("-"):
    #     res = max(res, len(s))

    for a,b in vE:
        ha, hb = vH[a], vH[b]
        if ha <= hb:
            vV[a] = 0
        if ha >= hb:
            vV[b] = 0
        
    res = sum(vV)


    # res = 0
    print(res)

    # print(("No","Yes")[res%2])


main()

Submission status: Accepted

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

edges = [[] for _ in range(N)]
for _ in range(M):
    fr, to = map(lambda a: int(a) - 1, input().split())
    edges[fr].append(to)
    edges[to].append(fr)

ans = 0
for i, h in enumerate(H):
    mx = 0
    for to in edges[i]:
        mx = max(mx, H[to])
    if mx < h:
        ans += 1

print(ans)

Submission status: Accepted

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

o_height = input().split()
result = []
for i in range(N):
    result.append(True)

while(M):
    road = input().split()
    if int(o_height[int(road[0])-1]) < int(o_height[int(road[1])-1]):
        result[int(road[0])-1] = False
    elif int(o_height[int(road[0])-1]) == int(o_height[int(road[1])-1]):
        result[int(road[0])-1] = False
        result[int(road[1])-1] = False
    else:
        result[int(road[1])-1] = False
    M-=1



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

Submission status: Accepted

Solution code:
# import math
# from collections import Counter

# N = int(input()) # 1行, 単数
# arg = list(map(int, input().split())) # 1行, 配列
# D = Counter(arg) # 出現数カウント

# print('Yes')
# print('No')
# print()


N,M = map(int, input().split()) # 1行, 配列
H = list(map(int, input().split())) # 1行, 配列

AB={}

while True:
  try:
    A,B = map(int, input().split())
    AB.setdefault(A, []).append(H[B-1])
    AB.setdefault(B, []).append(H[A-1])
  except:
    break;

good = 0

for i, item in enumerate(H):

  try:
    targetLoad = AB[i+1]
    if max(targetLoad) < item:
      good = good + 1
  except:
    good = good + 1

print(good)

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
H = list(map(int,input().split()))
alllist = []
notwinner = []
for i in range(M):
    ab = list(map(int,input().split()))
    if H[ab[0]-1] > H[ab[1]-1]:
        notwinner.append(ab[1])
    elif H[ab[0]-1] < H[ab[1]-1]:
        notwinner.append(ab[0])
    else:
        notwinner.append(ab[0])
        notwinner.append(ab[1])
wtou = N - len(set(notwinner))
print(wtou)

Submission status: Accepted

Solution code:
def main():
    import sys
    N,M=list(map(int,sys.stdin.readline().split()))
    H=list(map(int,sys.stdin.readline().split()))
    lsts=[[] for _ in range(N)]
    st=set()
    for i in range(M):
        A,B=list(map(int,sys.stdin.readline().split()))
        if (A,B) not in st:
            lsts[A-1].append(H[B-1])
            lsts[B-1].append(H[A-1])
            st.add((A,B))
            
    output=0
    for i,lst in enumerate(lsts):
        if len(lst)==0:
            output+=1
        elif max(lst)<H[i]:
            output+=1
    print(output)


    

main()

Submission status: Accepted

Solution code:
import collections

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

gb = [1]*n;
for i in range(m):
    a,b = map(int, input().split())
    a -= 1
    b -= 1
    if h[a] == h[b]:
        gb[a] = 0
        gb[b] = 0

    elif h[a]<h[b]:
        gb[a] = 0
    else:
        gb[b] = 0

l = collections.Counter(gb)
print(l[1])

Submission status: Accepted

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

for i in range(M):
    if H[int(AB[i][0]) - 1] > H[int(AB[i][1]) - 1]:
        ans_list[int(AB[i][1]) - 1] = 0
    elif H[int(AB[i][0]) - 1] < H[int(AB[i][1]) - 1]:
        ans_list[int(AB[i][0]) - 1] = 0
    elif H[int(AB[i][0]) - 1] == H[int(AB[i][1]) - 1]:
        ans_list[int(AB[i][0]) - 1] = 0
        ans_list[int(AB[i][1]) - 1] = 0

print(sum(ans_list))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1 << 25)
read = sys.stdin.readline
ra = range
enu = enumerate


def read_ints():
    return list(map(int, read().split()))


def read_a_int():
    return int(read())


def read_tuple(H):
    '''
    H is number of rows
    '''
    ret = []
    for _ in range(H):
        ret.append(tuple(map(int, read().split())))
    return ret


def read_col(H):
    '''
    H is number of rows
    A列、B列が与えられるようなとき
    ex1)A,B=read_col(H)    ex2) A,=read_col(H) #一列の場合
    '''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return tuple(map(list, zip(*ret)))


def read_matrix(H):
    '''
    H is number of rows
    '''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return ret
    # return [list(map(int, read().split())) for _ in range(H)] # 内包表記はpypyでは遅いため


MOD = 10**9 + 7
INF = 2**31  # 2147483648 > 10**9
# default import
from collections import defaultdict, Counter, deque
from operator import itemgetter
from itertools import product, permutations, combinations
from bisect import bisect_left, bisect_right  # , insort_left, insort_right
from math import gcd

# グラフを作って周り見て一番高ければおk？
N, M = read_ints()
H = read_ints()
graph = defaultdict(lambda: [])
for _ in range(M):
    a, b = read_ints()
    a -= 1
    b -= 1
    graph[a].append(b)
    graph[b].append(a)
ans = 0
for i in range(N):
    for adj in graph[i]:
        if H[i] <= H[adj]:
            break
    else:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(300000)

def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LMI(): return list(map(int, sys.stdin.readline().split()))
MOD = 10 ** 9 + 7
INF = float('inf')


N, M = MI()
H = LMI()
nl = [list() for _ in range(N)]
for _ in range(M):
    a, b = MI()
    a -= 1
    b -= 1
    nl[a].append(b)
    nl[b].append(a)

ans = 0
for i in range(N):
    good = True
    for j in nl[i]:
        if H[i] <= H[j]:
            good = False
            break
    if good:
        ans += 1
print(ans)

Submission status: Accepted

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

for i in range(0, int(m)):
    a, b = map(int, input().split())
    a_int = int(h[int(a)-1])
    b_int = int(h[int(b)-1])

    if (a_int < b_int):
        l[a - 1] = 0
    
    if (a_int > b_int):
        l[b - 1] = 0
    
    if (l[a-1] == 1):
        if (a_int == b_int):
            l[a - 1] = 0
            l[b - 1] = 0
    elif (l[b-1] == 1):
        if (a_int == b_int):
            l[a - 1] = 0
            l[b - 1] = 0 
       
cnt = 0
for k in range(0, len(l)):
    if(l[k]==1):
        cnt+=1

print(cnt)

Submission status: Accepted

Solution code:


N_ko, M_hon = map(int, input().split())
Heights = list(map(int, input().split()))
# indexs = [i for i in range(1, N_ko + 1)]
indexs=[]

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

    h_a = Heights[a]
    h_b = Heights[b]


    if (h_a > h_b):
        indexs.append(b)

    elif (h_b > h_a):
        indexs.append(a)
    
    else:
        indexs.append(a)
        indexs.append(b)

ans = N_ko - len(set(indexs))


print(ans)

Submission status: Accepted

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



graph = [[] for _ in range(N+1)]
for edge in edges:
    graph[edge[0]].append(edge[1])
    graph[edge[1]].append(edge[0])

ans = []

for i in range(1,N+1):
    can = graph[i]
    hights = []
    for j in can:
        hights.append(H[j-1])
    if len(hights) == 0:
        ans.append(i)
    else:
        h = max(hights)
        if H[i-1] > h:
            ans.append(i)

print(len(set(ans)))

Submission status: Accepted

Solution code:
n, m = list(map(int, input().split()))
h = list(map(int, input().split()))
d = {}
for i in range(m):
    a, b = list(map(int, input().split()))
    try:
        d[a-1].append(b-1)
    except KeyError:
        d[a-1] = [b-1]
    try: 
        d[b-1].append(a-1)
    except:
        d[b-1] = [a-1]
cnt = 0
for k, v in d.items():
    flag = True
    for i in set(v):
        if h[k] > h[i]:
            pass
        else:
            flag = False
    if flag is True:
        cnt += 1
print(cnt+(n-len(d.keys())))

Submission status: Accepted

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

for _ in range(m):
    a,b = map(int, input().split())
    nets[a - 1] = max(nets[a-1], h[b-1])
    nets[b - 1] = max(nets[b-1], h[a-1])

ans = 0

#print(nets)

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

print(ans)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
Height = [int(i) for i in input().split()]
check = [1] * N

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



for i in range(M):
    if Height[A_List[i] - 1] > Height[B_List[i] - 1]:
        check[B_List[i] - 1] = 0
    elif Height[A_List[i] - 1] < Height[B_List[i] - 1]:
        check[A_List[i] - 1] = 0
    elif Height[A_List[i] - 1] == Height[B_List[i] - 1]:
        check[B_List[i] - 1] = 0
        check[A_List[i] - 1] = 0


print(sum(check))

Submission status: Accepted

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




for i in A:
    #print(i)
    if H[i[0]-1] > H[i[1]-1]:
        res.append(i[1])
    elif H[i[0]-1] == H[i[1]-1]:
        res.append(i[0])
        res.append(i[1])
    else:
        res.append(i[0])
print(N-len(set(res)))

Submission status: Accepted

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

Submission status: Accepted

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


def solve(N: int, M: int, H: "List[int]", A: "List[int]", B: "List[int]"):
    l = [[] for i in range(N)]
    for i in range(M):
        l[A[i] - 1].append(B[i])
        l[B[i] - 1].append(A[i])
    nl = [list(set(x)) for x in l]
    cnt = 0
    for i, v in enumerate(nl):
        flg = True
        for j in v:
            if H[i] <= H[j - 1]:
                flg = False
                break
        if flg:
            cnt += 1
    print(cnt)
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    H = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    A = [int()] * (M)  # type: "List[int]"
    B = [int()] * (M)  # type: "List[int]"
    for i in range(M):
        A[i] = int(next(tokens))
        B[i] = int(next(tokens))
    solve(N, M, H, A, B)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n,m = [int(j) for j in input().split(" ")]
height = [int(j) for j in input().split(" ")]
neighbours = [[] for j in range(n)]
for _ in range(m):
    start, end = [int(j)-1 for j in input().split(" ")]
    neighbours[start].append(end)
    neighbours[end].append(start)

good = 0
for i in range(n):
    if len(neighbours[i]) == 0:
        good += 1
    else:
        if height[i] > max([height[j] for j in neighbours[i]]):
            good += 1

print(good)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
H = list(map(int, input().split()))
routes = dict()
for i in range(M):
    A, B = map(int, input().split())
    if routes.get(A) is None:
        routes[A] = set([B])
    else:
        routes[A].add(B)
    if routes.get(B) is None:
        routes[B] = set([A])
    else:
        routes[B].add(A)

#print(routes)
answer = 0
for i in range(1, N + 1):
    if routes.get(i) is None:
        answer += 1
    else:
        tmp = 0
        for j in routes.get(i):
            tmp = max(tmp, H[j - 1])
        if H[i - 1] > tmp:
            answer += 1
print(answer)

Submission status: Accepted

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

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