Problem:


Score : 300 points

Problem Statement

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

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

How many good observatories are there?

Constraints

2 \leq N \leq 10^5

1 \leq M \leq 10^5

1 \leq H_i \leq 10^9

1 \leq A_i,B_i \leq N

A_i \neq B_i

Multiple roads may connect the same pair of observatories.

All values in input are integers.

Input

Input is given from Standard Input in the following format:

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

Output

Print the number of good observatories.

Sample Input 1

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

Sample Output 1

2

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

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

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

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

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

Sample Input 2

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

Sample Output 2

3



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


Sample output:
2

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
H = list(map(int,input().split()))
d = {}
s = []

for _ in range(M):
    ab = list(map(int,input().split()))
    if ab[0] in d.keys():
        d[ab[0]] = max(d[ab[0]],H[ab[1]-1])
    else:
        d[ab[0]] = H[ab[1]-1]
    if ab[1] in d.keys():
        d[ab[1]] = max(d[ab[1]],H[ab[0]-1])
    else:
        d[ab[1]] = H[ab[0]-1]
    s.append(ab[0])
    s.append(ab[1])

count = 0
for i in d.keys():
    if H[i-1] > d[i]:
        count += 1

count += N - len(set(s))

print(count)

Submission status: Accepted

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

height=list(map(int,input().strip().split()) )
lst=[1]*h

for i in range(m):
    a,b=map(int,input().strip().split())
    if height[a-1]>height[b-1]:
        lst[b-1]=0
    elif height[a-1]<height[b-1]:
        lst[a-1]=0
    else:
        lst[b - 1] = 0
        lst[a - 1] = 0

print(lst.count(1))

Submission status: Accepted

Solution code:
n, m = [int(i) for i in input().split(" ")]
H = [int(i) for i in input().split(" ")]
ans = [1] * n
for i in range(m):
    a, b = [int(i) for i in input().split(" ")]
    if H[a - 1] <= H[b - 1]:
        ans[a - 1] = 0
    if H[a - 1] >= H[b - 1]:
        ans[b - 1] = 0
print(sum(ans))

Submission status: Accepted

Solution code:
N, M = map(int,input().split())
H_list = list(map(int,input().split()))
A_list = [0]*M
B_list = [0]*M
for i in range(M):
  A_list[i],B_list[i] = map(int,input().split())

count_list = ['+']*N
for j in range(M):
  if H_list[B_list[j]-1]-H_list[A_list[j]-1] >= 0:
    count_list[A_list[j]-1] = '-'
  if H_list[A_list[j]-1]-H_list[B_list[j]-1] < 0 and count_list[A_list[j]-1] != '-':
    count_list[A_list[j]-1] = '+'

for k in range(M):
  if H_list[A_list[k]-1]-H_list[B_list[k]-1] >= 0:
    count_list[B_list[k]-1] = '-'
  if H_list[A_list[k]-1]-H_list[B_list[k]-1] < 0 and count_list[B_list[k]-1] != '-':
    count_list[B_list[k]-1] = '+'
 
print(count_list.count('+'))

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
H = [0] + list(map(int, input().split()))
G = [[] * (n + 1) for _ in range(n + 1)]
for i in range(m):
	a, b = map(int, input().split())
	G[a].append(b)
	G[b].append(a)

# print(G)

cnt = 0
for i in range(1, n + 1):
	path = G[i] # つながっている展望台の集合
	if len(path) == 0:
		cnt += 1
	else:
		flg = True
		for e in path:
			if H[i] <= H[e]:
				flg = False
		if flg:
			cnt += 1

print(cnt)

Submission status: Accepted

Solution code:
def main():
    N, M = map(int, input().split())
    H = [int(h) for h  in input().split()]
    E = [None]*M
    G = [1]*N
    for p in range(M):
        A, B = map(int, input().split())
        if G[A-1] == 0 and G[B-1] == 0:
            continue
        if H[A-1] > H[B-1]:
            G[B-1] = 0
        elif H[A-1] == H[B-1]:
            G[A-1] = 0
            G[B-1] = 0
        else:
            G[A-1] = 0
        
    print(sum(G))


if __name__ == "__main__":
    main()

