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:
#MLE注意！0や1のケースに注意

def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    import math
    #from math import gcd

    #inf = 10**17
    #mod = 10**9 + 7

    n,m = map(int, input().split())
    h = list(map(int, input().split()))
    adj = [[] for _ in range(n)] #頂点数, 場合によって変える
    for _ in range(m):
        a,b = map(int, input().split())
        adj[a-1].append(b-1)
        adj[b-1].append(a-1)
    #-1まだ　0負け確　1良い
    check = [-1]*n
    for i in range(n):
        if check[i] == 0:
            continue
        if len(adj[i]) == 0:
            check[i] = 1
        else:
            for j in adj[i]:
                if h[i] < h[j]:
                    check[i] = 0
                    break
                elif h[i] == h[j]:
                    check[i] = 0
                    check[j] = 0
                    break
                else:
                    check[j] = 0
            if check[i] == -1:
                check[i] = 1
    res = 0
    for i in check:
        if i == 1:
            res += 1
    print(res)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

    ans = 0
    # print(tmp)
    for i, aa in enumerate(tmp):
        hh = h[i]
        if len(aa) == 0:
            ans += 1
            continue
        flg = True
        for j, h2 in enumerate(aa):
            h2 = h[h2]
            if hh > h2:
                continue
            else:
                flg = False
                break
        if flg :
            ans += 1
    print(ans)
if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
input = sys.stdin.readline

n, m = map(int, input().split())
h = [int(item) for item in 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[b] = False
    if h[b] >= h[a]:
        ans[a] = False

print(sum(ans))

Submission status: Accepted

Solution code:
def main():
    import sys
    from collections import deque
    sys.setrecursionlimit(10**6)
    input = sys.stdin.readline
    N, M = [int(x) for x in input().strip().split()]
    H = [int(x) for x in input().strip().split()]
    F = [False] * N
    G = [deque([]) for _ in range(N)]
    for m in range(M):
        a, b = [int(x) for x in input().strip().split()]
        G[a-1].append(b)
        G[b-1].append(a)

    ans = 0
    for n in range(N):
        t = 1
        for nm in G[n]:
            if H[nm-1] >= H[n]:
                t = 0
                break
        ans += t

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
H=[0]+list(map(int,input().split()))
G=[[] for index1 in range(N+1)]
for index1 in range(M):
    a,b=map(int,input().split())
    G[a].append(b)
    G[b].append(a)

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

print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10000000)
from collections import defaultdict

N, M = map(int, input().split())
h = list(map(int, input().split()))
flg = [1]*N
for i in range(M):
    a, b = map(lambda x : int(x)-1, input().split())
    if h[a] <= h[b]:
        flg[a] = 0
    if h[b] <= h[a]:
        flg[b] = 0
print(sum(flg))

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
H = list(map(int, input().split()))
li = [True]*N
for i in range(M):
    a, b = map(int, input().split())
    if H[a-1] >= H[b-1]:
        li[b-1] = False
    if H[b-1] >= H[a-1]:
        li[a-1] = False
ans = 0
for i in range(N):
    if li[i]:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
import numpy as np
N, M = map(int,input().split())
H = list(map(int, input().split())) 
check = [1 for _ in range(N)]
for i in range(M):
    A, B = map(int,input().split())
    A -= 1
    B -= 1
    if H[A] == H[B]:
        check[B] = 0
        check[A] = 0
    elif H[A] > H[B]:
        check[B] = 0
    else:
        check[A] = 0
print(sum(check))

Submission status: Accepted

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

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

print(sum(good))

Submission status: Accepted

Solution code:
import numpy as np 
N, M = map(int,input().split())
h_list = np.array(list(map(int,input().split())))
max_neighbor_hight = np.zeros(N) 
for _ in range(M):
    a,b = map(int,input().split())
    a-=1
    b-=1
    max_neighbor_hight[a] = max(max_neighbor_hight[a],h_list[b])
    max_neighbor_hight[b] = max(max_neighbor_hight[b],h_list[a])
diff = h_list - max_neighbor_hight
ans = np.sum(diff>0)
print(ans)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
h=list(map(int,input().split()))
l=[[] for _ in range(n)]
for _ 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):
  f=1
  for j in l[i]:
    if h[i]<=h[j]:
      f=0
  if f:
    ans+=1
print(ans)

Submission status: Accepted

