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
#input()
#int(input())
N,M=map(int,input().split())
H = list(map(int,input().split()))
AB=[list(map(int,input().split())) for _ in range(M)]

bad_l = []
for i in range(M):
    h1 = H[AB[i][0]-1]
    h2 = H[AB[i][1]-1]
    if h1 <= h2:
        bad_l.append(AB[i][0])
    if h1 >= h2:
        bad_l.append(AB[i][1])
p = list(set(bad_l))
print(N-len(p))

Submission status: Accepted

Solution code:

N,M =  map( int ,input().split())
H_list = list(map( int , input().split()))
A_B_list = [[0] * 2  for i in range(M)]
bad_list = []
J_list = []
for i in range(M):
    A,B = map( int ,input().split())
    A_B_list[i][0] = A
    A_B_list[i][1] = B
for j in range(M):
    if H_list[A_B_list[j][0]-1] > H_list[A_B_list[j][1]-1]:
        bad_list.append(A_B_list[j][1])
    elif H_list[A_B_list[j][0]-1] < H_list[A_B_list[j][1]-1]:
        bad_list.append(A_B_list[j][0])
    else:
        bad_list.append(A_B_list[j][0])
        bad_list.append(A_B_list[j][1])
J_list = list(set(bad_list))
print(N-len(J_list))

Submission status: Accepted

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


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

print(sum(ans))

Submission status: Accepted

Solution code:
import itertools
import math
import string
import collections
from collections import Counter
from collections import deque
import sys
sys.setrecursionlimit(2*10**5)
INF = 2**60


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


def nCr(n, r):
    return math.factorial(n)//(math.factorial(n-r)*math.factorial(r))


def has_duplicates2(seq):
    seen = []
    for item in seq:
        if not(item in seen):
            seen.append(item)
    return len(seq) != len(seen)


def divisor(n):
    divisor = []
    for i in range(1, n+1):
        if n % i == 0:
            divisor.append(i)
    return divisor


# coordinates
dx = [-1, -1, -1, 0, 0, 1, 1, 1]
dy = [-1, 0, 1, -1, 1, -1, 0, 1]

n, m = map(int, input().split())
h = readints()
x = [0]*n
for i in range(n):
    x[i] = []*n
for i in range(m):
    a, b = map(int, input().split())
    #print(a, b)
    x[a-1].append(b)
    x[b-1].append(a)
# print(x)
cnt = 0

for i in range(n):
    y = True
    for j in x[i]:
        #print(i, x[i])
        if h[i]-h[j-1] <= 0:
            y = False
    if y:
        cnt += 1
print(cnt)

Submission status: Accepted

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

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

for p in range(n):
  if cnt[p]==cnt2[p]:
    ans += 1
print(ans)

Submission status: Accepted

Solution code:
N, M, *I = map(int, open(0).read().split())
H, AB = [0] + I[:N], I[N:]

memo = [False] + [True] * N
for a, b in zip(*[iter(AB)] * 2):
    if H[a] < H[b]:
        memo[a] = False
    elif H[b] < H[a]:
        memo[b] = False
    else:
        memo[a] = memo[b] = False

print(sum(memo))

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
H = [int(x) for x in input().split()]
A = [0] * M
B = [0] * M
F = [0] * N
for i in range(M):
    A[i], B[i] = map(int, input().split())
    F[A[i] - 1] = max(F[A[i] - 1], H[B[i] - 1])
    F[B[i] - 1] = max(F[B[i] - 1], H[A[i] - 1])

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

print(ans)

Submission status: Accepted

Solution code:
num_tower, num_path = [int(ipt) for ipt in input().split(' ')]

heights = [0] + [int(h) for h in input().split(' ')]

bad_towers = set()

for p in range(num_path):
  tower_1, tower_2 = [int(t) for t in input().split(' ')]
  # either one is lower
  if heights[tower_1] < heights[tower_2]:
    bad_towers.add(tower_1)
  elif heights[tower_1] > heights[tower_2]:
  	bad_towers.add(tower_2)    
  # same height
  else:
    bad_towers.add(tower_1)
    bad_towers.add(tower_2)
    
