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:
def resolve():
    N, M = map(int, input().split())
    H = tuple(map(int, input().split()))
    C = [[] for i in range(N)]
    count = 0
    for i in range(M):
        A, B = map(int, input().split())
        C[A-1].append(B-1)
        C[B-1].append(A-1)
    for i in range(N):
        idx = 0
        if len(C[i]) == 0:
            count += 1
        for j in C[i]:
            idx += 1
            if H[i] <= H[j]:
                break
            if idx == len(C[i]):
                count += 1
    print(count)

if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
H = list(map(int, input().split()))
connected = [list() for _ in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    connected[a-1].append(H[b-1])
    connected[b-1].append(H[a-1])

result = 0
for i, c in enumerate(connected):
    if len(c) == 0 or H[i] > max(c):
        result += 1
print(result)

Submission status: Accepted

Solution code:
import numpy as np

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)
  
link = {}
for i in range(M):
  if A[i] in link.keys():
    link[A[i]].append(H[B[i]-1])
  else:
    link[A[i]] = [H[B[i]-1]]
  if B[i] in link.keys():
    link[B[i]].append(H[A[i]-1])
  else:
    link[B[i]] = [H[A[i]-1]]
  
ans = 0
for i in range(1, N+1, 1):
  if i not in link.keys():
    ans += 1
  else:
    if H[i-1] > max(link[i]):
      ans += 1
      
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
def resolve():
    n, m = map(int, input().split())
    h = list(map(int, input().split()))

    d = defaultdict(list)
    for _ in range(m):
        ai, bi = map(lambda x: int(x) - 1, input().split())
        d[ai].append(bi)
        d[bi].append(ai)

    bad = []
    ans = 0
    for i in range(n):
        if -1 in d[i]:
            continue
        flg = True
        for nei_peak in d[i]:
            if h[i] <= h[nei_peak]:
                flg = False
                break

        if flg:
            ans += 1
            for nei_peak in d[i]:
                d[nei_peak] = [-1]

    print(ans)
resolve()

Submission status: Accepted

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

p = []

ih = dict(zip(li, h))

for i in range(m):
    a, b = map(int,input().split())
    c = ih[a]
    d = ih[b]
    if c>d:
        p.append(b)
    elif d>c:
        p.append(a)
    else:
        p.append(a)
        p.append(b)

print(n-len(set(p)))

Submission status: Accepted

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

high = []
low = []
for i in range(M):
    if H[hikaku[i][0]-1] > H[hikaku[i][1]-1]:
        high.append(hikaku[i][0])
        low.append(hikaku[i][1])
    elif H[hikaku[i][0]-1] < H[hikaku[i][1]-1]:
        high.append(hikaku[i][1])
        low.append(hikaku[i][0])
    else:
        low.append(hikaku[i][0])
        low.append(hikaku[i][1])

Ans = len(set(high)) - len(set(high) & set(low)) + (N - len(set(high+low)))

print(Ans)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
is_good = [True] * N
H = list(map(int, input().split()))
for _ in range(M):
    A, B = map(lambda n: int(n) - 1, input().split())
    if H[A] <= H[B]:
        is_good[A] &= False
    if H[A] >= H[B]:
        is_good[B] &= False

print(sum(is_good))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n,m = map(lambda x:int(x),input().split())
heights = list(map(lambda x:int(x),input().split()))
good = 0
obscon = {}
for i in range(n):
  obscon[i] = [-1]
for i in range(m):
  a,b = map(lambda x:int(x)-1,input().split())
  obscon[a].append(b)
  obscon[b].append(a)
for i in range(n):
  if obscon[i] == [-1]:
    good += 1
  else:
    obscon[i].remove(-1)
    tall = 1
    for j in obscon[i]:
      if heights[i]>heights[j]:
        tall = min(tall,1)
      else:
        tall = min(tall,0)
    if tall == 1:
      good += 1
