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())
hs = list(map(int, input().split()))
edges = [[] for i in range(n)]
for i in range(m):
    a,b  = map(int, input().split())
    a -= 1
    b -= 1
    edges[a].append(b)
    edges[b].append(a)

cnt = 0
for v in range(n):
    flg = True
    for u in set(edges[v]): #次の展望台
        if hs[u] >= hs[v]:
            flg = False
    if flg:
        cnt += 1

print(cnt)

Submission status: Accepted

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

good=[True]*N

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

ans=0
for g in good:
    if g:
        ans+=1
print(ans)

Submission status: Accepted

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

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_neigh_hight = np.zeros(N) # 隣接する展望台で最も高いもの

for _ in range(M):
    a,b = map(int,input().split())
    a-=1
    b-=1
    max_neigh_hight[a] = max(max_neigh_hight[a],h_list[b])
    max_neigh_hight[b] = max(max_neigh_hight[b],h_list[a])

diff = h_list - max_neigh_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()))

F = [True] * N
for i in range(M):
    Ai, Bi = map(lambda s: int(s) - 1, input().split())
    if H[Ai] > H[Bi]:
        F[Bi] = False
    elif H[Ai] < H[Bi]:
        F[Ai] = False
    else:
        F[Ai] = F[Bi] = False

print(F.count(True))

Submission status: Accepted

Solution code:
import sys
import math
import fractions
from collections import deque
from collections import defaultdict
sys.setrecursionlimit(10**7)

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

cnt = 0
for g in good:
    if g:
        cnt += 1

print(cnt)

Submission status: Accepted

Solution code:
#!/usr/bin/env python
import os
import sys
from io import BytesIO, IOBase


def main():
    n,m=map(int,input().split())
    a=[int(x) for x in input().split()]
    ans=[True]*n
    for _ in range(m):
        u,v=[int(x)-1 for x in input().split()]
        if a[u]<=a[v]:
            ans[u]=False
        if a[u]>=a[v]:
            ans[v]=False
    print(sum(ans))


# region fastio

BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = 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(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")


sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")

# endregion

if __name__ == "__main__":
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N, M = [int(i) for i in input().split()]
H = [int(i) for i in input().split()]
graph = {i:set() for i in range(1,N+1)}
for _ in range(M):
    a,b = [int(i) for i in input().split()]
    graph[a].add(b)
    graph[b].add(a)

c = 0
good = [-1]*N
for i in range(1,N+1):
    if good[i-1] == -1:
        h = H[i-1]
        for j in graph[i]:
            if h > H[j-1]:
                good[j-1] = 0
            else:
                good[i-1] = 0
                break
        else:
            good[i-1] = 1
            c += 1
# print(good)
print(c)

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())
    if H[A-1] <= H[B-1]:
        ans[A-1] = 0
    if H[B-1] <= H[A-1]:
        ans[B-1] = 0
print(sum(ans))

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
h = [int(x) for x in input().split()]
res_list = [1] * n
for i in range(m):
    ai, bi = map(int, input().split())
    if h[ai-1] < h[bi-1]:
        res_list[ai-1] = 0
    elif h[ai-1] == h[bi-1]:
        res_list[ai-1] = 0
        res_list[bi-1] = 0
    else:
        res_list[bi-1] = 0
print(sum(res_list))

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[b-1]=0
    if H[b-1]>=H[a-1]:
        L[a-1]=0

print(sum(L))

Submission status: Accepted

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

Submission status: Accepted

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

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

counter = 0
for i in range(N):
    for next_node in AB[i]:
        if Hs[i] <= Hs[next_node]:
            break
    else:
        counter += 1

print(counter)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from collections import defaultdict

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

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

ans = 0
for i in range(n):
    for j in road[i]:
        if h[i] <= h[j]:
            break
    else:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
H = list(map(int, input().split()))
ans = [1]*N
for _ in range(M):
    a, b = map(int, input().split())
    if H[a-1] > H[b-1]:
        ans[b-1] = 0
    elif H[a-1] < H[b-1]:
        ans[a-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()))
check = [0]*N
for i in range(M):
    A, B = map(int, input().split())
    if H[A-1] > H[B-1]:
        check[B-1] = -1
    elif H[B-1] > H[A-1]:
        check[A-1] = -1
    else:
        check[A-1],check[B-1] = -1,-1
print(check.count(0))

Submission status: Accepted

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

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

print(sum(good))

Submission status: Accepted

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

N, M = map(int, input().split())
H = list(map(int, input().split()))
ab = [list(map(int, input().split())) for _ in range(M)]

ok = [1 for _ in range(N)]

for a, b in ab:
    if H[a - 1] < H[b - 1]:
        ok[a - 1] = 0
    if H[b - 1] < H[a - 1]:
        ok[b - 1] = 0
    if H[a - 1] == H[b - 1]:
        ok[a - 1] = 0
        ok[b - 1] = 0