Submission status: Accepted

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

Submission status: Accepted

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

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

for i in range(M):
  a, b = map(int, input().split())
  a -= 1
  b -= 1
  if Hl[a] > Hl[b]:
    al.append(b+1)
  elif Hl[a] < Hl[b]:
    al.append(a+1)
  else:
    al.extend([a+1,b+1])

al = set(al)
print(len(Hl) - len(al))

Submission status: Accepted

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

#H = list(range(1, n+1))
#print(H)

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

flag = [1] * n
#print(flag)

for i in range(m):
  a,b = map(int, input().split())
  #print(a, b)
  #print("aの高さ:" + str(H[a-1]))
  #print("bの高さ:" + str(H[b-1]))
  if H[a-1] <= H[b-1]:
    flag[a-1] = 0
    #print(str(a)+"はいい展望台じゃないよ")
  if H[b-1] <= H[a-1]:
    flag[b-1] = 0
    #print(str(b)+"はいい展望台じゃない~")
  #print(flag)
#print(flag)
count = 0
for f in flag:
  if f:
    count += 1
print(count)

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)]
tenbou=[1]*N
for i in range(M):
    if H[a[i][0]-1] < H[a[i][1]-1]:
        tenbou[a[i][0]-1]=0
    elif H[a[i][0]-1] > H[a[i][1]-1]:
        tenbou[a[i][1]-1]=0
    else:
        tenbou[a[i][0]-1]=0
        tenbou[a[i][1]-1]=0
print(sum(tenbou))

Submission status: Accepted

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

H=list(map(int, input().split()))
A = [input().split() for l in range(m)]

li = []

for a,b in A:
    if H[int(a)-1]<H[int(b)-1]:
        li.append((a,0))
    elif H[int(a)-1]>H[int(b)-1]:
        li.append((b,0))
    else:
        li.append((a,0))
        li.append((b,0))


di=dict(li)
print(n-len(di))

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

Submission status: Accepted

Solution code:
from sys import stdin, stdout  
  
def main(): 
	n, k = [int(x) for x in stdin.readline().split()] 
	arr = [int(x) for x in stdin.readline().split()] 
	notValid = set()
	for x in range(k): 
		a, b = [int(x) for x in stdin.readline().split()] 
		if arr[a-1] > arr[b-1]:
			notValid.add(b)
		elif arr[a-1] == arr[b-1]:
			notValid.add(b)
			notValid.add(a)
		else:
			notValid.add(a)
	#print(notValid,"hass")

	stdout.write(str(n - len(notValid))+'\n')
if __name__ == "__main__": 
	main()

Submission status: Accepted

Solution code:
N , M = map(int,input().split())
Height = [h_i for h_i in map(int,input().split())]
Roots = []
counter = [0 for i in range(N)]
for j in range(M):
    root = [c_i -1 for c_i in map(int,input().split())]
    #print(root)
    if Height[root[0]]<Height[root[1]]:
        counter[root[0]] += 1
    elif Height[root[0]]==Height[root[1]]:
        counter[root[0]] += 1
        counter[root[1]] += 1
    else:
        counter[root[1]] += 1

counter2 = 0
for i in range(N):
    if counter[i]==0:
        counter2+=1
print(counter2)

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
a=list(map(int,input().split()))
lst=[]
for i in range(M):
  b=list(map(int,input().split()))
  if a[b[0]-1]>a[b[1]-1]:
    lst.append(b[1])
  elif a[b[0]-1]==a[b[1]-1]:
    lst.append(b[0])
    lst.append(b[1])
  else:
    lst.append(b[0])
print(N-len(set(lst)))

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
H=[int(x) for x in input().split()]
l=[1 for _ in range(N)]
for _ in range(M):
  A,B=map(int,input().split())
  if H[A-1] < H[B-1]:
    l[A-1] = 0
  elif H[A-1] == H[B-1]:
    l[A-1] = 0
    l[B-1] = 0
  else:
    l[B-1] = 0
print(sum(l))

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
h_array = list(map(int, input().split()))
ab = []
sum = 0
answer = [True for i in range(n)]

for i in range(m):
  ab.append(list(map(int, input().split())))

