Problem:


Score : 300 points

Problem Statement

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

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

How many good observatories are there?

Constraints

2 \leq N \leq 10^5

1 \leq M \leq 10^5

1 \leq H_i \leq 10^9

1 \leq A_i,B_i \leq N

A_i \neq B_i

Multiple roads may connect the same pair of observatories.

All values in input are integers.

Input

Input is given from Standard Input in the following format:

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

Output

Print the number of good observatories.

Sample Input 1

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

Sample Output 1

2

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

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

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

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

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

Sample Input 2

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

Sample Output 2

3



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


Sample output:
2

Submission status: Accepted

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


def solve(N: int, M: int, H: "List[int]", A: "List[int]", B: "List[int]"):
    good = [True] * N

    for Ai1, Bi1 in zip(A, B):
        Ai = Ai1 - 1
        Bi = Bi1 - 1
        if H[Ai] > H[Bi]:
            good[Bi] = False
        elif H[Ai] < H[Bi]:
            good[Ai] = False
        else:
            good[Ai] = False
            good[Bi] = False

    print(good.count(True))
    return


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()))
ans = [1 for i in range(n)]
for i in range(m):
    a, b = map(int, input().split())
    if h[a-1] < h[b-1]:
        ans[a-1] = 0
    elif h[a-1] > h[b-1]:
        ans[b-1] = 0
    else:
        ans[a-1] = 0
        ans[b-1] = 0
print(sum(ans))

Submission status: Accepted

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


X = [1] * N

for i in range(M):
    a = A[i] - 1
    b = B[i] - 1
    ha = H[a]
    hb = H[b]
    if ha == hb:
        X[a] = 0
        X[b] = 0
    elif ha > hb:
        X[b] = 0
    else:
        X[a] = 0

print(sum(X))

Submission status: Accepted

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

edges = [[] for _ in range(n)]

ok = [True] * n

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

    if ha == hb:
        ok[a] = False
        ok[b] = False

    elif ha > hb:
        ok[b] = False

    elif ha < hb:
        ok[a] = False

print(sum(ok))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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())))
ans={i for i in range(1,N+1)}
for i in range(M):
	if H[a[i][0]-1] == H[a[i][1]-1]:
		dif = {a[i][0],a[i][1]}
	elif H[a[i][0]-1] > H[a[i][1]-1]:
		dif = {a[i][1]}
	else:
		dif = {a[i][0]}
	ans -= dif
print(len(ans))

Submission status: Accepted

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

ans = N
for v in range(N):
  flag = False
  for u in graph[v]:
    if H[v] <= H[u]:
      ans -= 1
      break

    
  
print(ans)

Submission status: Accepted

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

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

print(sum)

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
H = list(map(int,input().split()))
L = [list(map(int,input().split())) for _ in range(m)]
ans = [1 for _ in range(n)]
for l in L:
    if H[l[0]-1] > H[l[1]-1]:
        ans[l[1]-1] = 0
    elif H[l[0]-1] < H[l[1]-1]:
        ans[l[0]-1] = 0
    else:
        ans[l[1]-1] = 0
        ans[l[0]-1] = 0
print(sum(ans))

Submission status: Accepted

Solution code:
N, M = map(int,input().split())
H = list(map(int,input().split()))
state = [1 for _ in range(N)]
path_list = []
count = 0
for _ in range(M):
    A,B = map(int,input().split())
    if H[A-1] >= H[B-1]:
        state[B-1] = 0
    if H[B-1] >= H[A-1]:
        state[A-1] = 0
print(sum(state))

Submission status: Accepted

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

for m in range(M):
    A, B = map(int, input().split())
    if H[A-1] <= H[B-1]:
        result[A-1] = 0
    if H[A-1] >= H[B-1]:
        result[B-1] = 0

print(sum(result))

Submission status: Accepted

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

ans = [0] * n
for a, b in AB:
    if H[a-1] < H[b-1]:
        ans[a - 1] += 1
    elif H[a-1] > H[b-1]:
        ans[b - 1] += 1
    else:
        ans[a - 1] += 1
        ans[b - 1] += 1