print(good)

Submission status: Accepted

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

G = [[] for _ in range(n)]
for _ in range(m):
    a, b = map(int, input().split())
    G[a-1].append(b-1)
    G[b-1].append(a-1)
#print(G)
ans = 0
for i in range(n):
    maxh = 0
    for gi in G[i]:
        maxh = max(h[gi], maxh)
    if maxh < h[i]:
        ans += 1
    #print(maxh, h[i])

print(ans)

Submission status: Accepted

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

d = []

h_list = [int(s) for s in input().split()]

for (i, h) in enumerate(h_list):
    d.append({
        'h': h,
        'max': 0
    })

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

    if d[a]['max'] < d[b]['h']:
        d[a]['max'] = d[b]['h']

    if d[b]['max'] < d[a]['h']:
        d[b]['max'] = d[a]['h']

ans = 0

for e in d:
    if e['max'] < e['h']:
        ans += 1

print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
import math

n, m = [int(x) for x in sys.stdin.readline().rstrip().split()]
h = [int(x) for x in sys.stdin.readline().rstrip().split()]

ipt = sys.stdin.readlines()
dic = {str(x):True for x in range(1, n + 1)}

for x in ipt:
  a, b = [int(y) for y in x.split()]
  _a = h[a - 1]
  _b = h[b - 1]
  if _a  > _b:
    dic[str(b)] = False
  elif _a == _b:
    dic[str(a)] = False
    dic[str(b)] = False
  else:
    dic[str(a)] = False

li = list(dic.values())
print(li.count(True))

Submission status: Accepted

Solution code:
n, m = list(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())
x = [0] * n
for i in range(m):
    if h[a[i]-1] < h[b[i]-1]:
        x[a[i]-1] += 1
    elif h[a[i]-1] == h[b[i]-1]:
        x[a[i]-1] += 1
        x[b[i]-1] += 1
    else:
        x[b[i]-1] += 1
print(x.count(0))

Submission status: Accepted

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


count=0
for i in range(n):
    if h[i] > max(miti[i]):
        count+=1
print(count)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from heapq import heappush, heappop, heapify
from collections import deque, defaultdict, Counter
import itertools
from itertools import permutations, combinations, accumulate, product, combinations_with_replacement
import sys
import bisect
import string
import math
import time


def I(): return int(input())


def S(): return input()


def MI(): return map(int, input().split())


def MS(): return map(str, input().split())


def LI(): return [int(i) for i in input().split()]


def LI_(): return [int(i)-1 for i in input().split()]


def StoI(): return [ord(i)-97 for i in input()]


def ItoS(nn): return chr(nn+97)


def input(): return sys.stdin.readline().rstrip()


def debug(table, *args):
    ret = []
    for name, val in table.items():
        if val in args:
            ret.append('{}: {}'.format(name, val))
    print(' | '.join(ret), file=sys.stderr)


yn = {False: 'No', True: 'Yes'}
YN = {False: 'NO', True: 'YES'}
MOD = 10**9+7
inf = float('inf')
IINF = 10**10
l_alp = string.ascii_lowercase
u_alp = string.ascii_uppercase
ts = time.time()
sys.setrecursionlimit(10**6)
nums = ['1', '2', '3', '4', '5', '6', '7', '8', '9', '10']

show_flg = False
# show_flg = True

ans = []

def bfs(graph, initial, H):
    global ans
    n = len(graph) - 1
    dist = [-1] * (n + 1)
    q = deque([initial])
    visited = [False] * (n + 1)
    visited[initial] = True
    dist[initial] = 0

    while len(q) != 0:
        edge = q.popleft()
        nxt = graph[edge]

        for i, e in enumerate(nxt):
            if visited[e] is False:
                if H[initial] <= H[e]:
                    return 0
                q.append(e)
                dist[e] = dist[edge] + 1
                visited[e] = True

    return 1


