Problem:


Score : 300 points

Problem Statement

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

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

How many good observatories are there?

Constraints

2 \leq N \leq 10^5

1 \leq M \leq 10^5

1 \leq H_i \leq 10^9

1 \leq A_i,B_i \leq N

A_i \neq B_i

Multiple roads may connect the same pair of observatories.

All values in input are integers.

Input

Input is given from Standard Input in the following format:

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

Output

Print the number of good observatories.

Sample Input 1

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

Sample Output 1

2

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

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

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

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

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

Sample Input 2

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

Sample Output 2

3



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


Sample output:
2

Submission status: Accepted

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

ans = 0

for i in range(N):
    a = r[i]
    p = 0
    for j in range(len(a)):
        if H[i] > H[a[j]]:
            p += 1
    if p == len(a):
        ans += 1

print(ans)

Submission status: Accepted

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

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

good=[1]*N

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

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

for i, route in enumerate(AB):
    if H[route[0]-1] >= H[route[1]-1]:
        Highest[route[1]-1] = False
    if H[route[1]-1] >= H[route[0]-1]:
        Highest[route[0]-1] = False

print(Highest.count(True))

Submission status: Accepted

Solution code:
# coding: utf-8
import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N, M = lr()
good = [True] * (N+1)  # 1-indexed
H = [0] + lr()  # 1-indexed
for _ in range(M):
    a, b = lr()
    if H[a] >= H[b]:
        good[b] = False
    if H[a] <= H[b]:
        good[a] = False

answer = sum(good) - 1
print(answer)

Submission status: Accepted

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

Submission status: Accepted

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

# print(h)
for i in hi:
    if not i:
        ans -= 1

print(ans)

Submission status: Accepted

Solution code:
def main():
    n,m = map(int,input().split(" "))
    hs = list(map(int,input().split(" ")))
    check = [True]*n
    for i in range(m):
        a,b = map(int,input().split(" "))
        if hs[a-1] < hs[b-1]:
            check[a-1] = False
        elif hs[b-1] < hs[a-1]:
            check[b-1] = False
        elif hs[a-1] == hs[b-1]:
            check[a-1] = False
            check[b-1] = False
    
    print(check.count(True))
main()

Submission status: Accepted

Solution code:
N, M = map(int,input().split())
Hn = list(map(int,input().split()))
res = [True]*N
for m in range(M):
  A, B = map(int,input().split())
  A = A - 1
  B = B - 1
  if Hn[A] > Hn[B]:
    res[B] = False
  elif Hn[A] < Hn[B]:
    res[A] = False
  else:
    res[A] = False
    res[B] = False

ans = 0
for r in res:
  if r is True:
    ans += 1
print(ans)

Submission status: Accepted

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

ans = [None]*N
IH = sorted(enumerate(H),key = lambda x: (-x[1],x[0]))
E = [[] for _ in [0]*N]
for a,b in AB:
    a -=1
    b -= 1
    E[a].append(b)
    E[b].append(a)

for i,h in IH:
    if ans[i] == None:
        h = H[i]
        for j in E[i]:
            ans[j] = False
            if H[j] >= h:
                ans[i] = False
        if ans[i] == None:
            ans[i] = True
print(ans.count(True))

Submission status: Accepted

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

cnt = 0
for i, a in enumerate(c):
    if a:
        a.sort(reverse=True)
        if a[0] < h[i]:
            cnt += 1
    else:
        cnt += 1
print(cnt)

Submission status: Accepted

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

for i in range(1,n+1):
  now=l[i]
  o=0
  for j in now:
    if h[i-1]>h[j-1]:
      o+=1
  if o==len(now):
    ans+=1
print(ans)

Submission status: Accepted

Solution code:
import sys
import math
from decimal import Decimal, ROUND_HALF_UP, ROUND_HALF_EVEN
from collections import deque
def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def S(): return sys.stdin.readline().rstrip()
def LS(): return sys.stdin.readline().split()
def LS2(N): return [sys.stdin.readline().split() for i in range(N)]
def FILL(i,h): return [i for j in range(h)]
def FILL2(i,h,w): return [FILL(i,w) for j in range(h)]
def FILL3(i,h,w,d): return [FILL2(i,w,d) for j in range(h)]
def FILL4(i,h,w,d,d2): return [FILL3(i,w,d,d2) for j in range(h)]
def sisha(num,digit): return Decimal(str(num)).quantize(Decimal(digit),rounding=ROUND_HALF_UP)
#'0.01'や'1E1'などで指定、整数に戻すならintをかます
MOD = 1000000007
INF = float("inf")
sys.setrecursionlimit(10**5+10)
#input = sys.stdin.readline