print(ans.count(0))

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, gcd
from itertools import accumulate, permutations, combinations, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, M = MAP()
H = LIST()
AB = [LIST() for _ in range(M)]

HH = [1]*N
for i in range(M):
	if H[AB[i][0]-1] > H[AB[i][1]-1]:
		HH[AB[i][1]-1] = 0
	elif H[AB[i][0]-1] < H[AB[i][1]-1]:
		HH[AB[i][0]-1] = 0
	else:
		HH[AB[i][1]-1] = 0
		HH[AB[i][0]-1] = 0


print(sum(HH))

Submission status: Accepted

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

roots = [[] for i in range(N)]

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

ans = 0
for i in range(len(roots)):
    root = roots[i]
    if not root:
        ans += 1
        continue
    good = True
    for j in root:
        if heights[i] <= heights[j]:
            good = False
            break
    if good:
        ans += 1

print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

def main():
     n, m = map(int, input().split())
     n_list = list(map(int, input().split()))
     ans = [1 for i in range(n)]

     for i in range(m):
          path = list(map(int, input().split()))
          first = path[0]-1
          second = path[1]-1
          if n_list[first] < n_list[second]:
               ans[first] = 0
          elif n_list[second] < n_list[first]:
               ans[second] = 0
          else:
               ans[first] = 0
               ans[second] = 0
     
     print(sum(ans))

if __name__ == "__main__":
    main()

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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


G = [[] for _ in range(N)]
for el in AB:
    A, B = el
    A -= 1
    B -= 1
    G[A].append(B)
    G[B].append(A)
# print(H)
# print(G)

cnt = 0
for i in range(N):
    flag = True
    for next in G[i]:
        if H[i] <= H[next]:
            flag = False
    if flag:
        # print(i)
        cnt += 1
print(cnt)

Submission status: Accepted

Solution code:
# coding: utf-8
import re
import math
from collections import defaultdict
import itertools
from copy import deepcopy
import random
from heapq import heappop,heappush
import time
import os
import queue
import sys
import datetime
from functools import lru_cache
#@lru_cache(maxsize=None)
readline=sys.stdin.readline
sys.setrecursionlimit(2000000)
#import numpy as np
alphabet="abcdefghijklmnopqrstuvwxyz"
mod=int(10**9+7)
inf=int(10**20)
def yn(b):
    if b:
        print("yes")
    else:
        print("no")
def Yn(b):
    if b:
        print("Yes")
    else:
        print("No")
def YN(b):
    if b:
        print("YES")
    else:
        print("NO")
class union_find():
    def __init__(self,n):
        self.n=n
        self.P=[a for a in range(N)]
        self.rank=[0]*n
 
    def find(self,x):
        if(x!=self.P[x]):self.P[x]=self.find(self.P[x])
        return self.P[x]
 
    def same(self,x,y):
        return self.find(x)==self.find(y)
 
    def link(self,x,y):
        if self.rank[x]<self.rank[y]:
            self.P[x]=y
        elif self.rank[y]<self.rank[x]:
            self.P[y]=x
        else:
            self.P[x]=y
            self.rank[y]+=1
 
    def unite(self,x,y):
        self.link(self.find(x),self.find(y))
 
    def size(self):
        S=set()
        for a in range(self.n):
            S.add(self.find(a))
        return len(S)
def is_power(a,b):#aはbの累乗数か
    now=b
    while now<a:
        now*=b
    if now==a:return True
    else:return False
def bin_(num,size):
    A=[0]*size
    for a in range(size):
        if (num>>(size-a-1))&1==1:
            A[a]=1
        else:
            A[a]=0
    return A
def get_facs(n,mod_=0):
    A=[1]*(n+1)
    for a in range(2,len(A)):
        A[a]=A[a-1]*a
        if(mod>0):A[a]%=mod_
    return A
def comb(n,r,mod,fac):
    if(n-r<0):return 0
    return (fac[n]*pow(fac[n-r],mod-2,mod)*pow(fac[r],mod-2,mod))%mod
def next_comb(num,size):
    x=num&(-num)
    y=num+x
    z=num&(~y)
    z//=x
    z=z>>1
    num=(y|z)
    if(num>=(1<<size)):return False
    else:
        return num