ans = 0

for o in ok:
    if o == 1:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
H = list(map(int, input().split()))
G = [[] for _ in range(N)]
for _ 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 v in G[i]:
        if H[i] <= H[v]:
            break
    else:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6) #再帰関数の上限
import math
from copy import copy, deepcopy
from operator import itemgetter

from bisect import bisect_left, bisect, bisect_right#2分探索
#bisect_left(l,x), bisect(l,x)#aはソート済みである必要あり。aの中からx未満の要素数を返す。rightだと以下
from collections import deque 
#deque(l), pop(), append(x), popleft(), appendleft(x)
##listでqueの代用をするとO(N)の計算量がかかってしまうので注意
#dequeを使うときはpython3を使う、pypyはダメ
from collections import Counter#文字列を個数カウント辞書に、
#S=Counter(l),S.most_common(x),S.keys(),S.values(),S.items()
from itertools import accumulate#累積和
#list(accumulate(l))
from heapq import heapify,heappop,heappush
#heapify(q),heappush(q,a),heappop(q) #q=heapify(q)としないこと、返り値はNone

def input(): return sys.stdin.readline()[:-1]
def printl(li): print(*li, sep="\n")
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds

#mod = 10**9+7
#w.sort(key=itemgetter(1),reversed=True)  #二個目の要素で降順並び替え

#N = int(input())
N, M = map(int, input().split())
#L = [int(input()) for i in range(N)]
H = list(map(int, input().split()))
#S = [list(map(int, input().split())) for i in range(N)]
l=[1]*N
for i in range(M):
    a,b=map(int, input().split())
    a-=1
    b-=1
    ha, hb=H[a],H[b]
    if ha==hb:
        l[a]=l[b]=0
    elif ha>hb:
        l[b]=0
    else:
        l[a]=0
print(sum(l))

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


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

    ROAD = [[] for j in range(N + 1)]
    for a, b in AB:
        ROAD[a].append(b)
        ROAD[b].append(a)

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

    print(ans)



if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from sys import stdin, setrecursionlimit

setrecursionlimit(10 ** 9)


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

N, M = map(int, input().split())
H = list(map(int, input().split()))
g = [list() 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):
    good = True
    for j in g[i]:
        if H[i] <= H[j]:
            good = False

    ans += good

print(ans)

Submission status: Accepted

Solution code:
import math
import pprint
import fractions
import collections
import itertools
N,M=map(int,input().split())
H=list(map(int,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)
l=[1]*N
for i in range(N):
    flag=1
    for j in tree[i]:
        if H[i]<=H[j]:
            flag=0
    l[i]=flag
print(sum(l))

Submission status: Accepted

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

int1 = lambda x: int(x) - 1
lst = [1] * N
for _ in range(M):
    a, b = map(int1, input().split())
    if H[a] >= H[b]:
        lst[b] = 0
    if H[b] >= H[a]:
        lst[a] = 0
print(sum(lst))

Submission status: Accepted

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

Submission status: Accepted

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

def main():
    N, M = map(int, input().split())
    H = list(map(int, input().split()))
    adj = [[] for _ in range(N)]
    for i in range(M):
        A, B  = map(int, input().split())
        adj[A-1].append(B-1)
        adj[B-1].append(A-1)
    
    ans = 0
    for i in range(N):
        flag = True
        for u in adj[i]:
            if H[i] <= H[u]:
                flag = False
        if flag:
            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)]

isgood = [True] * N
for i, (Ai, Bi) in enumerate(AB):
    if H[Ai - 1] == H[Bi - 1]:
        isgood[Ai - 1] = False
        isgood[Bi - 1] = False
    elif H[Ai - 1] < H[Bi - 1]:
        isgood[Ai - 1] = False
    else:
        isgood[Bi - 1] = False

ans = sum([int(flag) for flag in isgood])

print(ans)

Submission status: Accepted

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

lst = []
for i in range(M):
    A_,B_ = map(int,input().split())
    if H[A_ -1] >= H[B_ -1]:
        lst.append(B_)
    if H[A_-1] <= H[B_- 1]:
        lst.append(A_)
print(N - len(set(lst)))

Submission status: Accepted

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

Submission status: Accepted

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

a = list(map(int,input().split()))
edge = [0]*N
for _ in range(M):
    b,c = map(int,input().split())
    b -= 1;c -= 1
    if a[b] > a[c]:
        edge[c] += 1
    elif a[b] < a[c]:
        edge[b] += 1
    else:
        edge[b] += 1
        edge[c] += 1

print(edge.count(0))

Submission status: Accepted

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

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
    else:
        good[A - 1] = 0
print(good.count(1))

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
import sys
readline = sys.stdin.readline
read = sys.stdin.read