N,M = MI()
hlist = LI()
link = [[] for i in range(N)]
ans = 0
for i in range(M):
    a,b = MI()
    link[a-1].append(b)
    link[b-1].append(a)
for i in range(N):
    here = hlist[i]
    for next in link[i]:
        if here<=hlist[next-1]:
            break
    else:
        ans += 1
print(ans)

Submission status: Accepted

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


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

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

Submission status: Accepted

Solution code:
def main():
    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())
        if h[a-1] >= h[b-1]:
            good[b-1] = 0
        if h[b-1] >= h[a-1]:
            good[a-1] = 0
    print(sum(good))
    
if __name__ == '__main__':
    main()

Submission status: Accepted

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

    not_good = set()

    for a, b in paths:
        if H[a-1] >= H[b-1]:
            not_good.add(b-1)

        if H[a-1] <= H[b-1]:
            not_good.add(a-1)

    print(N - len(not_good))
    # print(not_good)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# coding: utf-8
import sys

stdin = sys.stdin
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip() # ignore trailing spaces


def main():
    n,m = na()
    hs = na()
    ans = [1 for _ in range(n)]
    for _ in range(m):
        a,b = na()
        a -= 1
        b -= 1
        if hs[a] < hs[b]:
            ans[a] = 0
        elif hs[b] < hs[a]:
            ans[b] = 0
        else:
            ans[a] = 0
            ans[b] = 0
    print(sum(ans))
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
H = list(map(int, input().split()))
bad = []
for _ in range(M):
    i, j = map(int, input().split())
    if H[i-1] <= H[j-1]:
        bad.append(i)
    if H[i-1] >= H[j-1]:
        bad.append(j)
print(N-len(set(bad)))

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):
    for node in g[i]:
        if h[i] <= h[node]:
            break
    else:
        ans += 1
print(ans)

Submission status: Accepted

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

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

ans = 0
for i in range(n):
    h = hs[i]
    maxi = 0
    for x in graph[i]:
        maxi = max(hs[x], maxi)

    if h > maxi:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python
from collections import deque, defaultdict
from itertools import combinations, combinations_with_replacement
import bisect
from math import factorial, sqrt, log, ceil, floor

def main():
    N, M = map(int, input().split())
    Hs = list(map(int, input().split()))

    bads = set()
    height = {idx+1: h for idx, h in enumerate(Hs)}
    for m in range(M):
        A, B = map(int, input().split())

        if height[A] <= height[B]:
            bads.add(A)
        if height[B] <= height[A]:
            bads.add(B)

    print(N - len(bads))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**9)
N, M = list(map(int, input().split()))
H = list(map(int, input().split()))
E = []
for i in range(N):
    E.append([])
for i in range(M):
    a, b = list(map(int, input().split()))
    a -= 1
    b -= 1
    E[a].append(b)
    E[b].append(a)

ans = 0
for i in range(N):
    ok = True
    for to in E[i]:
        if(H[i] <= H[to]):
            ok = False
    if ok:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
H = [int(i) for i in input().split()]
path = []
total = N
good = [1]*N
for i in range(M):
    new = [int(j) for j in input().split()]
    path.append(new)
    if H[new[0]-1] <= H[new[1]-1]:
        if good[new[0]-1] == 1:
            good[new[0]-1] = 0
            total -= 1
    if H[new[1]-1] <= H[new[0]-1]:
        if good[new[1]-1] == 1:
            good[new[1]-1] = 0
            total -= 1
print(total)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
H = list(map(int,input().split()))
B = []
for i in range(M):
  a,b = map(int,input().split())
  if H[a-1] < H[b-1]:
    B += [a]
  elif H[a-1] == H[b-1]:
    B += [a,b]
  elif H[a-1] > H[b-1]:
    B += [b]
C = set(B)

print(N - len(C))

Submission status: Accepted

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

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())
    a -= 1
    b -= 1
    g[a].append(b)
    g[b].append(a)

ans = 0

for i in range(N):
    h = H[i]
    high = True
    for j in g[i]:
        if h <= H[j]:
            high = False
    if high:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
n,m=map(int,input().split())
h=list(map(int,input().split()))
d=defaultdict(int)
for i in range(m):
    a,b=map(int,input().split())
    d[a]=max(d[a],h[b-1])
    d[b]=max(d[b],h[a-1])