def get_primes(n,type="int"):
    A=[True]*(n+1)
    A[0]=False
    A[1]=False
    for a in range(2,n+1):
        if A[a]:
            for b in range(a*2,n+1,a):
                A[b]=False
    if(type=="bool"):return A
    B=[]
    for a in range(n+1):
        if(A[a]):B.append(a)
    return B
def is_prime(num):
    if(num<=2):return False
    i=2
    while i*i<=num:
       if(num%i==0):return False
       i+=1
    return True
def ifelse(a,b,c):
    if a:return b
    else:return  c
def join(A,c=" "):
    n=len(A)
    A=list(map(str,A))
    s=""
    for a in range(n):
        s+=A[a]
        if(a<n-1):s+=c
    return s
def factorize(n,type_="dict"):
    b = 2
    list_ = []
    while b * b <= n:
        while n % b == 0:
            n //= b
            list_.append(b)
        b+=1
    if n > 1:list_.append(n)
    if type_=="dict":
        dic={}
        for a in list_:
            if a in dic:
                dic[a]+=1
            else:
                dic[a]=1
        return dic
    elif type_=="list":
        return list_
    else:
        return None
def floor_(n,x=1):
    return x*(n//x)
def ceil_(n,x=1):
    return x*((n+x-1)//x)
def hani(x,min_,max_):
    ret=x
    if x<min_:ret=min_
    if x>max_:ret=max_
    return ret
def seifu(x):
    return x//abs(x)
###################################################
def f():
    return
def main():
    n,m=map(int,input().split())
    H=list(map(int,input().split()))
    A=[0]*m
    B=[0]*m
    G=[0]*n
    for a in range(m):
        x,y=map(int,input().split())
        x-=1
        y-=1
        G[x]=max(G[x],H[y])
        G[y]=max(G[y],H[x])
    ans=0
    for i in range(n):
        if G[i]<H[i]:
            ans+=1
    print(ans)

main()

Submission status: Accepted

Solution code:
def main():
    nm = list(map(int, input().split()))
    h = list(map(int, input().split()))
    ab = [None]*nm[1]
    for i in range(nm[1]):
        ab[i] = list(map(int, input().split()))

    memo = [0]*nm[0]
    for i in range(nm[1]):
        a = ab[i][0]-1
        b = ab[i][1]-1
        if h[a] > h[b]:
            memo[b] = 1
        elif h[a] < h[b]:
            memo[a] = 1
        else:
            memo[a] = 1
            memo[b] = 1
    
    print(memo.count(0))

if __name__ == '__main__':
    main()

Submission status: Accepted

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


# 入力を整数に変換して受け取る
def input_int():
    return int(input())


# マイナス1した値を返却
def int1(x):
    return int(x) - 1


# 半角スペース区切り入力をIntに変換してMapで受け取る
def input_to_int_map():
    return map(int, input().split())


# 半角スペース区切り入力をIntに変換して受け取る
def input_to_int_tuple():
    return tuple(map(int, input().split()))


# 半角スペース区切り入力をIntに変換してマイナス1した値を受け取る
def input_to_int_tuple_minus1():
    return tuple(map(int1, input().split()))


def main():
    n, m = input_to_int_map()
    h = input_to_int_tuple()

    roads = [input_to_int_tuple() for i in range(m)]

    ret = set([i + 1 for i in range(n)])

    for road in roads:
        a_h = h[road[0] - 1]
        b_h = h[road[1] - 1]

        if a_h > b_h:
            ret -= set([road[1]])

        if b_h > a_h:
            ret -= set([road[0]])

        if b_h == a_h:
            ret -= set([road[0]])
            ret -= set([road[1]])

    print(len(ret))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
h=[int(i) for i in input().split()]
rel=[set() for _ in range(n)]
for i in range(m):
  a,b=map(int,input().split())
  if h[a-1]<=h[b-1]:
    rel[a-1].add(b)
  if h[a-1]>=h[b-1]:
    rel[b-1].add(a)
ans=0
for l in rel:
  if len(l)==0:
    ans+=1
print(ans)

Submission status: Accepted

Solution code:
# print('input >>')
N, M = map(int,(input().split()))
H = list(map(int,(input().split())))
ABs = []
for _ in range(M):
    ABs.append(tuple(map(int,(input().split()))))

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

for AB in ABs:
    A, B = AB
    lists[A-1] += [H[B-1]]
    lists[B-1] += [H[A-1]]

ans = 0

for i, list_ in enumerate(lists):
    if all([H[i] > h for h in list_]) or len(list_) == 0:
        ans += 1

# print('-----output-----')
print(ans)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
peaks = list(map(int, input().split()))
ng_peaks = set([])
for j in range(M):
    A_j, B_j = map(int, input().split())
    if peaks[A_j-1] >= peaks[B_j-1]:
        ng_peaks.add(B_j)
    if peaks[A_j-1] <= peaks[B_j-1]:
        ng_peaks.add(A_j)
print(N-len(ng_peaks))

Submission status: Accepted

Solution code:
import numpy as np
n,m = [int(i) for i in input().split()]

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

l = [[int(i)-1 for i in input().split()] for _ in range(m)]

ans = np.array([1 for _ in range(n)])

for x,y in l:
    if h[x]>h[y]:
        ans[y] = 0
    elif h[x] < h[y]:
        ans[x] = 0
    else:
        ans[x] = 0
        ans[y] = 0
        
print(np.count_nonzero(ans))

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
H = list(map(int,input().split()))
L = [[] for _ in range(N)]
for i in range(M):
    A,B = map(int,input().split())
    L[A-1].append(B-1)
    L[B-1].append(A-1)
ans = 0
for i in range(N):
    a = True
    for j in L[i]:
        if H[i] <= H[j]:
            a = False
            break
    if a:
        ans += 1
print(ans)

Submission status: Accepted

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

G = [0] * N

for a, b in AB:
    a -= 1
    b -= 1
    G[a] = max(G[a], H[b])
    G[b] = max(G[b], H[a])

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

print(ans)

Submission status: Accepted

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

is_best = [True] * n


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

    is_best[a] &= H[a] > H[b]
    is_best[b] &= H[a] < H[b]

print(is_best.count(True))

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
H = list(map(int, input().split()))
check = [1]*N
for m in range(M):
  ab =  list(map(int, input().split()))
  if H[ab[0]-1] > H[ab[1]-1]:
    check[ab[1]-1] = 0
  elif H[ab[1]-1] > H[ab[0]-1]:
    check[ab[0]-1] = 0
  elif H[ab[1]-1] == H[ab[0]-1]:
    check[ab[0]-1] = 0
    check[ab[1]-1] = 0
print(sum(check))

Submission status: Accepted

Solution code:
def solve():
    n, m = map(int, input().split())
    h = list(map(int, input().split()))
    ans = [1 for _ in range(n)]
    for _ in range(m):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        if h[a] <= h[b]:
            ans[a] = 0
        if h[b] <= h[a]:
            ans[b] = 0
    print(sum(ans))


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
[N,M]=[int(i) for i in input().split()]
H=[int(i) for i in input().split()]
A=[0 for i in range(N)]
ans=0
for i in range(M):
	[x,y]=[int(i) for i in input().split()]
	if H[x-1]-H[y-1]>-1:A[y-1]+=1
	if H[y-1]-H[x-1]>-1:A[x-1]+=1
for i in range(len(A)):
	if A[i]==0:ans+=1
print(ans)

Submission status: Accepted

Solution code:
def resolve():
	n, m = map(int, input().split())
	bs = [[i] for i in list(map(int, input().split()))]
	for i in range(m):
		a, b = map(int, input().split())
		bs[a-1].append(bs[b-1][0])
		bs[b-1].append(bs[a-1][0])
	ans = 0
	for v in bs:
		if len(v) == 1 or v[0] > max(v[1:]):
			ans += 1
	print(ans)
resolve()

Submission status: Accepted

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

good = [True] * N

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

print(good.count(True))

Submission status: Accepted

Solution code:
from functools import reduce
from fractions import gcd
import math
import bisect
import itertools
import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline
INF = float("inf")


def main():
    N, M = map(int, input().split())
    H = list(map(int, input().split()))
    C = [1]*N
    for _ in range(M):
        A, B = map(int, input().split())
        if H[A-1] < H[B-1]:
            C[A-1] = 0
        elif H[A-1] == H[B-1]:
            C[A-1] = 0
            C[B-1] = 0
        else:
            C[B-1] = 0
    
    print(C.count(1))


if __name__ == '__main__':
    main()

Submission status: Accepted

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

from pprint import pprint
from collections import deque, defaultdict
import sys

sys.setrecursionlimit(10 ** 6)
input = sys.stdin.buffer.readline
INF = float("inf")

N, M = map(int, input().split())
H = list(map(int, input().split()))
paths = []
for _ in range(M):
    line = list(map(int, input().split()))
    paths.append(line)

# print(H, path)

flags = [0 for _ in range(N)]
path = [[] for _ in range(N)]
for a, b in paths:
    path[a-1].append(H[b-1])
    path[b-1].append(H[a-1])

# print(path)

for i in range(N):
    if len(path[i]) == 0:
        flags[i] = 1
    else:
        if max(path[i]) < H[i]:
            flags[i] = 1

print(sum(flags))

Submission status: Accepted

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

M = [0] * n

for a, b in AB:
  M[a - 1] = max(M[a - 1], H[b - 1])
  M[b - 1] = max(M[b - 1], H[a - 1])

ans = 0
for i, j in zip(H, M):
  if j == 0 or i > j:
    ans += 1

print(ans)

Submission status: Accepted

Solution code:
def main():
  n,m = map(int,input().split())
  array = [-1] * n

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

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

      array[a] = max(array[a], h[b])
      array[b] = max(array[b], h[a])


  count = 0

  for i in range(n):
    if array[i] == -1:
      count += 1

    elif h[i] > array[i]:
      count += 1
        
  print(count)
    
main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import heapq
class Graph:
    def __init__(self,v,edgelist,w_v = None,directed = False):
        super().__init__()
        self.v = v
        self.w_e = [{} for _ in [0]*self.v]
        self.neighbor = [[] for _ in [0]*self.v]
        self.w_v = w_v
        self.directed = directed

        for i,j,w in edgelist:
            self.w_e[i][j] = w
            self.neighbor[i].append(j)

    def dijkstra(self,v_n):
        d = [float('inf')]*self.v
        d[v_n] = 0
        prev = [-1]*self.v

        queue = []
        for i,d_i in enumerate(d): heapq.heappush(queue,(d_i,i))
        
        while len(queue)>0:
            d_u,u = queue.pop()
            if d[u]<d_u :continue
            for v in self.neighbor[u]:
                alt = d[u]+self.w_e[u][v]
                if d[v]>alt:
                    d[v] = alt
                    prev[v] = u
                    heapq.heappush(queue,(alt,v))

        return d,prev

    def warshallFloyd(self):
        d = [[10**18]*self.v for _ in [0]*self.v]
        for i in range(self.v):
            d[i][i] = 0
            
        for i in range(self.v):
            for j in self.neighbor[i]:
                d[i][j] = self.w_e[i][j]
            
        for i in range(self.v):
            for j in self.neighbor[i]:
                d[i][j] = self.w_e[i][j]
        
        for k in range(self.v):
            for i in range(self.v):
                for j in range(self.v):
                    check = d[i][k] + d[k][j]
                    if d[i][j] > check:
                        d[i][j] = check
        return d

    def prim(self):
        gb = GraphBuilder(self.v,self.directed)

        queue = []
        for i,w in self.w_e[0].items(): heapq.heappush(queue,(w,0,i))
        rest = [True]*self.v
        rest[0] = False

        while len(queue)>0:
            w,i,j = heapq.heappop(queue)
            if rest[j]:
                gb.addEdge(i,j,w)
                rest[j] = False
                for k,w in self.w_e[j].items():
                    if rest[k]:
                        heapq.heappush(queue,(w,j,k))

        return gb


class Tree():
    def __init__(self,v,e):
        pass

class GraphBuilder():
    def __init__(self,v,directed = False):
        self.v = v
        self.directed = directed
        self.edge = []

    def addEdge(self,i,j,w=1):
        if not self.directed:
            self.edge.append((j,i,w))
        self.edge.append((i,j,w))

    def addEdges(self,edgelist,weight = True):
        if weight:
            if self.directed:
                for i,j,w in edgelist:
                    self.edge.append((i,j,w))
            else:
                for i,j,w in edgelist:
                    self.edge.append((i,j,w))
                    self.edge.append((j,i,w))
        else:
            if self.directed:
                for i,j in edgelist:
                    self.edge.append((i,j,1))
            else:
                for i,j in edgelist:
                    self.edge.append((i,j,1))
                    self.edge.append((j,i,1))
            

    def addAdjMat(self, mat):
        for i,mat_i in enumerate(mat):
            for j,w in enumerate(mat_i):
                self.edge.append((i,j,w))

    def buildTree(self):
        pass

    def buildGraph(self):
        return Graph(self.v,self.edge,directed=self.directed)

def main():
    n,m = tuple([int(t)for t in input().split()])

    h = tuple([int(t)for t in input().split()])

    path = [[int(t)-1 for t in input().split()]for _ in [0]*m]

    gb = GraphBuilder(n)
    gb.addEdges(path,False)

    g = gb.buildGraph()

    ans = 0
    counter = [False]*n

    for i in range(n):
        if counter[i]:
            continue
        if all([h[i]>h[j]for j in g.neighbor[i]]):
            for j in g.neighbor[i]:
                counter[j] = True
            ans+=1

    print(ans)
            

if __name__ == "__main__":
    main()

Submission status: Accepted

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

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

edges = [[] for i in range(N)]
for a,b in AB:
    edges[a - 1].append(b - 1)
    edges[b - 1].append(a - 1)

a = [None] * N

def test(n):
    for t in edges[n]:
        if H[t] > H[n]:
            a[n] = False
            return
        elif H[t] == H[n]:
            a[t] = a[n] = False
            return
        else:
            a[t] = False
    a[n] = True
    return

for i in range(N):
    if a[i] is None:
        test(i)

print(a.count(True))

Submission status: Accepted

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

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

S = [True for i in range(N)]
A = []

for i in range(M):
  a,b = list(map(int,input().split()))
  if H[a-1] < H[b-1]:
    S[a-1]= False
  elif H[a-1] > H[b-1]:
    S[b-1]= False
  elif H[a-1] == H[b-1]:
    S[a-1]= False
    S[b-1]= False
print(sum(S))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)
from math import floor,ceil,sqrt,factorial,log
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from operator import itemgetter
from fractions import gcd
mod = 10 ** 9 + 7
inf = float('inf')
ninf = -float('inf')
 
#整数input
def ii(): return int(sys.stdin.readline().rstrip()) #int(input())
def mii(): return map(int,sys.stdin.readline().rstrip().split())
def limii(): return list(mii()) #list(map(int,input().split()))
def lin(n:int): return [ii() for _ in range(n)]
def llint(n: int): return [limii() for _ in range(n)]
#文字列input
def ss(): return sys.stdin.readline().rstrip() #input()
def mss(): return sys.stdin.readline().rstrip().split()
def limss(): return list(mss()) #list(input().split())
def lst(n:int): return [ss() for _ in range(n)]
def llstr(n: int): return [limss() for _ in range(n)]

#本当に貪欲法か？ DP法では？？
#本当に貪欲法か？ DP法では？？
#本当に貪欲法か？ DP法では？？

n,m=mii()

arr=limii()

mat=[[0] for _ in range(n)]
for i in range(m):
    a,b=mii()
    mat[a-1].append(arr[b-1])
    mat[b-1].append(arr[a-1])
chk=0
for i in range(n):
    if arr[i]>max(mat[i]):
        chk+=1

print(chk)

Submission status: Accepted

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

print(sum(ans))

Submission status: Accepted

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

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

cnt = 0
for tower_i in tower:
    if tower_i == 1:
        cnt = cnt + 1

print( cnt )