Solution code:
#dt = {} for i in x: dt[i] = dt.get(i,0)+1
#dt = {k:v for k,v in sorted(x.items(), key=lambda i: i[1])}
ipnl = lambda n: [int(input()) for _ in range(n)]
inp = lambda :int(input())
ip = lambda :[int(w) for w in input().split()]
mp = lambda :map(int,input().split())

n,m = mp()
x = ip()
h = {}
graph = {}
for i in range(1,n+1):
    graph[i] = []
    h[i] = x[i-1]
for i in range(m):
    a,b = mp()
    graph[a].append(b)
    graph[b].append(a)
ctr = 0
for i in graph:
    graph[i] = list(set(graph[i]))
    t = [h[j] for j in graph[i]]
    if t == []:
        ctr += 1
        continue
    if h[i] > max(t):
        ctr += 1
print(ctr)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from collections import deque
n, m = map(int, input().split())
h = [int(x) for x in input().split()]

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

ans = 0
for i in range(n):
  judge = True
  for v in tree[i]:
    if h[i] <= h[v]:
      judge = False
  if judge:
    ans += 1

print(ans)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
H = [int(x) for x in input().split()]
T = [1] * N
for _ in range(M):
  a, b = map(int, input().split())
  if H[a - 1] <= H[b - 1]:
    T[a - 1] = 0
  if H[b - 1] <= H[a - 1]:
    T[b - 1] = 0
print(sum(T))

Submission status: Accepted

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

is_good_Hs = [True for _ in range(N)]

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


count = 0
for i in range(N):
    if is_good_Hs[i]:
        count += 1

print(count)

Submission status: Accepted

Solution code:
N, M = [int(x) for x in input().split()]
H_list = [int(x) for x in input().split()]
bad_list = []
for _ in range(M):
    A, B = [int(x) for x in input().split()]
    if H_list[A - 1] < H_list[B - 1]:
        bad_list.append(A)
    elif H_list[A - 1] > H_list[B - 1]:
        bad_list.append(B)
    else:
        bad_list.append(A)
        bad_list.append(B)

print(N - len(set(bad_list)))

Submission status: Accepted

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

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

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

ans = 0

for i in range(N):
    flag = True
    for j in g[i]:
        if H[i] > H[j]:
            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().rstrip().split(" ")))
ans = [True] * N
ansi = N
for i in range(M):
    K = list(map(int,input().rstrip().split(" ")))
    if (H[K[0] - 1] > H[K[1] - 1]):
        if ans[K[1] - 1] == True:
            ans[K[1] - 1] = False
            ansi -= 1
    elif (H[K[0] - 1] < H[K[1] - 1]):
        if ans[K[0] - 1] == True:
            ans[K[0] - 1] = False
            ansi -= 1
    else:
        if ans[K[1] - 1] == True:
            ans[K[1] - 1] = False
            ansi -= 1
        if ans[K[0] - 1] == True:
            ans[K[0] - 1] = False
            ansi -= 1
print(ansi)

Submission status: Accepted

Solution code:
def LI():return list(map(int,input().split()))

n,m=LI()
h=LI()
edge=[[] for _ in range(n)]
for i in range(m):
    a,b=LI()
    a-=1
    b-=1
    edge[a].append(b)
    edge[b].append(a)
    
ans=0
for i in range(n):
    if all([h[i]-h[v]>0 for v in edge[i]]):
        # print(i)
        ans+=1

print(ans)

Submission status: Accepted

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

for i in range(M):
  A[i],B[i] = map(int,input().split())
  if H[A[i]-1]<H[B[i]-1]:
    ans[A[i]-1]=0
  elif H[A[i]-1]>H[B[i]-1]:
    ans[B[i]-1]=0
  else:
    ans[A[i]-1]=0
    ans[B[i]-1]=0
  
#print(ans)
print(sum(ans))

Submission status: Accepted

Solution code:
import sys
from math import log2,floor,ceil,sqrt
# import bisect
# from collections import deque

Ri = lambda : [int(x) for x in sys.stdin.readline().split()]
ri = lambda : sys.stdin.readline().strip()
 
def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
INF = 10 ** 18
MOD = 10**9+7

n,m = Ri()
ver     = [True]*(n+1)
h = Ri()
h = [0]+h
for i in range(m):
    a,b = Ri()
    if h[a] > h[b]:
        ver[b] = False
    elif h[a] < h[b]:
        ver[a] = False
    else:
        ver[a] = False
        ver[b] = False
cnt=  0
for i in range(1,n+1):
    if ver[i] == True:
        cnt+=1