print(num_tower - len(bad_towers))

Submission status: Accepted

Solution code:
a=input().split()
N=int(a[0])
M=int(a[1])
H=[int(x) for x in input().split()]
way=[]
for i in range(M):
    way.append([int(x) for x in input().split()])

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

for h in way:
    dic[h[0]-1].add(h[1]-1)
    dic[h[1]-1].add(h[0]-1)
    

print(sum(all([H[i]>H[hs] for hs in dic[i]])for i in range(N)))

Submission status: Accepted

Solution code:

class abc_166:
    
    def __init__(self):
        pass
    
    def A(self):
        S=input()
        ans= "ARC" if S=="ABC" else "ABC"
        print(ans)
    
    def B(self):
        NK=list(map(int,input().split()))
        d=[]
        A=[]
        
        for i in range(NK[1]):
            d=int(input())
            a = list(map(int,input().split()))
            A.extend(a)
        
        print(NK[0]-len(list(set(A))))  
            
    def C(self):
        NM=list(map(int,input().split()))
        H=list(map(int,input().split()))
        A=[list(map(int,input().split())) for i in range(NM[1])]
        memo=[0]*(NM[0])
        count=0
        
        #メモ配列初期化
        for i in range(len(memo)):memo[i]=H[i]
        #メモ化処理
        for i in A:
            if H[i[0]-1]>H[i[1]-1]:memo[i[1]-1]=H[i[0]-1]
            elif H[i[0]-1]<H[i[1]-1]:memo[i[0]-1]=H[i[1]-1]
            else:
                memo[i[0]-1]=0
                memo[i[1]-1]=0
                
        for i in range(NM[0]):
            if H[i]==memo[i]:count+=1
            else:pass
        print(count)
    
    
    def D(self):
        pass
    
    def E(self):
        pass
    
    def F(self):
        pass
    
    
if __name__=='__main__':
    obj=abc_166()
    obj.C()

Submission status: Accepted

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

for j in range(m):

    if h[l[j][1]]>=h[l[j][0]]:
        g[l[j][0]]=0
    if h[l[j][1]]<=h[l[j][0]]:
        g[l[j][1]]=0

print(g.count(1))

Submission status: Accepted

Solution code:
import copy

def main():
  n,m = map(int,input().split())
  s = [int(n) for n in input().split()]
  cs = copy.copy(s)
  for i in range(m):
    a,b = map(int,input().split())
    a-=1
    b-=1
    if(s[a] < s[b]):
      cs[a] = -1
    elif(s[a] == s[b]):
      cs[a] = -1
      cs[b] = -1
    elif(s[b] < s[a]):
      cs[b] = -1
  print(len(cs)-cs.count(-1))
      
if __name__ == '__main__':
  main()

Submission status: Accepted

Solution code:

class abc_166:
    
    def __init__(self):
        pass
    
    def A(self):
        S=input()
        ans= "ARC" if S=="ABC" else "ABC"
        print(ans)
    
    def B(self):
        NK=list(map(int,input().split()))
        d=[]
        A=[]
        
        for i in range(NK[1]):
            d=int(input())
            a = list(map(int,input().split()))
            A.extend(a)
        
        print(NK[0]-len(list(set(A))))  
            
    def C(self):
        NM=list(map(int,input().split()))
        H=list(map(int,input().split()))
        A=[list(map(int,input().split())) for i in range(NM[1])]
        memo=[0]*(NM[0])
        count=0
        
        for i in range(len(memo)):memo[i]=H[i]
        
        #メモ化処理
        for i in A:
            if H[i[0]-1]>H[i[1]-1]:
                memo[i[1]-1]=H[i[0]-1]
            elif H[i[0]-1]==H[i[1]-1]:
                memo[i[0]-1]=0
                memo[i[1]-1]=0
            else:
                memo[i[0]-1]=H[i[1]-1]
                
        
        for i in range(NM[0]):
            if H[i]==memo[i]:count+=1
            else:pass
        
        print(count)
    
    
    def D(self):
        pass
    
    def E(self):
        pass
    
    def F(self):
        pass
    
    