def main():
    global ans
    N, M = MI()
    H = LI()
    graph = [[] for i in range(N+1)]

    for i in range(M):
        a, b = MI()
        graph[a-1].append(b-1)
        graph[b-1].append(a-1)

    ans = [-1] * N

    ret = 0
    for i in range(N):
        d = bfs(graph, i, H)
        print(i, d)
    print(ret)

def main():
    N, M = MI()
    H = LI()
    A = [0] * M
    B = [0] * M

    H_G = [-1 for i in range(N)]

    for i in range(M):
        A[i], B[i] = MI()

    for i in range(M):
        H_G[A[i]-1] = max(H_G[A[i]-1], H[B[i]-1])
        H_G[B[i]-1] = max(H_G[B[i]-1], H[A[i]-1])

    ans = 0

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

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

ans = set()

for i in range(N):
    if len(X[i]) == 0:
        ans.add(i)
    else:
        if all(H[i] > H[j-1] for j in X[i]):
            ans.add(i)

print(len(ans))

Submission status: Accepted

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

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

#print(d)
ans = 0
for i in range(1, N + 1):
  cnt = 0
  for j in d[i]:
    if H[j - 1] >= H[i - 1]:
      cnt +=1
      break
  if cnt ==0:
    ans +=1
print(ans)

Submission status: Accepted

Solution code:
N, M = map(int, input().split(" "))
Hs = list(map(int, input().split(" ")))
candidate = set(range(1, N+1))
for _ in range(M):
    i, j = map(int, input().split(" "))
    if Hs[i - 1] >= Hs[j - 1]:
        # jは良い展望台ではない
        candidate.discard(j)
    if Hs[j - 1] >= Hs[i - 1]:
        # iは良い展望台ではない
        candidate.discard(i)
print(len(candidate))

Submission status: Accepted

Solution code:
#coding: utf-8

N, M = map(int, input().split())
H = list(map(int, input().split()))
nodes = [set() for i in range(N)]
for i in range(M):
    a, b = map(int, input().split())
    nodes[a-1].add(b-1)
    nodes[b-1].add(a-1)

count = 0
for i in range(N):
    height = H[i]
    if all(map(lambda x: H[x] < height, nodes[i])):
        count += 1
print(count)

Submission status: Accepted

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

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

h = [1] * N

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

print(h.count(1))

Submission status: Accepted

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

for i in range(1,n+1):
    T[i] = "good"

for _ in range(m):
    a,b = map(int,input().split())
    if H[a-1] <= H[b-1]:
        T[a] = "bad"
    if H[a-1] >= H[b-1]:
        T[b] = "bad"

#print (T)
print (list(T.values()).count("good"))

Submission status: Accepted

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

  ah=H[a-1]
  bh=H[b-1]
  if ah>bh:
    good[b-1]=0
  elif ah<bh:
    good[a-1]=0
  else:
    good[a-1]=0
    good[b-1]=0
counter=0
for i in good:
  if i==1:
    counter=counter+1
print(counter)

Submission status: Accepted

Solution code:
from math import factorial as fact
import math
import sys
import itertools
import numpy as np
from collections import Counter
import datetime


#入力:N(int:整数)
def input1():
	return int(input())

#入力:N,M(int:整数)
def input2():
	return map(int,input().split())

#入力:[n1,n2,...nk](int:整数配列)
def input_array():
	return list(map(int,input().split()))

def keta(N):
	return len(str(N))


def input_daytime(input_time):
	time,distance=input_time.split()
	t=time.split(":")
	se=str(t[-1]).split(".")
	dt1 = datetime.timedelta(hours=int(t[0]),minutes=int(t[1]),seconds=int(se[0]),milliseconds=int(se[1]))
	return dt1

def combinations(n,r):
	return list(itertools.combinations(range(n),r))



def all_sets(num_list):
	subsets=[]
	for i in range(2,len(num_list) + 1):
		for c in combinations(num_list, i):
			subsets.append(c) 
	return subsets