for i in range(len(ab)):
  if h_array[ab[i][0]- 1] >= h_array[ab[i][1]- 1]:
    answer[ab[i][1] - 1] = False
  if h_array[ab[i][1]- 1] >= h_array[ab[i][0]- 1]:
      answer[ab[i][0] - 1] = False

print(answer.count(True))

Submission status: Accepted

Solution code:
import bisect

inputLine=input()
N=int(inputLine.split(" ")[0])
M=int(inputLine.split(" ")[1])

inputLine=input()
H=inputLine.split(" ")
for i in range(len(H)):
    H[i]=int(H[i])

root=[]
for i in range(M):
    inputLine=input()
    A=int(inputLine.split(" ")[0])
    B=int(inputLine.split(" ")[1])

    root.append([A,B])
    root.append([B,A])

root.sort()

root2=[]
for i in range(len(root)):
    root2.append(root[i][0])

allObservatoryCheck=[]
for i in range(N):
    allObservatoryCheck.append(True)

for i in range(N):

    startPoint = bisect.bisect_left(root2, i + 1)

    for j in range(startPoint, len(root)):
        
        if root[j][0] == i + 1:
            if H[i] <= H[root[j][1] - 1]:
                allObservatoryCheck[i] = False

        if root[j][0] > i + 1:
            break

result = 0
for i in range(N):
    if allObservatoryCheck[i] == True:
        result += 1

print(result)

Submission status: Accepted

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

print(sum(result))

Submission status: Accepted

Solution code:
import numpy as np

N,M   = list(map(int,input().split()))
Hlist = list(map(int,input().split()))
Hdict = {i:Hlist[i] for i in range(len(Hlist))}
# adj = [[0 for _ in range(N)] for _ in range(N)]

# for line in Mlist:
bad_set = set()
for _ in range(M):
    line = list(map(int,input().split()))
    if Hdict[line[0]-1] <= Hdict[line[1]-1]:
        bad_set.add(line[0])
    if Hdict[line[1]-1] <= Hdict[line[0]-1]:
        bad_set.add(line[1])
print(N-len(bad_set))

Submission status: Accepted

Solution code:
import numpy

inp=input().split(" ")
n=int(inp[0])
m=int(inp[1])
inh=input().split(" ")
for i in range(len(inh)):
  inh[i]=int(inh[i])
pairs=numpy.zeros(2*m,dtype=">i4").reshape(-1,2)
for i in range(m):
  a=input().split(" ")
  pairs[i][0]=int(a[0])
  pairs[i][1]=int(a[1])
lists=[[] for i in range(n)]
for i in range(len(pairs)):
  lists[pairs[i][0]-1].append(pairs[i][1]-1)
  lists[pairs[i][1]-1].append(pairs[i][0]-1)
for i in range(len(lists)):
  lists[i]=list(set(lists[i]))
count=0
for i in range(len(lists)):
  if len(lists[i])==0:
    count+=1
    continue
  for j in range(len(lists[i])):
    if inh[i] <= inh[lists[i][j]]:
      break
    if j == len(lists[i])-1:
      count+=1
print(count)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
h_list = list(map(int, input().split()))
road_dict = {a+1: set() for a in range(n)}
for i in range(m):
  a, b = map(int, input().split())
  if a in road_dict:
    road_dict[a].add(b)
  else:
    road_dict[a] = set([b])
  if b in road_dict:
    road_dict[b].add(a)
  else:
    road_dict[b] = set([a])
use_list = []
res = 0
for k, s in road_dict.items():
  k_height = h_list[k-1]
  if len(s) == 0:
    res += 1
  else:
    add_flg = True
    for v in list(s):
      v_height = h_list[v-1]
      if k_height > v_height:
        continue
      else:
        add_flg = False
        break
    if add_flg:
      res += 1
print(res)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
# スペース区切りの整数の入力
N, M = map(int, input().split())
# 文字列の入力
H_list = list(map(int, input().split()))
#print(H_list)
#開業されたN個要素を受け付ける
road_list = []
for i in range(M):
    road_list.append(list(map(int, input().split())))
    #road_list.append(input())