if __name__=='__main__':
    obj=abc_166()
    obj.C()

Submission status: Accepted

Solution code:
# coding: utf-8


def solve(*args: str) -> str:
    n, m = map(int, args[0].split())
    H = [0]+list(map(int, args[1].split()))
    AB = [tuple(map(int, ab.split())) for ab in args[2:]]

    G = [True]*(n+1)
    for a, b in AB:
        G[a] &= H[b] < H[a]
        G[b] &= H[a] < H[b]

    return str(sum(G[1:]))


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))

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

Submission status: Accepted

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

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

for n in range(N):
  if not T[n]:
    flg[n] =1
  else:
    MAX=max([H[t-1] for t in T[n]])
    if H[n]>MAX:
    	flg[n]=1

print(sum(flg))

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
H = [int(x) for x in input().split()]
A = [0 for x in range(M)]
B = [0 for x in range(M)]
C = []
flag = True
for i in range(M) :
    A[i],B[i] = map(int,input().split())
    C.append([A[i],B[i]])
G = [1 for x in range(N)]

for i in range(M) :
    if H[C[i][0]-1] < H[C[i][1]-1] :
        G[C[i][0]-1] = 0
    elif H[C[i][0]-1] == H[C[i][1]-1] :
        G[C[i][0]-1] = 0
        G[C[i][1]-1] = 0
    else :
        G[C[i][1]-1] = 0
    
print(sum(G))

Submission status: Accepted

Solution code:
obs, roads = [int(x) for x in input().split()]
heights = [int(x) for x in input().split()]
goodone = [1] * obs
for _ in range(roads):
    a, b = [int(x) for x in input().split()]
    if heights[a - 1] <= heights[b - 1]:
        goodone[a - 1] -= goodone[a - 1]
    if heights[a - 1]  >=  heights[b - 1]:
        goodone[b - 1] -= goodone[b - 1]
print(sum(goodone))

Submission status: Accepted

Solution code:
x,try_k = map(int,input().split())

input_x = input().split()

list_a = [0]*x
list_b = [[] for i in range(x)]
for i in range(len(list_a)):
  list_a[i] = int(input_x[i])

for i in range(try_k):
  a,b = map(int,input().split())
  
  list_b[b-1].append(list_a[a-1])
  list_b[a-1].append(list_a[b-1])
  
#print(list_b)
count = 0
for i in range(x):
  if(len(list_b[i]) == 0):
     count += 1
     continue
  if(list_a[i] > max(list_b[i]) ):
    count += 1
print(count)

Submission status: Accepted

Solution code:
n,m = map(int, input().split())
h = list(map(int, input().split()))
ans = [True for _ in range(n)]
for i in range(m):
    a,b = map(lambda z:int(z)-1,input().split())
    if h[a] >= h[b]:
        ans[b] = False
    if h[b]>=h[a]:
        ans[a] = False

print(sum(ans))

Submission status: Accepted

Solution code:
from sys import stdin, setrecursionlimit

setrecursionlimit(10 ** 9)


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


N, M = map(int, input().split())
H = list(map(int, input().split()))
ans = [True] * N
for _ in range(M):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    if H[a] < H[b]:
        ans[a] = False
    elif H[a] > H[b]:
        ans[b] = False
    else:
        ans[a] = False
        ans[b] = False

print(sum(ans))

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

def main():
    N,M = map(int, readline().split())
    H = [int(i) for i in readline().split()]
    ab = map(int, read().split())

    E = [0] * N
    for i, (a, b) in enumerate(zip(*[iter(ab)]*2)):
        if H[b-1] > E[a-1]:
            E[a-1] = H[b-1]
        if H[a-1] > E[b-1]:
            E[b-1] = H[a-1]

    ans = 0
    for i,h in enumerate(H):
        if h > E[i]:
            ans += 1
    
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict

N, M = [int(el) for el in input().split()]

hts = [int(el) for el in input().split()]
heights = {}
mh = {}
for i, val in enumerate(hts, start=1):
    heights[i] = val
    mh[i] = 0

for _ in range(M):
    s, d = [int(el) for el in input().split()]
    mh[s] = max(mh[s], heights[d])
    mh[d] = max(mh[d], heights[s])

ans = 0
for i in range(1, N + 1):
    if heights[i] > mh[i]:
        ans += 1

print(ans)

Submission status: Accepted

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

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

print(sum(A))

Submission status: Accepted

Solution code:
import heapq

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

d={i:[0] for i in range(1,N+1)}

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

ans=0
for i in range(1,N+1):
    hq=d[i]
    heapq.heapify(hq)
    s=heapq.heappop(hq)
    if (-s)<H[i-1]:
        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())))

# Trueで初期化
isBest = [True for i in range(N)]

# 自分より高いものが一つでもあったらFalseにする
# ・同じ展望台の組を結ぶ道が複数あってもFalseを上書きするだけなので問題ない
for ab in AB:
    numA = ab[0] - 1
    numB = ab[1] - 1
    if (H[numA] <=H[numB]):
        isBest[numA] = False
    if (H[numB] <=H[numA]):
        isBest[numB] = False

# 良い展望台を数える
ans = 0
for z in isBest:
    if (z == True):
        ans += 1
print(ans)

Submission status: Accepted

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

for i in range(M):
  A, B = map(int, input().split())
  clist[A-1] += 1
  clist[B-1] += 1
  if H[A-1] > H[B-1]:
    hlist[A-1] += 1
  elif H[A-1] < H[B-1]:
    hlist[B-1] += 1

for i in range(N):
  if hlist[i] == clist[i]:
    cnt += 1

print(cnt)

Submission status: Accepted

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

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

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

count = 0

dic = {}

for i in range(1, N+1):
  dic[i] = set()

for hen in V:
  dic[hen[0]].add(hen[1])
  dic[hen[1]].add(hen[0])

print(sum(all([H[i] > H[hs] for hs in dic[i]]) for i in range(1, N+1)))

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
h_list = list(map(int, input().split()))
r_list = {}
all_list = set()
for i in range(m):
	a, b = map(int, input().split())
	all_list.add(a)
	all_list.add(b)
	if a in r_list.keys():
		r_list[a].add(b)
	else:
		r_list[a] = {b}
	if b in r_list.keys():
		r_list[b].add(a)
	else:
		r_list[b] = {a}
count = n - len(all_list)
for key in r_list.keys():
	r_set = r_list[key]
	heights = list(map(lambda i: h_list[i-1], r_set))
	height = h_list[key - 1]
	if height > max(heights):
		count += 1
print(count)

Submission status: Accepted

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

def main():
    n, m = map(int, input().split())
    h_list = list(map(int, input().split()))
    arry = [0 for _ in range(n)]
    ans = 0

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

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

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
h = list(map(int, input().split()))
maxh = []
for height in h:
    maxh.append(0)
for i in range(m):
    a, b = map(int, input().split())
    a, b = a-1, b-1
    maxh[a] = max(maxh[a], h[b])
    maxh[b] = max(maxh[b], h[a])
g = 0
for height, maxheight in zip(h, maxh):
    if height > maxheight:
        g += 1
print(g)

Submission status: Accepted

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


for i in range(n):
    if g[i] < 0:
        continue
    co+=1

print(co)

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 = [[] for i in range(n)]
ans=[0]*n
for x,y in a:
    b[x-1].append(y-1)
    b[y-1].append(x-1)
for i in range(n):
    b[i]=set(b[i])

for i in range(n):
    x=[]
    y=[[0,0]]
    x.append([i,h[i]])
    for j in b[i]:
        y.append([j,h[j]])
    y.sort(key=lambda y:y[1])
    y.reverse()
    if x[0][1]>y[0][1]:
        ans[x[0][0]]=1