print(cnt)

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]"):
    mh = [-1] * N
    for a, b in zip(A, B):
        mh[a-1] = max(mh[a-1], H[b-1])
        mh[b-1] = max(mh[b-1], H[a-1])
    ans = 0
    for h, mhh in zip(H, mh):
        if h > mhh:
            ans += 1
    return ans


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools
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))
    print(solve(N, M, H, A, B))

def test():
    import doctest
    doctest.testmod()

if __name__ == '__main__':
    #test()
    main()

Submission status: Accepted

Solution code:
ii = lambda : int(input())
mi = lambda : map(int,input().split())
li = lambda : list(map(int,input().split()))

n,m = mi()
hlis = li()
A = [[]for _ in range(n)]
for i in range(m):
    a,b = mi()
    A[a-1].append(b-1)
    A[b-1].append(a-1)

ans = 0
for i in range(n):
    ima = hlis[i]
    flag = 1
    for k in A[i]:
        if ima <= hlis[k]:
            flag = 0
            break
    if flag:
        ans += 1



print(ans)

Submission status: Accepted

Solution code:
N,M  = [int(_n) for _n in input().split()]
H = [int(_n) for _n in input().split()]
li = [[] for _ in range(N)]
for i in range(M):
    A, B = [int(_n)-1 for _n in input().split()]
    # print(A,B)
    li[A].append(B)
    li[B].append(A)
res = 0
# print(li)
for i in range(N):
    h = H[i]
    flag = True
    for l in li[i]:
        if H[l] >= h:
            # print(i,l)
            flag = False
            break
    if not flag:
        continue
    res+=1
    # print(i)
print(res)

Submission status: Accepted

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

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

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

ans = 0
for i in range(N):
    ma = -1
    for h in A[i]:
        ma = max(ma, H[h])

    if ma < H[i]:
        ans += 1

print(ans)

Submission status: Accepted

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

R = [ [] for _ in range(N+1) ]

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

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

ans = 0

for i in range(N):
  h = H[i]
  r = R[i+1]
  if r == []:
    ans += 1
  else:
    max_h = 0
    for _r in r:
      max_h = max(max_h, H[_r - 1])
    if h  > max_h:
      ans += 1
      
      
print(ans)

Submission status: Accepted

Solution code:
import sys
import heapq
import re
from itertools import permutations
from bisect import bisect_left, bisect_right
from collections import Counter, deque
from math import factorial, sqrt, ceil, gcd
from functools import lru_cache, reduce
INF = 1 << 60
MOD = 1000000007
sys.setrecursionlimit(10 ** 7)

# UnionFind
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

# ダイクストラ
def dijkstra_heap(s, edge, n):
    #始点sから各頂点への最短距離
    d = [10**20] * n
    used = [True] * n #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for a,b in edge[s]:
        heapq.heappush(edgelist,a*(10**6)+b)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge%(10**6)]:
            continue
        v = minedge%(10**6)
        d[v] = minedge//(10**6)
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,(e[0]+d[v])*(10**6)+e[1])
    return d

# 素因数分解
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

# 2数の最小公倍数
def lcm(x, y):
    return (x * y) // gcd(x, y)

# リストの要素の最小公倍数
def lcm_list(numbers):
    return reduce(lcm, numbers, 1)

# リストの要素の最大公約数
def gcd_list(numbers):
    return reduce(gcd, numbers)

# 素数判定
def is_prime(n):
    if n <= 1:
        return False
    p = 2
    while True:
        if p ** 2 > n:
            break
        if n % p == 0:
            return False
        p += 1
    return True


# limit以下の素数を列挙
def eratosthenes(limit):
    A = [i for i in range(2, limit+1)]
    P = []

    while True:
        prime = min(A)
        
        if prime > sqrt(limit):
            break
            
        P.append(prime)
            
        i = 0
        while i < len(A):
            if A[i] % prime == 0:
                A.pop(i)
                continue
            i += 1
            
    for a in A:
        P.append(a)
            
    return P

# 同じものを含む順列
def permutation_with_duplicates(L):

    if L == []:
        return [[]]

    else:
        ret = []

        # set（集合）型で重複を削除、ソート
        S = sorted(set(L))

        for i in S:

            data = L[:]
            data.remove(i)

            for j in permutation_with_duplicates(data):
                ret.append([i] + j)

        return ret


# ここから書き始める
n, m = map(int, input().split())
h = list(map(int, input().split()))
cnt = [1 for i in range(n)]
for i in range(m):
    a, b = map(int, input().split())
    if h[a - 1] <= h[b - 1]:
        cnt[a - 1] = 0
    if h[b - 1] <= h[a - 1]:
        cnt[b - 1] = 0