#n = int(input())
#a = [int(i) for i in read().split()]

n,m = [int(i) for i in readline().split()]
h = [int(i) for i in readline().split()]

res = [1]*n
for _ in range(m):
    a,b = [int(i)-1 for i in readline().split()]
    if h[a] >= h[b]:
        res[b] = 0
    if h[a] <= h[b]:
        res[a] = 0
    
    
print(res.count(1))

Submission status: Accepted

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

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


print(cnt)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
Hs = list(map(int, input().split()))
bad = set()
for _ in range(M):
    a, b = map(int, input().split())
    if Hs[a - 1] <= Hs[b - 1]:
        bad.add(a)
    if Hs[b - 1] <= Hs[a - 1]:
        bad.add(b)
print(N - len(bad))

Submission status: Accepted

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

    if h[a]<=h[b]: s.append(a)
    if h[a]>=h[b]: s.append(b)

print(n-len(set(s)))

Submission status: Accepted

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

class Node:
    def __init__(self,index,height):
        self.index = index
        self.height = height
        self.refs = []
        self.isGood = True

    def append(self,target):
        if target.height >= self.height:
            self.isGood = False
        if self.height >= target.height:
            target.isGood = False
        self.refs.append(target)
        target.refs.append(self)

def solve(N: int, M: int, H: "List[int]", A: "List[int]", B: "List[int]"):
    nodes = [Node(i,H[i]) for i in range(N)]
    for i in range(M):
        nodes[A[i]-1].append(nodes[B[i]-1])
    def isGood(node):
        return node.isGood

    print(len(list(filter(isGood,nodes))))
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    H = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    A = [int()] * (M)  # type: "List[int]"
    B = [int()] * (M)  # type: "List[int]"
    for i in range(M):
        A[i] = int(next(tokens))
        B[i] = int(next(tokens))
    solve(N, M, H, A, B)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N,M = [int(hoge) for hoge in input().split()]
H = [int(hoge) for hoge in input().split()]
Survive = [True] * N
for t in range(M):
    A,B = [int(hoge)-1 for hoge in input().split()]
    if H[A] >= H[B] :
        Survive[B] = False
    if H[B] >= H[A]:
        Survive[A] = False
print(sum(Survive))

Submission status: Accepted

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

yoi = [1 for i in range(n)]
for i in range(m):
    ai, bi = a[i], b[i]
    if h[ai] > h[bi]:
        yoi[bi] = 0
    elif h[bi] > h[ai]:
        yoi[ai] = 0
    else:
        yoi[ai], yoi[bi] = 0, 0

print(sum(yoi))

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
*H, = map(int, input().split())
good = [True] * N
for _ in range(M):
    a, b = map(int, input().split())
    a, b = a-1, b-1
    good[a] &= H[a] > H[b]
    good[b] &= H[b] > H[a]
print(sum(good))

Submission status: Accepted

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

for i in range(m):
    a,b=map(int,input().split())
    a-=1
    b-=1
    mi[a].append(h[b])
    mi[b].append(h[a])
ans=0
for i in range(n):
    if len(mi[i])==0:
        ans+=1
    else:
        if h[i]>max(mi[i]):ans+=1

print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
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()))

n,m=MAP()
h=LIST()
g=[[] for i in range(n)]
for i in range(m):
    a,b=MAP()
    g[a-1].append(b-1)
    g[b-1].append(a-1)

ans=0

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
import os
import itertools
import string
import heapq
import _collections
from collections import Counter
from collections import defaultdict
from functools import lru_cache
import bisect
import re
import queue
from decimal import *


class Scanner():
    @staticmethod
    def int():
        return int(sys.stdin.readline().rstrip())

    @staticmethod
    def string():
        return sys.stdin.readline().rstrip()

    @staticmethod
    def map_int():
        return [int(x) for x in Scanner.string().split()]

    @staticmethod
    def string_list(n):
        return [Scanner.string() for i in range(n)]

    @staticmethod
    def int_list_list(n):
        return [Scanner.map_int() for i in range(n)]

    @staticmethod
    def int_cols_list(n):
        return [Scanner.int() for i in range(n)]