cnt=0
for i in range(n):
    cnt+=ans[i]

print(cnt)

Submission status: Accepted

Solution code:
import sys

lines = sys.stdin.readlines()

X = lines[0].split(' ')
N = int(X[0])
M = int(X[1])

H = []
Y = []

H=lines[1].split(' ')

for j in range(M):
    A = int(lines[j+2].split(' ')[0])
    B = int(lines[j+2].split(' ')[1])
    if int(H[A-1]) <= int(H[B-1]):      
      Y.append(A-1)
    if int(H[B-1]) <= int(H[A-1]):
      Y.append(B-1)
Z = len(set(Y))
print(N-Z)

Submission status: Accepted

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

label=[-1]*N
Edge=[[] for _ in range(N)]
for i in range(M):
    A,B=map(int,input().split())
    Edge[A-1].append(B-1)
    Edge[B-1].append(A-1)
out=0
for i in range(N):
    S=0
    for ii in Edge[i]:
        S=max(S,H[ii])
    if S<H[i]:
        out+=1
print(out)
# out=0
# for i in range(N):
#     if label[i]==-1:
#         S=0
#         CN=0
#         stack=[i]
#         while stack:
#             T=stack.pop()
#             label[T]=0
#             for ii in Edge[i]:
#                 if label[ii]==-1:
#                     stack.append(ii)
#                     label[ii]=0
#             if S<H[T]:
#                 S=H[T]
#                 CN=1
#             elif S==H[T]:
#                 CN=0
#         out+=CN
# print(out)

Submission status: Accepted

Solution code:
N, M, *I = map(int, open(0).read().split())
H, AB = [0] + I[:N], I[N:]

memo = [0] * (N + 1)
for a, b in zip(*[iter(AB)] * 2):
    memo[a] = max(memo[a], H[b])
    memo[b] = max(memo[b], H[a])

print(sum(h > ma for h, ma in zip(H[1:], memo[1:])))

Submission status: Accepted

Solution code:
n,m  = map(int, input().split())
ten = list(map(int, input().split()))
arr = [list(map(int,input().split())) for i in range(m)]
hikui = []
for i in arr:
    if ten[i[0]-1]<ten[i[1]-1]:
        hikui.append(i[0])
    elif ten[i[1]-1]<ten[i[0]-1]:
        hikui.append(i[1])
    else:
        hikui.append(i[0])
        hikui.append(i[1])
ans = n-len(set(hikui))

print(ans)

Submission status: Accepted

Solution code:

n,m = map(int,input().split())
l=list(map(int,input().split()))
r=[True]*(n+1)
r[0]=False
d={}
for i in range(m):
    a,b=map(int,input().split())
    if l[a-1]>l[b-1]:
        r[b]=False
    if l[a-1]<l[b-1]:
        r[a]=False
    if l[a-1]==l[b-1]:
        r[a]=False
        r[b]=False
cnt=0
for i in r:
    if i:
        cnt+=1

print(cnt)

Submission status: Accepted

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

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

print(li.count(0))

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
h = list(map(int,input().split()))
c = dict()
for i in range(m):
    a, b = map(int,input().split())
    if a in c:
        c[a].append(b)
    else:
        c[a] = [b]
    if b in c:
        c[b].append(a)
    else:
        c[b] = [a]
        
cnt = n
for k,v in c.items():
    for i in range(len(v)):
        if h[v[i] - 1] >= h[k - 1]:
            cnt -= 1
            break
print(cnt)

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
H=list(map(int,input().split()))
tunagari=[[] for i in range(N)]
for i in range(M):
  A,B=map(int,input().split())
  tunagari[A-1]+=[B-1]
  tunagari[B-1]+=[A-1]
ans=0
for i in range(N):
  tmpl=tunagari[i]
  n=len(tmpl)
  if n==0 :
    ans+=1
  else:
    for j in range(n):
      tmpl[j]=H[tmpl[j]]
    maxh=max(tmpl)
    if maxh<H[i]:
      ans+=1