#公約数の列挙
def ch(x1):
	cf=[]
	for i in range(2,math.sqrt(x1)+1):
		if x1 % i==0:
			cf.append(i)
	return cf

def CountOneRoots(x,y):
	#x:縦，y:横
	return fact(x+y)/fact(x)/fact(y)

# 素因数分解
def factorization(n):
	tmp=n
	count=0
	for i in range(2,int(n**0.5)+2):
		if tmp%i==0:
			cnt=0
			while tmp%i==0:
				cnt+=1
				tmp//=i
			count+=1
	if tmp!=1:
		count+=1

	return count
			


n,m=input2()
H=input_array()
# G=[[0]*n]*n #グラフ
counts=[]
la=[1]*n
for i in range(m):
	a,b=input2()
	if H[a-1]>H[b-1]:
		la[b-1]=0
	elif H[a-1]<H[b-1]:
		la[a-1]=0
	else:
		la[a-1]=0
		la[b-1]=0



print(sum(la))

Submission status: Accepted

Solution code:
n, m = list(map(int, input().split()))
heights = list(map(int, input().split()))
roads = {}
for x in range(m):
    road = list(map(int, input().split()))
    if road[0] not in roads.keys():
        roads[road[0]] = []
    if road[1] not in roads.keys():
        roads[road[1]] = []
    roads[road[0]].append(road[1])
    roads[road[1]].append(road[0])
g = 0
flag = False
for y in range(1, n+1):
    if y not in roads.keys() or len(roads[y]) == 0:
        g += 1
        pass
    else:
        for z in roads[y]:
            if heights[z - 1] >= heights[y - 1]:
                flag = True
                break
        if flag:
            flag = False
            continue
        else:
            g += 1
print(g)

Submission status: Accepted

Solution code:
from collections import deque

def main():
    N,M=map(int,input().split())
    H=[int(x) for x in input().split()]
    S=[list(map(int,input().split())) for _ in range(M)]
    
    A=[0]*(N+1)
    for i in S:
        A[i[0]]=max(A[i[0]],H[i[1]-1])
        A[i[1]]=max(A[i[1]],H[i[0]-1])
        
        
    ans=0
    tmp=0
    for i in A[1:]:
        if H[tmp]>i:
            ans+=1
        tmp+=1
        
    print(ans)
   
    
if __name__=="__main__":
    main()

Submission status: Accepted

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

h=list(map(int,input().split()))
hills=[[-1]for _ in range(len(h))]
for i in range(len(h)):
    hills[i][0]=h[i]

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

ans = 0
for i in range(n):
    tower = hills[i][0]
    flag=False
    for enemy in hills[i][1:]:
        if enemy>=tower:
            flag=True
            break
    if flag == False:
        ans += 1

print(ans)

Submission status: Accepted

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

import sys


def input():
    return sys.stdin.readline()


def resolve():
    n, m = map(int, input().split())
    h_list = list(map(int, input().split()))
    a_list = []
    b_list = []
    ans_list = [1 for i in range(n)]
    iso_list = [1 for i in range(n)]

    count = 0
    for i in range(m):
        a, b = map(int, input().split())
        if h_list[a-1] > h_list[b-1]:
            ans_list[b-1] = 0
        elif 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



    count = 0
    for i in ans_list:
        if i == 1:
            count += 1


    print(count)




if __name__ == "__main__":
    resolve()

Submission status: Accepted

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

Submission status: Accepted

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

ans = 0

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

for i in range(N):
    if H[i] > max(connect[i]):
        ans += 1
        
print(ans)

Submission status: Accepted

Solution code:
import numpy as np

N,M = (int(x) for x in input().split())
H = [int(x) for x in input().split()]
count = 0
x=np.zeros(N)
y=np.zeros(N)