#print(road_list)
flg_list=[]
for i in range(N):
    flg_list.append(1)

#print(flg_list)

ans = 0
'''
for i in range(N):
    #print(i+1)
    flg = 1
    for road in road_list:
        if i+1 in road:
            if i+1 == road[0] and H_list[road[0]-1] <= H_list[road[1]-1]:
                flg=0
            elif i+1 == road[1] and H_list[road[1]-1] <= H_list[road[0]-1]:
                flg=0
    if flg==1:
        #print("flg")
        ans=ans+1
'''
for road in road_list:
    if H_list[road[0]-1] < H_list[road[1]-1]:
        flg_list[road[0]-1]=0
    elif H_list[road[1]-1] < H_list[road[0]-1]:
        flg_list[road[1]-1]=0
    else:
        flg_list[road[0]-1]=0
        flg_list[road[1]-1]=0
for i in range(N):
    if flg_list[i]==1:
        ans=ans+1


print(ans)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
h = []
a = []
b = []
dic_target = {}
dic_exclude = {}

counter = 0

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

for i in range(m):
  _a, _b = map(int, input().split())
  #print(_a, _b)
  h_a = h[_a - 1]
  h_b = h[_b - 1]
  if _a in dic_target:
    dic_target[_a] = max(dic_target[_a], h_a, h_b)
  else:
    dic_target[_a] = max(h_a, h_b)
  if _b in dic_target:
    dic_target[_b] = max(dic_target[_b], h_a, h_b)
  else:
    dic_target[_b] = max(h_a, h_b)
  if h_a == h_b:
    if _a in dic_exclude:
      dic_exclude[_a] = max(dic_exclude[_a], h_a, h_b)
    else:
      dic_exclude[_a] = max(h_a, h_b)
    if _b in dic_exclude:
      dic_exclude[_b] = max(dic_exclude[_b], h_a, h_b)
    else:
      dic_exclude[_b] = max(h_a, h_b)

for i in range(n):
  if i + 1 not in dic_target:
    counter += 1
  elif i + 1 in dic_target and h[i] == dic_target.get(i + 1):
    if i + 1 not in dic_exclude or h[i] != dic_exclude.get(i + 1):
      counter += 1
print(counter)

Submission status: Accepted

Solution code:
# from collections import defaultdict

n, m = map(int, input().split())
high = [int(i) for i in input().split()]
# a_b = [[int(i) for i in input().split()] for i in range(m)]

high_d = {}
for i in range(n):
    # d = defaultdict(list)
    high_d[i+1] = high[i]
# print(high_d)

d = {}
for _ in range(m):
    a, b = map(int, input().split())
    if a not in d:
        d[a] = [b]  # リストにし忘れ
    else:
        d[a].append(b)
    if b not in d:
        d[b] = [a]  # リストにし忘れ
    else:
        d[b].append(a)


# print(d)
cnt = 0
for i, li in d.items():
    # [a].append(b)
    is_true = True
    for j in li:
        if high_d[i] > high_d[j]:
            continue
        else:
            is_true = False
    if is_true:
        cnt += 1

cnt += n - len(d)

print(cnt)

Submission status: Accepted

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

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

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

good = []
for i in range(n):
    good.append(0)

for i in range(m):
    if h[a[i][0] - 1] > h[a[i][1] - 1]:
        good[a[i][1] - 1] = 1
        if good[a[i][0] - 1] != 1:
            good[a[i][0] - 1] = 2
    elif h[a[i][0] - 1] < h[a[i][1] - 1]:
        good[a[i][0] - 1] = 1
        if good[a[i][1] - 1] != 1:
            good[a[i][1] - 1] = 2
    else:
        good[a[i][1] - 1] = 1
        good[a[i][0] - 1] = 1

count = 0
for i in range(n):
    if good[i] == 0 or good[i] == 2:
        count = count + 1

print(count)

Submission status: Accepted

Solution code:
import itertools

N,M=map(int,input().split())
S=list(map(int,input().split()))
miti=[input().split() for i in range(M)]
miti2= [ flatten for inner in miti for flatten in inner ]
miti2 = [int(i) for i in miti2]
miti3=N-len(set(miti2))