ans=0
for i in range(1,n+1):
    h1=d[i]
    if h[i-1]>h1:
        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)]

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

for a, b in ab:
    roads[a-1].append(b)
    roads[b-1].append(a)

ans = 0

for i, r in enumerate(roads):
    r_ = set(r)
    if len(r_) == 0:
        ans += 1
    else:
        flag = True
        h = H[i]
        for x in r_:
            if H[x-1] >= h:
                flag = False
                break
        if flag:
            ans += 1
    
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
############ ---- USER DEFINED INPUT FUNCTIONS ---- ############
def inp():
    return(int(input().rstrip()))
def inlt():
    return(list(map(int,input().rstrip().split())))
def insr():
    s = input().rstrip()
    return(s[:len(s) - 1])
def invr():
    return(map(int,input().rstrip().split()))
################################################################
n,m = invr()
nums = [0] + inlt()
graph = defaultdict(set)

for i in range(m):
    a,b = invr()
    graph[a].add(b)
    graph[b].add(a)

cnt = 0
for i in range(1,n + 1):
    for each in graph[i]:
        if nums[i] <= nums[each]:
            break
    else:
        cnt += 1
print(cnt)

Submission status: Accepted

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

print(sum(ans))

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()

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

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

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

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# nが頂点数、mが辺の本数
n, m = map(int, input().split())

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

edges = [list(map(int, input().split())) for _ in range(m)]
edges = [[b[0]-1, b[1]-1] for b in edges]  # 1-idx -> 0-idx

neighbor = [[] for i in range(n)]
# print(neighbor)
for i in range(m):
    a = edges[i][0]
    b = edges[i][1]
    neighbor[a] += [b]
    neighbor[b] += [a]
# print(neighbor)


ans = 0
for vertex in range(n):
    result = True
    for nei in neighbor[vertex]:
        if heights[nei] >= heights[vertex]:
            result = False
        
    if result:
        ans += 1
            
print(ans)

Submission status: Accepted

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

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

t=[1 for i in range(n)]

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

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
h=[0]+list(map(int,input().split()))
good=[1]*(n+1)
good[0]=0
for i in range(m):
  a,b=map(int,input().split())
  if h[a]<h[b]:
    good[a]=0
  elif h[a]>h[b]:
    good[b]=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 = [tuple(map(int, input().split())) for i in range(M)]
G = [0]*N

for a, b in AB:
    a -= 1
    b -= 1
    if G[a] < H[b]:
        G[a] = H[b]
    if G[b] < H[a]:
        G[b] = H[a]
ans = 0
for i in range(N):
    if H[i] > G[i]:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict

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

a = []
b = []
for j in range(m):
    data = list(map(int, input().split()))
    a.append(data[0])
    b.append(data[1])

conn = defaultdict(list)

for j in range(m):
    conn[a[j]-1].append(b[j]-1)
    conn[b[j]-1].append(a[j]-1)

good = 0

for a in range(n):
    if len(conn[a]) == 0:
        good += 1
    else:
        for b in conn[a]:
            if h[b] >= h[a]:
                break
        else:
            good += 1

print(good)

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
H_li = list(map(int,input().split()))
ans = 0
route = [[] for i in range(N)]
for i in range(M):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    route[a].append(b)
    route[b].append(a)
for i in range(N):
    i_h = H_li[i]
    ikeru = route[i]
    if ikeru == []:
        ans += 1
        continue
    ikeru_h = [H_li[j] for j in ikeru]
    if max(ikeru_h) < i_h:
        ans += 1
print(ans)

Submission status: Accepted

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


ans = 0
for i in range(N):
    now = H[i]
    if all([now > H[nv] for nv in to[i]]):
        ans += 1
print(ans)

Submission status: Accepted

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

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

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

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

ans = 0
for i in range(n):
   if len(x[i]) == 0:
      ans += 1

   elif h[i] > max(x[i]):
      ans += 1

print(ans)

Submission status: Accepted

Solution code:


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

Submission status: Accepted

Solution code:

MOD = 10 ** 9 + 7
RLIMIT = 1000
DEBUG = 1

def main():
    for _ in inputt(1):
        n, m = inputi()
        H = [0] + inputl()
        P = [[] for _ in range(n + 1)]
        T = [0] * (n + 1)
        for a, b in inputl(m):
            if H[a] <= H[b]:
                T[a] = 1
            if H[b] <= H[a]:
                T[b] = 1
        debug(T)
        print(n - sum(T))
            




# region M


# region import