for i in range(M):
    A,B = (int(x) for x in input().split())
    x[A-1] = x[A-1] + 1
    x[B-1] = x[B-1] + 1
    
    if H[A-1] != 0 and H[B-1] != 0 and H[A-1] > H[B-1]:
        y[A-1] = y[A-1] + 1
    elif H[A-1] != 0 and H[B-1] != 0 and H[A-1] < H[B-1]:
        y[B-1] = y[B-1] + 1

for i in range(N):
    if x[i] == y[i]:
        count = count + 1
print(count)

Submission status: Accepted

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

for m in range(M):
  A[m], B[m] = map(int, input().split())

dic = [[] for j in range(N)]
for m in range(M):
  dic[A[m]-1].append(H[B[m]-1])
  dic[B[m]-1].append(H[A[m]-1])
ans = 0
for n in range(N):
  if len(dic[n]) == 0:
    ans += 1
  elif H[n] > max(dic[n]):
    ans += 1
print(ans)

Submission status: Accepted

Solution code:
import numpy as np
import math
n, m = map(int,input().split())
h = list(map(int,input().split()))
mr = [1 for i in range(n)]
for i in range(m):
    a,b = map(int,input().split())
    if h[a-1] <= h[b-1]:
        mr[a-1] = 0
    if h[a-1] >= h[b-1]:
        mr[b-1] = 0
ans = 0
for i in mr:
    ans += i
print(ans)

Submission status: Accepted

Solution code:
import numpy as np
# coding: utf-8
# Your code here!
N, M = map(int, input().split())
#S = input()

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

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

path_max = [np.max(path_list[i]) for i in range(N)]
H = np.array(H)

#print(H)
#print(path_max)
print(len(H)-len(H[H<=path_max]))

Submission status: Accepted

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

import networkx as nx
G = nx.Graph()
G.add_nodes_from(list(range(1, N+1)))
for i in range(1, N+1):
    G.nodes[i]['H'] = H[i-1]
G.add_edges_from(paths)

ans = 0
for adj in G.adjacency():
    dic_adj = adj[1]
    ans += 1
    for n_adj in dic_adj.keys():
        if G.nodes[adj[0]]['H'] <= G.nodes[n_adj]['H'] :
            ans -=1
            break
print(ans)

Submission status: Accepted

Solution code:
mod = 10**9+7
import sys
from collections import Counter, defaultdict, deque
from itertools import product, permutations, combinations, combinations_with_replacement
from itertools import accumulate
from operator import itemgetter
from bisect import bisect_left,bisect
from heapq import heappop,heappush
from math import ceil,floor
from copy import deepcopy
from heapq import heappop,heappush,heapify
import heapq


# l = ['a', 'a', 'a', 'a', 'b', 'c', 'c']
# c = Counter(l)

# d = defaultdict(int)

sys.setrecursionlimit(10 ** 6)

int1 = lambda x: int(x) - 1

# リストの要素を改行を挟んで表示する
p2D = lambda x: print(*x, sep="\n")
# 入力を整数に変換して受け取る
def II(): return int(sys.stdin.readline())

def MI(): return map(int, sys.stdin.readline().split())
def MI1(): return map(int1, sys.stdin.readline().split())

# 入力全てを整数に変換したものの配列を受け取る
# def LI(): return list(map(int, sys.stdin.readline().split()))
# 入力全てを整数に変換して1引いたものの配列を受け取る
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def LI(): return list(map(lambda x:int(x), sys.stdin.readline().split()))
def HI(): return list(map(lambda x:int(x)*(-1), sys.stdin.readline().split()))


n,m = MI()
h = LI()
a = []

d = defaultdict(int)
for _ in range(m):
	aa,bb = MI()
	d[(aa-1)] = max(d[bb-1],d[(aa-1)])
	d[(bb-1)] = max(d[bb-1],d[(aa-1)])
	if not aa==bb:
		if h[aa-1]>=h[bb-1]:
			a.append(bb-1)
		if h[bb-1]>=h[aa-1]:
			a.append(aa-1)