ans = sum(cnt)
# print("cnt =", cnt)
print(ans)

Submission status: Accepted

Solution code:
N, M = [int(x) for x in input().split(' ')]
H =  [int(x) for x in input().split(' ')]

C = set(range(1,N+1))
for _ in range(M):
  a, b = set(int(x) for x in input().split(' '))
  if H[a-1] >= H[b-1] and b in C:
    C.remove(b)
  if H[b-1] >= H[a-1] and a in C:
    C.remove(a)
    
print(len(C))

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10 ** 6)
#from collections import defaultdict
#d = defaultdict(int)
#import fractions
#import math
#import collections
#from collections import deque
#from bisect import bisect_left
#from bisect import insort_left
#N = int(input())
#A = list(map(int,input().split()))
#S = list(input())
#S.remove("\n")
#N,M = map(int,input().split())
#S,T = map(str,input().split())
#A = [int(input()) for _ in range(N)]
#S = [input() for _ in range(N)]
#A = [list(map(int,input().split())) for _ in range(N)]
#import itertools
#import heapq
#import numpy as np
#INF = float("inf")
N,M = map(int,input().split())
H = list(map(int,input().split()))
AB = [list(map(int,input().split())) for _ in range(M)]
ans = [1]*N
for i in range(M):
    A,B = AB[i]
    if H[A-1] < H[B-1]:
        if ans[A-1] == 1:
            ans[A-1] = 0
    elif H[A-1] > H[B-1]:
        if ans[B-1] == 1:
            ans[B-1] = 0
    else:
        if ans[B-1] == 1:
            ans[B-1] = 0
        if ans[A-1] == 1:
            ans[A-1] = 0
s = 0
for i in ans:
    s += i
print(s)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
H = list(map(int, input().split()))
graph = [[] for _ in range(N)]
for i in range(M):
  a, b = map(int, input().split())
  graph[a-1].append(b-1)
  graph[b-1].append(a-1)
ans = [1] * N
for j in range(N):
  for t in graph[j]:
    if(H[j] <= H[t]):
      ans[j] = 0
print(sum(ans))

Submission status: Accepted

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

ans = 0
for i in range(N):
    m = H[i]
    judge = 0
    for j in K[i]:
        if H[j] >= m:
            judge = 1
            break
    if judge == 0:
        ans += 1
print(ans)

Submission status: Accepted

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

n, m = [int(x) for x in input().split()]
h = [int(x) for x in input().split()]
g = [[] for _ in range(n)]
for _ in range(m):
    a, b = [int(x) for x in input().split()]
    g[a - 1].append(b - 1)
    g[b - 1].append(a - 1)
ans = 0
for i in range(n):
    if len(g[i]) == 0:
        ans += 1
    else:
        flag = 0
        for j in g[i]:
            if h[i] <= h[j]:
                flag = 1
                break
        if not flag:
            ans += 1
print(ans)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
h_lis = list(map(int, input().split()))
ab_lis = [list(map(int, input().split())) for _ in range(m)]
ans=[True]*n

for ab_li in ab_lis:
    #print(ab_li)
    if h_lis[ab_li[0]-1] > h_lis[ab_li[1]-1]:
        ans[ab_li[1]-1] = False
    elif h_lis[ab_li[0]-1] < h_lis[ab_li[1]-1]:
        ans[ab_li[0]-1] = False
    else:
        ans[ab_li[0]-1], ans[ab_li[1]-1] = False, False
#print(ans)
print(sum(ans))

Submission status: Accepted

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

t = [0] * N

for _ in range(M):
    A, B = map(int, input().split())
    t[A-1] = max(t[A-1], H[B-1])
    t[B-1] = max(t[B-1], H[A-1])

result = 0
for i in range(N):
    if H[i] > t[i]:
        result += 1
print(result)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
H=list(map(int,input().split()))
X=[[] for _ in range(n)]
for i in range(m):
    a,b=map(int,input().split())
    X[a-1].append(b-1)
    X[b-1].append(a-1)
ans=0
for i in range(n):
    flag=True
    if len(X[i])==0:
        ans+=1
    else:
        for x in X[i]:
            if H[i]<=H[x]:
                flag=False
        if flag:
            ans+=1
print(ans)

Submission status: Accepted

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

good=[1]*N

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

    a-=1
    b-=1

    if H[a]>H[b]:
        good[b]=0
    elif H[b]>H[a]:
        good[a]=0
    else:
        good[a]=0
        good[b]=0