count2=[int(i) for i in range(1,N+1)]

for j in range(0,2*M,2):
  if S[miti2[j]-1]>S[miti2[j+1]-1]:
    count2[miti2[j+1]-1]=0
  elif S[miti2[j]-1]<S[miti2[j+1]-1]:
    count2[miti2[j]-1]=0
  else:
    count2[miti2[j+1]-1]=0
    count2[miti2[j]-1]=0
print(len(set(count2))-1)

Submission status: Accepted

Solution code:
def resolve():
    N, M = map(int, input().split())
    H = list(map(int, input().split()))
    not_good = []
    for i in range(M):
        A, B = map(lambda x: int(x) - 1, input().split())
        if H[A] > H[B]:
            not_good.append(B)
        elif H[A] < H[B]:
            not_good.append(A)
        elif H[A] == H[B]:
            not_good.extend([A, B])
    print(N - len(set(not_good)))

resolve()

Submission status: Accepted

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


class Node:

    def __init__(self):
        self.comparison_list = []
        
        self.height = 0
        
        self.id_list = []


def main():
# 整数の入力
    
    s = [int(x) for x in input().split(' ')]
    n = s[0]
    m = s[1]
    h_list = [int(x) for x in input().split(' ')]
    node_list = []
    for h in h_list:
        node = Node()
        
        node.height = h
        node_list.append(node)

    for i in range(m):
        s = [int(x) for x in input().split(' ')]
        a = s[0] - 1
        b = s[1] - 1
        node_list[a].id_list.append(b)
        node_list[b].id_list.append(a)

    for n in node_list:
        if len(n.id_list) == 0:
            n.comparison_list.append(True)
        else:
            n.id_list = list(set(n.id_list))
            # もしまだ調べていなかったら
            if len(n.comparison_list) == 0:
                for id in n.id_list:
                    target = node_list[id]
                    if n.height > target.height:
                        n.comparison_list.append(True)
                        target.comparison_list.append(False)                       
                        
                    else:
                        n.comparison_list.append(False)
    
    print(len([x for x in node_list if all(x.comparison_list)]))

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def resolve():
    n, m = map(int, input().split())
    h = list(map(int, input().split()))
    a = [0] * m
    b = [0] * m
    s = [[-1] for j in range(n)]
    ans=0
    x=1
    for i in range(m):
        a[i], b[i] = map(int, input().split())
    for i in range(m):
        s[a[i]-1].append(b[i])
        s[b[i]-1].append(a[i])
    for i in range(n):
        if len(s[i])!=1:
            for j in s[i]:
                if j!=-1:
                    if h[i]<=h[j-1]:
                        x=0
        ans+=x
        x=1
    print(ans)
resolve()

Submission status: Accepted

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

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

R=[[] for _ in range(N)]
for i in range(M):
    R[A[i]-1].append(B[i])
    R[B[i]-1].append(A[i])

best=0
for i in range(len(R)):
    biggest=True
    if len(R[i])==0:
        pass
    else:
        for j in range(len(R[i])):
            if H[i]<=H[R[i][j]-1]:
                biggest=False
    if biggest==True:
        best+=1

print(best)

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
import copy
n, m = map(int, input().split())
H = list(map(int, input().split()))
A = []
for i in range(m):
    A.append(list(map(int,input().split())))
# print(A)
T = copy.copy(H)
# print(T)

for i in range(m):
    if H[A[i][0]-1] > H[A[i][1]-1]:
        T[A[i][1]-1] = 0
    elif H[A[i][0]-1] < H[A[i][1]-1]:
        T[A[i][0]-1] = 0
    else:
        T[A[i][0]-1] = 0
        T[A[i][1]-1] = 0
    
cnt = 0    
for i in range(n):
    if T[i] != 0:
        cnt = cnt + 1
print(cnt)

Submission status: Accepted

Solution code:
N,M =  map(int, input().split())
HList = input().split(" ")
ABHash = {}
for i in range(M) :
    A,B = map(int, input().split())
    A = A-1
    B = B-1
    if A not in ABHash :
        ABHash[A] = []
    ABHash[A].append(B)
    if B not in ABHash :
        ABHash[B] = []
    ABHash[B].append(A)