from math import *
from heapq import *
from itertools import *
from functools import reduce, lru_cache, partial
from collections import Counter, defaultdict
import re, copy, operator, cmath
import sys, io, os, builtins
sys.setrecursionlimit(RLIMIT)

# endregion

# region fastio

BUFSIZE = 8192
class FastIO(io.IOBase):
    newlines = 0
    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = io.BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None
    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()
    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()
    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)
class IOWrapper(io.IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")
def print(*args, **kwargs):
    if args:
        sys.stdout.write(str(args[0]))
        split = kwargs.pop("split", " ")
        for arg in args[1:]:
            sys.stdout.write(split)
            sys.stdout.write(str(arg))
    sys.stdout.write(kwargs.pop("end", "\n"))
def debug(*args, **kwargs):
    if DEBUG and not __debug__:
        print("debug", *args, **kwargs)
        sys.stdout.flush()
sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip()
inputt = lambda t = 0: range(t) if t else range(int(input()))
inputs = lambda: input().split()
inputi = lambda k = int: map(k, inputs())
inputl = lambda t = 0, k = lambda: list(inputi()): [k() for _ in range(t)] if t else list(k())

# endregion

# region bisect

def len(a):
    if isinstance(a, range):
        return -((a.start - a.stop) // a.step)
    return builtins.len(a)
def bisect_left(a, x, key = None, lo = 0, hi = None):
    if lo < 0: lo = 0
    if hi == None: hi = len(a)
    if key == None: key = do_nothing
    while lo < hi:
        mid = (lo + hi) // 2
        if key(a[mid]) < x: lo = mid + 1
        else: hi = mid
    return lo
def bisect_right(a, x, key = None, lo = 0, hi = None):
    if lo < 0: lo = 0
    if hi == None: hi = len(a)
    if key == None: key = do_nothing
    while lo < hi:
        mid = (lo + hi) // 2
        if x < key(a[mid]): hi = mid
        else: lo = mid + 1
    return lo
def insort_left(a, x, key = None, lo = 0, hi = None):
    lo = bisect_left(a, x, key, lo, hi)
    a.insert(lo, x)
def insort_right(a, x, key = None, lo = 0, hi = None):
    lo = bisect_right(a, x, key, lo, hi)
    a.insert(lo, x)
do_nothing = lambda x: x
bisect = bisect_right
insort = insort_right
def index(a, x, default = None, key = None, lo = 0, hi = None):
    if lo < 0: lo = 0
    if hi == None: hi = len(a)
    if key == None: key = do_nothing
    i = bisect_left(a, x, key, lo, hi)
    if lo <= i < hi and key(a[i]) == x: return a[i]
    if default != None: return default
    raise ValueError
def find_lt(a, x, default = None, key = None, lo = 0, hi = None):
    if lo < 0: lo = 0
    if hi == None: hi = len(a)
    i = bisect_left(a, x, key, lo, hi)
    if lo < i <= hi: return a[i - 1]
    if default != None: return default
    raise ValueError
def find_le(a, x, default = None, key = None, lo = 0, hi = None):
    if lo < 0: lo = 0
    if hi == None: hi = len(a)
    i = bisect_right(a, x, key, lo, hi)
    if lo < i <= hi: return a[i - 1]
    if default != None: return default
    raise ValueError
def find_gt(a, x, default = None, key = None, lo = 0, hi = None):
    if lo < 0: lo = 0
    if hi == None: hi = len(a)
    i = bisect_right(a, x, key, lo, hi)
    if lo <= i < hi: return a[i]
    if default != None: return default
    raise ValueError
def find_ge(a, x, default = None, key = None, lo = 0, hi = None):
    if lo < 0: lo = 0
    if hi == None: hi = len(a)
    i = bisect_left(a, x, key, lo, hi)
    if lo <= i < hi: return a[i]
    if default != None: return default
    raise ValueError

# endregion

# region csgraph
# TODO

class Tree:
    def __init__(n):
        self._n = n
        self._conn = [[] for _ in range(n)]
        self._list = [0] * n
    def connect(a, b):
        pass

# endregion

# region ntheory

class Sieve:
    def __init__(self):
        self._n = 6
        self._list = [2, 3, 5, 7, 11, 13]
    def extend(self, n):
        if n <= self._list[-1]: return
        maxbase = int(n ** 0.5) + 1
        self.extend(maxbase)
        begin = self._list[-1] + 1
        newsieve = [i for i in range(begin, n + 1)]
        for p in self.primerange(2, maxbase):
            for i in range(-begin % p, len(newsieve), p):
                newsieve[i] = 0
        self._list.extend([x for x in newsieve if x])
    def extend_to_no(self, i):
        while len(self._list) < i: 
            self.extend(int(self._list[-1] * 1.5))
    def primerange(self, a, b):
        a = max(2, a)
        if a >= b: return
        self.extend(b)
        i = self.search(a)[1]
        maxi = len(self._list) + 1
        while i < maxi:
            p = self._list[i - 1]
            if p < b:
                yield p
                i += 1
            else: return
    def search(self, n):
        if n < 2: raise ValueError
        if n > self._list[-1]: self.extend(n)
        b = bisect(self._list, n)
        if self._list[b - 1] == n: return b, b
        else: return b, b + 1
    def __contains__(self, n):
        if n < 2: raise ValueError
        if not n % 2: return n == 2
        a, b = self.search(n)
        return a == b
    def __getitem__(self, n):
        if isinstance(n, slice):
            self.extend_to_no(n.stop + 1)
            return self._list[n.start: n.stop: n.step]
        else:
            self.extend_to_no(n + 1)
            return self._list[n]
sieve = Sieve()
def isprime(n):
    if n <= sieve._list[-1]:
        return n in sieve
    for i in sieve:
        if not n % i: return False
        if n < i * i: return True
prime = sieve.__getitem__
primerange = lambda a, b = 0: sieve.primerange(a, b) if b else sieve.primerange(2, a)
def factorint(n):
    factors = []
    for i in sieve:
        if n < i * i: break
        while not n % i:
            factors.append(i)
            n //= i
    if n != 1: factors.append(n)
    return factors
factordict = lambda n: Counter(factorint(n))

# endregion

# region main

if __name__ == "__main__":
    main()

# endregion


# endregion

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
INF = 10**10
MOD = 10**9 + 7

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

print (sum(ok))

Submission status: Accepted

Solution code:
def resolve():
    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]:
            if ans[a] == 1:
                ans[a] = 1
            ans[b] = 0
        elif h[a] == h[b]:
            ans[a] = 0
            ans[b] = 0
        else:
            if ans[b] == 1:
                ans[b] = 1
            ans[a] = 0
    print(sum(ans))

resolve()

Submission status: Accepted

Solution code:
import sys


N, M = map(int, input().split())
H = list(map(int, input().split()))
edge = [set() for _ in range(N)]
for s in sys.stdin.readlines():
    a, b = map(int, s.split())
    a -= 1; b -= 1
    edge[a].add(b)
    edge[b].add(a)

done = [0] * N
for i in range(N):
    if done[i] == 0:
        h = H[i]
        for e in edge[i]:
            h1 = H[e]
            if h1 < h:
                done[e] = -1
            else:
                done[i] = -1
                break
        else:
            done[i] = 1

print(done.count(1))

Submission status: Accepted

Solution code:
from math import sqrt,ceil,floor
def mi():return map(int,input().split())
def li():return list(mi())
def ii():return int(input())

n,k=mi()

m=[1]*(n+1)
a=li()
for i in range(k):
    x,y=mi()
    if(a[x-1]==a[y-1]):
        m[x]=0
        m[y]=0
    if(a[x-1]>a[y-1]):
        m[y]=0
    else:
        m[x]=0


m=m[1:]
print(m.count(1))

Submission status: Accepted

Solution code:
from collections import defaultdict
import numpy as np

N, M = map(int, input().split())
H = np.array(list(map(int, input().split())))
AB = []
dic = defaultdict(list)
for _ in range(M):
    a, b = map(int, input().split())
    a, b = a - 1, b - 1  # 0-indexed
    AB.append((a, b))
    dic[a].append(b)
    dic[b].append(a)
# print('dic', dic)

ans = 0
for i in range(N):
    if dic.get(i, None) is None:
        ans += 1
        continue
    if H[i] > (H[[dic[i]]]).max():
        ans += 1
print(ans)

Submission status: Accepted

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

V = []
for node in range(N):
    V.append(set())
for _ in range(M):
    a,b = map(int, input().split())
    V[a-1].add(b-1)
    V[b-1].add(a-1)

ans = 0
for node in range(N):
    Hi = H[node]
    flg = 0
    for next_node in V[node]:
        if Hi>H[next_node]:
            continue
        flg = 1
    if flg==0:
        ans = ans + 1
    elif len(V[node])==0:
        ans = ans + 1
print(ans)

Submission status: Accepted

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