print(ans)

Submission status: Accepted

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

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

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

graph = [[] for _ in range(N)]

for a, b in AB:
  a, b = a-1, b-1
  graph[a].append(b)
  graph[b].append(a)

  ans = 0

for i, h in enumerate(H):
  flag = True
  for to in graph[i]:
    if H[i] > H[to]:
      continue
    else:
      flag = False
    
  if flag:
    ans += 1
  
print(ans)

Submission status: Accepted

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

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

a = [True for i in range(N)]

for i in range(M):
  A,B = map(int, input().split())
  if H[A-1] < H[B-1]:
    a[A-1] = False
  elif H[A-1] > H[B-1]:
    a[B-1] = False
  elif H[A-1]== H[B-1]:
    a[A-1] = False
    a[B-1] = False

print(len([0 for i in a if i == True]))

Submission status: Accepted

Solution code:
L=lambda:list(map(int,input().split()))
n,m=L();h=L()
e,c=[[]for _ in range(n)],0
for i in range(m):
  a,b=L();e[a-1]+=b-1,;e[b-1]+=a-1,
for i in range(n):
  if all(h[i]>h[v]for v in e[i]):c+=1
print(c)

Submission status: Accepted

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

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

tele = {}
for num, h in enumerate(height, 1):
    tele[num] = [h, "G"]

for roads in range(m):
    a, b = list(map(int, input().split()))
    if (tele[a][0] > tele[b][0]):
        tele[b][1] = "N"
    elif (tele[a][0] < tele[b][0]):
        tele[a][1] = "N"
    elif (tele[a][0] == tele[b][0]):
        tele[a][1] = "N"
        tele[b][1] = "N"

ans_list = tele.values()
ans = 0
for a in ans_list:
    if (a[1] == "G"):
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
N, M =map(int, input().split())
H_tree = [0] + [int(n) for n in input().split()]
GOOD_tree = [0] + [1 for n in range(N)]
 
for i in range(M):
  A, B = map(int, input().split())
  if H_tree[A]<=H_tree[B]:GOOD_tree[A] = 0
  if H_tree[A]>=H_tree[B]:GOOD_tree[B] = 0
print(sum(GOOD_tree))

Submission status: Accepted

Solution code:
n,m = map(int, input().split())
H = list(map(int, input().split()))
s = [[0] for i in range(n)]
for i in range(m):
    a, b = map(int, input().split())
    s[a-1].append(H[b-1])
    s[b-1].append(H[a-1])
c = 0
for j in range(n):
    if H[j] > max(s[j]):
        c+= 1
print(c)

Submission status: Accepted

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

def main():
  n,m = map(int, input().split())
  heights = tuple(map(int, input().split()))

  roads = [tuple(map(int, input().split())) for _ in range(m)]
  max_heights = [0 for _ in range(n)]

  for i in range(m):
    build_1 = roads[i][0]-1
    build_2 = roads[i][1]-1
    if heights[build_2] > max_heights[build_1]:
      max_heights[build_1] = heights[build_2]
    if heights[build_1] > max_heights[build_2]:
      max_heights[build_2] = heights[build_1]

  sum = 0
  for i in range(n):
    if heights[i] > max_heights[i]:
      sum += 1
  print(sum)

if __name__ == '__main__':
  main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N,M = map(int, input().split())
h = list(map(int, input().split()))
ma = [0]*N
for i in range(M):
    a,b = map(int,input().split())
    ma[a-1] = max(ma[a-1],h[b-1])
    ma[b-1] = max(ma[b-1],h[a-1])
ans = 0
for a in range(N):
    if h[a] > ma[a]:
        ans = ans + 1

print(ans)

Submission status: Accepted

Solution code:
N, M =map(int, input().split())
H_tree = [0] + [int(n) for n in input().split()]
GOOD_Tree = [0] + [1 for n in range(N)]
 