count = 0

for i in range(N) :
    if i not in ABHash :
        count += 1
        continue

    BList = ABHash[i]
    AHeight = int(HList[i])
    isGood = True
    
    for j in range(len(BList)) :
        if AHeight <= int(HList[BList[j]]) :
            isGood = False
    if(isGood) :
        count += 1
print(count)

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
H=map(int,input().split())
S=[[] for _ in range(N)]
for _ in range(M):
    A,B=map(int,input().split())
    S[A-1].append(B-1)
    S[B-1].append(A-1)
answer=0
H=[int(h) for h in H]
n=0
for s in S:
    kazu=0
    number=len(s)
    for a in s:
        if H[n] > H[a]:
            kazu+=1
    if kazu==number:
            answer+=1
    n+=1
print(answer)

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
h = tuple(map(int,input().split()))
l = set([tuple(map(int,input().split())) for i in range(m)])
x = [[] for i in range(n)]
ans=0
for t in l:
    x[t[0]-1].append(h[t[1]-1])
    x[t[1]-1].append(h[t[0]-1])
for k,li in enumerate(x):
    a = h[k]
    if li == []:
        ans+=1
    else:
        if a>max(li):
            ans+=1
print(ans)

Submission status: Accepted

Solution code:
N,M=input().split()
N=int(N)
M=int(M)
H=input().split()
H=list(map(int,H))
my_list=[1]*N

for i in range(M):
  r,s=input().split()
  r=int(r)-1
  s=int(s)-1
  if H[r]>H[s]:
    my_list[s]=0
  elif H[r]<H[s]:
    my_list[r]=0
  else:
    my_list[r]=0
    my_list[s]=0

count=0
for j in my_list:
  count+=j
print(count)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
h=list(map(int,input().split()))
h.insert(0,0)
s=set()
for i in range(m):
	a,b=map(int,input().split())
	if h[a]<=h[b]:s.add(a)
	if h[a]>=h[b]:s.add(b)
print(n-len(s))

Submission status: Accepted

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

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

print(sum(l))

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
H = list(map(int, input().split()))
connection = [0 for _ in range(N)]
cnt = 1
result = 0
for _ in range(M):
    A, B = map(int, input().split())
    if H[A-1] < H[B-1]:
        connection[A-1] = -1
    elif H[A-1] > H[B-1]:
        connection[B-1] = -1
    else:
        connection[B-1] = -1
        connection[A-1] = -1

for i in connection:
    if i == 0:
        result += 1

print(result)

Submission status: Accepted

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

Submission status: Accepted

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

#print(tenbo)
print(tenbo.count(1))

Submission status: Accepted

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

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

print(k.count(0))

Submission status: Accepted

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

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

print(n-len(set(low)))

Submission status: Accepted

Solution code:
from sys import stdin


def get_result(data):
    N, M = data[0]
    H = data[1]
    adj_list = [set() for _ in range(N)]
    for val in data[2:]:
        adj_list[val[0]-1].add(val[1]-1)
        adj_list[val[1]-1].add(val[0]-1)

    ans = 0
    for i in range(N):
        base_h = H[i]
        flag = True
        edges = adj_list[i]
        for edge in edges:
            h = H[edge]
            if h >= base_h:
                flag = False
                break
        if flag:
            ans += 1
    return ans


if __name__ == '__main__':
    raw_data = [val.rstrip() for val in stdin.readlines()]
    data = [list(map(int, val.split(' '))) for val in raw_data]
    result = get_result(data)
    print(result)

Submission status: Accepted

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


all_temboudai = {i for i in range(1, n+1)}

for a, b in ab_list:
    if h[a-1] > h[b-1]:
        if b not in all_temboudai:
            continue
        all_temboudai.discard(b)
    elif h[a-1] < h[b-1]:
        if a not in all_temboudai:
            continue
        all_temboudai.discard(a)
    elif h[a-1] == h[b-1]:
        if a in all_temboudai:
            all_temboudai.discard(a)
        if b in all_temboudai:
            all_temboudai.discard(b)