class Math():
    @staticmethod
    def gcd(a, b):
        if b == 0:
            return a
        return Math.gcd(b, a % b)

    @staticmethod
    def lcm(a, b):
        return (a * b) // Math.gcd(a, b)

    @staticmethod
    def divisor(n):
        res = []
        i = 1
        for i in range(1, int(n ** 0.5) + 1):
            if n % i == 0:
                res.append(i)
                if i != n // i:
                    res.append(n // i)
        return res

    @staticmethod
    def round_up(a, b):
        return -(-a // b)

    @staticmethod
    def is_prime(n):
        if n < 2:
            return False
        if n == 2:
            return True
        if n % 2 == 0:
            return False
        d = int(n ** 0.5) + 1
        for i in range(3, d + 1, 2):
            if n % i == 0:
                return False
        return True


def pop_count(x):
    x = x - ((x >> 1) & 0x5555555555555555)
    x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)
    x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f
    x = x + (x >> 8)
    x = x + (x >> 16)
    x = x + (x >> 32)
    return x & 0x0000007f


MOD = int(1e09) + 7
INF = int(1e15)


def solve():
    N, M = Scanner.map_int()
    H = Scanner.map_int()
    G = [[] for _ in range(N)]
    for _ in range(M):
        a, b = Scanner.map_int()
        a -= 1
        b -= 1
        G[a].append(b)
        G[b].append(a)

    ans = 0
    for i in range(N):
        if len(G[i]) == 0:
            ans += 1
            continue
        for g in G[i]:
            if H[g] >= H[i]:
                break
        else:
            ans += 1
    print(ans)


def main():
    # sys.stdin = open("sample.txt")
    solve()


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
H=[int(i) for i in input().split()]
res=[1 for i in range(n)]

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

print(sum(res))

Submission status: Accepted

Solution code:
N,M=map(int, input().split())
*H,=map(int, input().split())
G=[[] for _ in range(N)]
for _ in range(M):
    a,b=map(int, input().split())
    a,b=a-1,b-1
    G[a].append(b)
    G[b].append(a)
ans=0
for i in range(N):
    if G[i]:
        if H[i]>max(H[g] for g in G[i]): ans+=1
    else: ans+=1
print(ans)

Submission status: Accepted

Solution code:
import sys,math,copy,queue,itertools,bisect,collections
from heapq import *
sys.setrecursionlimit(10**7)
LI = lambda : [int(x) for x in sys.stdin.readline().split()]
NI = lambda : int(sys.stdin.readline())
INF = 10**18
MOD = 10**9 + 7
DD = ((1,0),(-1,0),(0,1),(0,-1))

N,M = LI()
H = [0] + LI()
root = [[] for _ in range(N+1)]
for _ in range(M):
    a,b = LI()
    root[a].append(b)
    root[b].append(a)

ans = 0
for i in range(1,N+1):
    x = H[i]
    for r in root[i]:
        if H[r] >= x: break
    else:
        ans += 1
print(ans)

Submission status: Accepted

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

import sys

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')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

N, M = MAP()
nodes = [[0] for i in range(N)]
H = LIST()
for i in range(M):
    a, b = MAP()
    a -= 1; b -= 1
    nodes[a].append(H[b])
    nodes[b].append(H[a])

ans = 0
for i in range(N):
    if H[i] > max(nodes[i]):
        ans += 1
print(ans)

Submission status: Accepted

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

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n,m = LI()
h = LI()
ab = [LI() 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 in range(n):
    if m[i] < h[i]:
        ans += 1   
print(ans)

Submission status: Accepted

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

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

memo = [True]*N

for _ in range(M):
    a,b = map(int,input().split())
    a,b = a-1,b-1
    if H[a] == H[b]:
        memo[a] = False
        memo[b] = False
    else:
        _,k = min((H[a],a),(H[b],b))
        memo[k] = False

print(sum(memo))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys

stdin = sys.stdin
inf = 1 << 60
mod = 1000000007

ni      = lambda: int(ns())
nin     = lambda y: [ni() for _ in range(y)]
na      = lambda: list(map(int, stdin.readline().split()))
nan     = lambda y: [na() for _ in range(y)]
nf      = lambda: float(ns())
nfn     = lambda y: [nf() for _ in range(y)]
nfa     = lambda: list(map(float, stdin.readline().split()))
nfan    = lambda y: [nfa() for _ in range(y)]
ns      = lambda: stdin.readline().rstrip()
nsn     = lambda y: [ns() for _ in range(y)]
ncl     = lambda y: [list(ns()) for _ in range(y)]
nas     = lambda: stdin.readline().split()

n, m = na()
h = na()
ab = nan(m)

g = [[] for _ in range(n)]
for i in range(m):
    a, b = ab[i]
    a -= 1
    b -= 1
    g[a].append(b)
    g[b].append(a)

def ok(v):
    hv = h[v]
    for nv in g[v]:
        if hv <= h[nv]:
            return False
    return True

ans = 0
for i in range(n):
    if ok(i):
        ans += 1

print(ans)

Submission status: Accepted

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

ans=0
for i in range(n):
    if G[i]:
        if max(G[i])<H[i]:
            ans+=1
    else:
        ans+=1
print(ans)

Submission status: Accepted

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

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

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

ans = 0
for i in range(1,n+1):
    hi = h[i-1]
    gr = graph[i]
    tmp = 1
    for j in gr:
        hj = h[j-1]
        if(hj >= hi):
            tmp=0
    ans += tmp

print(ans)