for i in range(M):
  A, B = map(int, input().split())
  if H_tree[A]<=H_tree[B]:GOOD_Tree[A] = 0
  if H_tree[A]>=H_tree[B]:GOOD_Tree[B] = 0
print(sum(GOOD_Tree))

Submission status: Accepted

Solution code:
import time
startTimeProblem=time.time()

import fileinput, sys, itertools, functools
from math import *
from bisect import *
from heapq import *
from collections import *

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

class InputHelper:
    def __init__(self):
        self.myinput = fileinput.input()

    def isLocal(self):
        return not fileinput.isstdin()

    def int(self):
        return int(self.myinput.readline().rstrip())

    def ints(self):
        return [int(_) for _ in self.myinput.readline().rstrip().split()]

    def str(self):
        return self.myinput.readline().rstrip()

    def strs(self):
        return [_ for _ in self.myinput.readline().rstrip().split()]

class OutputHelper:
    def int(self, a):
        print(a)    

    def ints(self, a):  
        print(" ".join([str(_) for _ in a]))
    
    def intsNL(self, a):
        for _ in a:
            print(_)
    
    def str(self, s):
        print(s)

    def strs(self, s):
        print(" ".join([_ for _ in s]))

    def strsNL(self, s):
        for st in s:
            print(st)

class ListNode:
    def __init__(self, val):
        self.val = val
        self.next = None
        self.prev = None

In = InputHelper()
Out = OutputHelper()

######################################

N, M = In.ints()
H = [0]+In.ints()

hasBigger = [False]*(N+1)
for i in range(M):
    a,b = In.ints()
    
    if H[a]>=H[b]:
        hasBigger[b]=True
    
    if H[b]>=H[a]:
        hasBigger[a]=True

Out.int(hasBigger.count(False)-1)






######################################

if len(sys.argv)>2 and sys.argv[2]=="TIMEIT":
    fin = (time.time()-startTimeProblem)*1000
    print("{:.2f}".format(fin) + "ms")

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):
        h = [H[j - 1] for j in v]
        if not h or H[i] > max(h):
            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 = map(int,input().split())
h = list(map(int,input().split()))
q = [1]*n
for i in range(m):
    a,b = map(int,input().split())
    if h[a-1] < h[b-1]:
        q[a-1] = 0
    elif h[a-1] > h[b-1]:
        q[b-1] = 0
    else:
        q[a-1] = 0
        q[b-1] = 0
print(q.count(1))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
n, m = [int(x) for x in input().split()]
h = [0, *(int(x) for x in input().split())]
adj = [[] for i in range(n + 1)]
for _ in range(m):
    u, v = [int(x) for x in input().split()]
    adj[u].append(v)
    adj[v].append(u)
print(sum(1 for u in range(1, n + 1) if all(h[u] > h[v] for v in adj[u])))

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
h = list(map(int, input().split()))
sore = [[0] for i in range(n)]
for i in range(m):
    road = list(map(int, input().split()))
    sore[road[0]-1].append(h[road[1]-1])
    sore[road[1]-1].append(h[road[0]-1])
ans = 0
for i in range(n):
    if h[i] > max(sore[i]):
        ans+=1
print(ans)

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
H = list(map(int,input().split()))
H = [0] + H
Tree = [0] + [1]*N
for _ in range(M):
  A,B = map(int,input().split())
  if H[A] > H[B]:
    Tree[B] = 0
  elif H[A] == H[B]:
    Tree[A]=0
    Tree[B]=0
  else:
    Tree[A] = 0
print(sum(Tree))

Submission status: Accepted

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

Submission status: Accepted

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

 
ans = 0
for i in range(N): #i番目の展望台に注目
    if michi[i] == []:
        ans +=1
    else:
        counter = 0
        # カウンターを追加
        for j in michi[i]:
            counter += 1
            # インクリメント
        # print(i,j,H[i],H[j]) 
        # このprintを消した
            if H[i] <= H[j]:
            #   不等号を直した
                break
            if counter == len(michi[i]):
                # 最後までいったらの判定の変更
                ans += 1
 
print(ans)