print(len(all_temboudai))

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)]
s = [0 for i in range(n)]
for i in range(m):
    if h[a[i][0]-1] <= h[a[i][1]-1]:
        s[a[i][0]-1] = 1
    if h[a[i][0]-1] >= h[a[i][1]-1]:
        s[a[i][1]-1] = 1
ans = n - sum(s)
print(ans)

Submission status: Accepted

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

good = [True] * N

for _ in range(M):
    A, B = tuple(map(int, input().split()))
    H_A, H_B = Hs[A-1], Hs[B-1]
    if H_A < H_B:
        good[A-1] = False
    elif H_B < H_A:
        good[B-1] = False
    else:
        good[A-1] = good[B-1] = False

print(sum([v == True for v in good]))

# path = [[0] * N for _ in range(N)]
# for _ in range(M):
#     A, B = tuple(map(int, input().split()))
#     H_A, H_B = Hs[A-1], Hs[B-1]
#     path[A-1][B-1] = H_B
#     path[B-1][A-1] = H_A

# print(sum(all(Hs[i] > h for h in p) for i, p in enumerate(path)))

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

import sys
import math


debug = False

def log(text):
    if debug:
        print(text)


def parse_input(lines_as_string = None):

    global debug
    lines = []
    if lines_as_string is None:
        debug = False
        lines.append(input())
        (n, m) = [int(e) for e in lines[0].split(' ')]
        lines.append(input())
        for _ in range(m):
            lines.append(input())
    else:
        debug = True
        lines = [e for e in lines_as_string.split("\n")][1:-1]
        (n, m) = [int(e) for e in lines[0].split(' ')]

    h_list = [int(e) for e in lines[1].split(' ')]
    ab_list = []
    for i in range(2, m+2):
        ab_list.append([int(e) for e in lines[i].split(' ')])
        
    return (n, m, h_list, ab_list)


def solve(n, m, h_list, ab_list):


    bad_tower = set()
    for j in range(m):

        ab = ab_list[j]
        if h_list[ab[0]-1] <= h_list[ab[1]-1]:
            bad_tower.add(ab[0])
        
        if h_list[ab[1]-1] <= h_list[ab[0]-1]:
            bad_tower.add(ab[1])

        if debug:
            log("j=%d, bad_tower=%s" % (j, bad_tower))
    
    result = n - len(bad_tower)

    return  result


def main():
    # 出力
    result = solve(*parse_input())
    if isinstance(result, list):
        for r in result:
            print("%s" % r, sep='')
    else:
        print("%s" % result, sep='')

if __name__ == '__main__':

    main()

Submission status: Accepted

Solution code:
a,b = map(int, input().split())
List = [list(map(int, input().split())) for i in range(b+1)]
#i番目の展望台の高さ　List[0][i-1](i>=1)
Flag=[1]*a
for i in range(1,b+1):
  m = List[i][0]-1 # 比較する展望台の番号
  n = List[i][1]-1 # 比較する展望台の番号
  if List[0][m] < List[0][n]:
    Flag[m]=0
  elif List[0][n] < List[0][m]:
    Flag[n]=0
  elif List[0][n] == List[0][m]:
    Flag[m]=0
    Flag[n]=0
  else:
    print("weird")
Output=Flag.count(1)
print(Output)

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

cnt = 0

lose_flag = [0] * n
for j in range(m):
    if h[a[j]-1] < h[b[j]-1]:
        lose_flag[a[j]-1] = 1
    elif h[a[j]-1] > h[b[j]-1]:
        lose_flag[b[j]-1] = 1
    elif h[a[j]-1] == h[b[j]-1]:
        lose_flag[a[j]-1] = 1
        lose_flag[b[j]-1] = 1

cnt += lose_flag.count(0)

print(cnt)

Submission status: Accepted

Solution code:
N,K = map(int,input().split())
Hs = list(map(int,input().split()))
outs = [1] * N
for _ in range(K):
    a,b = map(int,input().split())
    if Hs[a-1] == Hs[b-1]:
        outs[a-1] = 0 
        outs[b-1] = 0 
    elif Hs[a-1] > Hs[b-1]:
        outs[b-1] = 0 
    else:
        outs[a-1] = 0 
print(sum(outs))

Submission status: Accepted

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