print(n-len(set(a)))
# ans=0
# for i in range(n):
# 	if h[i]<=d[i]:
# 		ans += 0
# 	else:
# 		ans += 1
	# tmp = d[str(h[i])]
	# k = 1
	# if len(tmp)>0:
	# 	tmp = [int(s) for s in tmp.split(':') if not s=='']
	# 	for s in tmp:
	# 		if int(h[i])<=s:
	# 			k = 0
	# ans+=k
# print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
n, m = map(int, input().split())
*h, = map(int, input().split())
h = [0] + h
i = [0] + [1] * n

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

Submission status: Accepted

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

hantei = [1]*n

for i in range(m):
    data = list(map(int, input().split()))

    if h[data[0]-1] < h[data[1]-1]:
        hantei[data[0]-1] = 0
    elif h[data[0]-1] > h[data[1]-1]:
        hantei[data[1]-1] = 0
    else:
        hantei[data[0]-1] = 0
        hantei[data[1]-1] = 0

print(sum(hantei))

Submission status: Accepted

Solution code:
from collections import deque
n,m=[int(_) for _ in input().split()]
H=[int(_) for _ in input().split()]
Hlist=deque(deque() for a in range(n))
count=0
for a in range(m):
    a,b=[int(_) for _ in input().split()]
    Hlist[a-1].append(b-1)
    Hlist[b-1].append(a-1)
for i,j in enumerate(Hlist):
    flag=1
    for a in j:
        if H[a]>=H[i]:
            flag=0
    if flag==1:
        count+=1
    flag=1
print(count)

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
n,m=map(int,input('').split(' '))
s=input('')
s=s.split(' ')
h=[]
for i in range(n):
    h.append(int(s[i]))

c=[]
for i in range(n):
    c.append(1)

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

m=0
for i in range(n):
    m=m+c[i]

print(m)

Submission status: Accepted

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

print(sum(nn))

Submission status: Accepted

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

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

ahi = [True] * N
for i, a in enumerate(A):
    b = B[i]
    a -= 1
    b -= 1
    if H[a] < H[b]:
        ahi[a] = False
    elif H[a] == H[b]:
        ahi[a] = False
        ahi[b] = False
    else:
        ahi[b] = False
#  for i, h in enumerate(H):
    #  ahi[]
    #  ok = True
    #  for a_i in [i for i, a in enumerate(A) if a == h]:
        #  a = A[a_i]
        #  b = B[a_i]
        #  if h <= H[b]:
            #  ok = False
            #  break
    #  ahi[i] = ok

print(len(list(filter(lambda x: x, ahi))))

Submission status: Accepted

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

a = []
b = []
for i in range(m):
  tmp = list(map(int,input().split()))
  a.append(tmp[0])
  b.append(tmp[1])
  
atta = [1]*n
for j in range(m):
  if height[a[j]-1] == height[b[j]-1]:
    atta[a[j]-1] = 0
    atta[b[j]-1] = 0
  elif height[a[j]-1] < height[b[j]-1]:
    atta[a[j]-1] = 0
  elif height[a[j]-1] > height[b[j]-1]:
    atta[b[j]-1] = 0
  #print(j,atta)

print(atta.count(1))

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
h = list(map(int,input().split()))
l = [[]]*m
cnt = 0
for i in range(m):
    l[i] = list(map(int,input().split()))
f = [1]*n
for j in range(m):
    if h[l[j][0]-1] <= h[l[j][1]-1]:
        f[l[j][0]-1] = 0
    if h[l[j][0]-1] >= h[l[j][1]-1]:
        f[l[j][1]-1] = 0
print(sum(f))

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)]
h = [1]*n