print(sum(good))

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

g = [0 for i in range(N+1)]

for a, b in AB:
    if g[a] < H[b-1]:
        g[a] = H[b-1]
    if g[b] < H[a-1]:
        g[b] = H[a-1]

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

print(ans)

Submission status: Accepted

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

for _ in range(M):
    A, B = map(int, input().split())
    if H[A - 1] == H[B - 1]:
        H_ans[A - 1] = 0
        H_ans[B - 1] = 0
    elif H[A - 1] > H[B - 1]:
        H_ans[B - 1] = 0
    else:
        H_ans[A - 1] = 0

ans = H_ans.count(1)

print(ans)

Submission status: Accepted

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

flag = [True]*n
for _ in range(m):
    a,b = map(int,input().split())
    if h_li[a-1] < h_li[b-1]:
        flag[a-1]=False
    elif h_li[a-1]>h_li[b-1]:
        flag[b-1]=False
    elif h_li[a-1] == h_li[b-1]:
        flag[a-1]=False
        flag[b-1]=False
print(flag.count(True))

Submission status: Accepted

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

print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

print(sum(is_good))

Submission status: Accepted

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))

from collections import defaultdict
from sys import exit
import math


def main():
    n, m = getList()
    nums = getList()
    tree = [[] for _ in range(n)]
    for i in range(m):
        # start, end, cost
        a, b = getList()
        # 0-indexed
        a -= 1
        b -= 1
        tree[a].append(b)
        tree[b].append(a)
    ans = 0
    for i, t in enumerate(tree):
        cur = nums[i]
        fl = True
        for ne in t:
            if nums[ne] >= cur:
                fl = False

        if fl:
            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()))
# ab = [list(map(int, input().split())) for _ in range(m)]
graph = [[] for _ in range(n+1)]
good = {}
for _ in range(m):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)

for i in range(n):
    h_i = h[i]
    if i in good.keys():
        continue
    if not graph[i+1]:
        good[i] = True
        continue
    for j in graph[i+1]:
        if h_i > h[j-1]:
            good[j-1] = False
        else:
            good[i] = False
            break
    if i not in good.keys():
        good[i] = True

ans = 0
for v in good.values():
    if v:
        ans += 1
print(ans)

Submission status: Accepted

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

H = list(map(int,input().split()))
G = [1]*n
for _ in range(m):
    a,b = map(int,input().split())
    if H[a-1] <= H[b-1]:
        G[a-1] = 0
    if H[a-1] >= H[b-1]:
        G[b-1] = 0

print(sum(G))

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
H = list(map(int, input().split()))
P = [1] * (N+1)
P[0] = 0
for m in range(M):
    A, B = map(int, input().split())
    Ha, Hb = H[A-1], H[B-1]
    if Ha > Hb:
        P[B] = 0
    elif Ha < Hb:
        P[A] = 0
    elif Ha == Hb:
        P[A] = 0
        P[B] = 0

print(sum(P))

Submission status: Accepted

Solution code:
#create date: 2020-05-03 21:05

import sys
stdin = sys.stdin

def ns(): return stdin.readline().rstrip()
def ni(): return int(ns())
def na(): return list(map(int, stdin.readline().split()))

def main():
    n, m = na()
    h = na()
    g = [[] for i in range(n)]
    for i in range(m):
        a, b = na()
        a -= 1
        b -= 1
        g[a].append(b)
        g[b].append(a)
    ans = 0
    for i in range(n):
        if len(g[i]) > 0:
            if max(h[gi] for gi in g[i]) < h[i]:
                ans += 1
        else:
            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()))
flag = [True] * N
for _ in range(M):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    if H[a] >= H[b]:
        flag[b] = False

    if H[b] >= H[a]:
        flag[a] = False

    if H[a] == H[b]:
        flag[b] = False
        flag[a] = False

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

Submission status: Accepted

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

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

cnt = 0
for i in dp:
    if i == 0:
        cnt += 1

print(cnt)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
def main():
    N,M = map(int,input().split())
    H = tuple(map(int,input().split()))
    good = [1]*N
    for _ in range(M):
        a,b = map(int,input().split())
        a-=1;b-=1
        if H[a]<H[b]:
            good[a] = 0
        elif H[a] ==H[b]:
            good[a] = 0
            good[b] = 0
        else:
            good[b] = 0
    print(good.count(1))
if __name__ == "__main__":
    main()

Submission status: Accepted

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

print(sum(H_ok))