for i in range(m):
    if H[l[i][0]-1] > H[l[i][1]-1]:
        h[l[i][1]-1] = 0
    elif H[l[i][0]-1] < H[l[i][1]-1]:
        h[l[i][0]-1] = 0
    elif H[l[i][0]-1] == H[l[i][1]-1]:
        h[l[i][0]-1] = 0
        h[l[i][1]-1] = 0
ans=0
for i in range(n):
    if h[i] != 0:
        ans+=1
print(ans)

Submission status: Accepted

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

buf = [[0] for i in range(n)] 

for i in range(m):
    buf[ab[i][0] - 1].append(h[ab[i][1] - 1])
    buf[ab[i][1] - 1].append(h[ab[i][0] - 1])

cnt = 0
for i in range(n):
    if h[i] > max(buf[i]):
        cnt += 1

print(cnt)

Submission status: Accepted

Solution code:
n,m = input().split()
n = int(n)
m = int(m)
graph = []
str_list = list(input().split())
str_list = list(map(lambda x:int(x), str_list))
for i in range(n):
  graph.append([])
for i in range(m):
  a,b = input().split()
  a = int(a)
  b = int(b)
  graph[a-1].append(str_list[b-1])
  graph[b-1].append(str_list[a-1])
count = 0
for i in range(n):
  graph[i].sort(reverse=True)
  if len(graph[i])==0:
    count = count + 1
    continue
  if str_list[i] > graph[i][0]:
    count = count + 1
print(count)

Submission status: Accepted

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

print(c)

Submission status: Accepted

Solution code:
N, M = input().split()
H = input().split()
x2 = []
count = 0
for i in range(0, int(N)):
  x2.append(1)
for i in range(0, int(M)):
  A, B = input().split()
  if int(H[int(A)-1]) > int(H[int(B)-1]):
    x2[int(B)-1] = 0
  elif int(H[int(A)-1]) == int(H[int(B)-1]) :
    x2[int(B)-1] = 0
    x2[int(A)-1] = 0
  else:
    x2[int(A)-1] = 0
for j in range(0, int(N)):
  if x2[j-1] == 1:
    count += 1
print(count)

Submission status: Accepted

Solution code:
def Main(N, M, H, A, B):
#     d = {}
    d2 = {}
    for i in range(N):
#         d[i+1] = []
        d2[i+1] = 0
    ans = 0
    for i in range(M):
#         d[A[i]].append(B[i])
        d2[A[i]] = max(d2[A[i]], H[B[i]-1])
#         d[B[i]].append(A[i])
        d2[B[i]] = max(d2[B[i]], H[A[i]-1])
    for k, v in d2.items():
        if H[k-1] > v:
            ans += 1
    return ans  
    
def main():
    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())
    print(Main(N, M, H, A, B))

if __name__ == '__main__':
    main()

Submission status: Accepted

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


hills = [[] for i in range(N)]
for ab in AB:
    a = ab[0]
    b = ab[1]
    hills[a-1].append(H[b-1])
    hills[b-1].append(H[a-1])

for hill in hills:
    hill = set(hill)
    
counter = 0
for i in range(N):
    hill = hills[i]
    if not hill :
        counter += 1
    elif H[i] > max(hill):
        counter += 1
    else :
        counter += 0

print(counter)

Submission status: Accepted

Solution code:
N,M = map(int,input().split())  #N個の展望台,M本の道

H_list = [int(x) for x in input().split()]

answer_list = [0 for _ in range(N)]

for i in range(M):
    B = [int(x) for x in input().split()]
    #print(B)
    
    if H_list[B[0]-1] < H_list[B[1]-1]:
        answer_list[B[0]-1] += 1
    elif H_list[B[0]-1] > H_list[B[1]-1]:
        answer_list[B[1]-1] += 1
    else:
        answer_list[B[0]-1] += 1
        answer_list[B[1]-1] += 1

    
cnt = 0
for j in range(N):
    if answer_list[j] == 0 :
        cnt += 1
    
print(cnt)