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

    if(h[a-1] > h[b-1]):
        r[b-1] = 1
    elif(h[a-1] < h[b-1]):
        r[a-1] = 1
    elif(h[a-1] == h[b-1]):
        r[a-1] = 1
        r[b-1] = 1

count = 0
for i in range(n):
    if(r[i] == 0):
        count += 1

print(count)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
h=list(map(int,input().split()))
p=[i for i in range(1,n+1)]
q=[]
for i in range(m):
  a=list(map(int,input().split()))
  if h[a[0]-1]<=h[a[1]-1]:
    q.append(a[0])
  if h[a[0]-1]>=h[a[1]-1]:
    q.append(a[1])
p=set(p)
q=set(q)
print(len(p-q))

Submission status: Accepted

Solution code:
class Observatory:
    def __init__(self, height):
        self.height = height
        self.connected_observatories = []

    def add_connected_observatories(self, observatory):
        self.connected_observatories.append(observatory)

    def compare_height_with_connected_observatories(self):
        for i in self.connected_observatories:
            if self.height <= i.height:
                return False

        return True

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

observatories = []

for i in list(map(int, input().split())):
    observatories.append(Observatory(i))

for i in range(M):
    A, B = map(int, input().split())

    observatories[A - 1].add_connected_observatories(observatories[B - 1])
    observatories[B - 1].add_connected_observatories(observatories[A - 1])

count = 0

for i in observatories:
    if i.compare_height_with_connected_observatories():
        count += 1

print(count)

Submission status: Accepted

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

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

ans = 0
for i in range(N):
    g = groups[i]
    g.sort(reverse=True)
    if len(g) == 1:
        ans += 1
        continue
    if g[0] != g[1] and g[0] == H[i]:
        ans += 1
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n,m = (int(num) for num in input().split())
h = [int(num) for num in input().split()]
l = [1] * n
a = 0
b = 0
for _ in range(m):
    a,b = (int(num)-1 for num in input().split())
    if h[a] <= h[b]:
        l[a] = 0
    if h[a] >= h[b]:
        l[b] = 0
#print(l)        
print(sum(l))

Submission status: Accepted

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

def check(origin,target):
    return origin > target

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

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

    tmp = check(h_L[a],h_L[b])
    dic[a].append(tmp)
    tmp = check(h_L[b],h_L[a])
    dic[b].append(tmp)

#print(dic)

ans = 0
for k,v in dic.items():
    try:
        if v[0] and len(set(v)) ==1:
            ans += 1
    except:
        ans += 1
print(ans)

Submission status: Accepted

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

res = 0
for cur in range(1, N+1):
    isObser = True
    for u in e[cur]:
        if H[u-1] >= H[cur-1]:
            isObser = False
    res += int(isObser)
print(res)

Submission status: Accepted

Solution code:
from collections import Counter
import sys
sys.setrecursionlimit(200000)


def read():
    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())
        G[a-1].append(b-1)
        G[b-1].append(a-1)
    return N, M, H, G


def solve(N, M, H, G):
    ans = []
    for i in range(N):
        best = True
        for j in G[i]:
            if H[j] >= H[i]:
                best = False
        if best:
            ans.append(i+1)
    return len(ans)


if __name__ == '__main__':
    inputs = read()
    outputs = solve(*inputs)
    if outputs is not None:
        print("{}".format(outputs))

Submission status: Accepted

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

Submission status: Accepted

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

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

for i in range(m):
    s, g = input().split()

    s = int(s) - 1
    g = int(g) - 1

    vs[s].append(g)
    vs[g].append(s)

goods = []

for i, v in enumerate(vs):
    if len(v) == 0:
        goods.append(i + 1)

    if all(hs[i] > hs[d] for d in v):
        goods.append(i + 1)

print(len(set(goods)))

Submission status: Accepted

Solution code:
import collections
import math
import operator as op
from functools import reduce
from collections import Counter
import numpy as np
import math
import bisect
import heapq


def get_inputs(cast_func=None):
    if cast_func is None:
        return input().split()
    else:
        return list(map(cast_func, input().split()))


def get_input(cast_func=None):
    if cast_func is None:
        return input()
    else:
        return cast_func(input())


def main():
    N, M = get_inputs(int)
    H = get_inputs(int)

    adj_list = [[] for _ in range(N+1)]
    for i in range(M):
        A, B = get_inputs(int)
        adj_list[A].append(B)
        adj_list[B].append(A)

    # is_visited = [False for _ in range(N+1)]
    # num_good = 0
    # for i in range(1, N+1):
    #     if not is_visited[i]:
    #         queue = []
    #         queue.append(i)
    #         max_heights = [0, ]
    #         while len(queue) > 0:
    #             cur_node = queue.pop(0)
    #             if H[cur_node-1] > max_heights[0]:
    #                 max_heights = [H[cur_node-1], ]
    #             elif H[cur_node-1] == max_heights[0]:
    #                 max_heights.append(H[cur_node-1])
    num_good = 0
    for  i in range(1, N+1):
        H_i = H[i-1]
        if all([H[j-1] < H_i for j in adj_list[i]]):
            num_good += 1

    print(num_good)





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 i in range(m)]
l = [[] for i in range(n)]



for i in range(m):
    if h[ab[i][0]-1] > h[ab[i][1]-1]:
        l[ab[i][0]-1].append(1)
        l[ab[i][1]-1].append(0)
    
    elif h[ab[i][1]-1] > h[ab[i][0]-1]:
        l[ab[i][0]-1].append(0)
        l[ab[i][1]-1].append(1)
    else:
        l[ab[i][0]-1].append(0)
        l[ab[i][1]-1].append(0)
        

cnt = 0

for i in l:
    if len(i) == i.count(1) or len(i) == 0:
        cnt += 1
        
print(cnt)

Submission status: Accepted

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

Submission status: Accepted

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

possible = [1] * (N+1)
possible[0] = 0
ans = 0
for t in range(1, N+1):
    if not possible[t]: continue
    for next in graph[t]:
        if H[t] > H[next]:
            possible[next] = 0
        else:
            possible[t] = 0
    if possible[t]:
        ans += 1

print(ans)

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[a-1] > h[b-1]:
        good[b-1] = False
    else:
        good[a-1] = False
        good[b-1] = False
print(sum(good))

Submission status: Accepted

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

is_good = [True] * n
for a, b in ab:
    if h[a] > h[b]:
        is_good[b] = False
    elif h[a] < h[b]:
        is_good[a] = False
    else:
        is_good[a] = False
        is_good[b] = False
print(sum(is_good))

Submission status: Accepted

Solution code:
def LI(): return list(map(int,input().split()))
N,M = LI()
H = LI()
AB = [LI() for _ in range(M)]
ans = 0
graph = {i:[] for i in range(1,N+1)} #1_indexed
for a,b in AB:
    graph[a].append(b)
    graph[b].append(a)
for i in range(1,N+1):
    if len(graph[i])==0:
        ans += 1
        continue
    height = []
    for x in graph[i]:
        height.append(H[x-1])
    if H[i-1] > max(height):
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
H = list(map(int, input().split()))
r = [True] * N
for _ in range(M):
    A, B = map(int, input().split())
    A -= 1
    B -= 1
    if H[A] > H[B]:
        r[B] = False
    elif H[A] < H[B]:
        r[A] = False
    else:
        r[A] = False
        r[B] = False
print(len(list(_r for _r in r if _r == True)))

Submission status: Accepted

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

ans = [1] * n
for abi in ab:
    if h[abi[0] - 1] == h[abi[1] - 1]:
        ans[abi[0] - 1] = 0
        ans[abi[1] - 1] = 0
    elif h[abi[0] - 1] < h[abi[1] - 1]:
        ans[abi[0] - 1] = 0
    elif h[abi[0] - 1] > h[abi[1] - 1]:
        ans[abi[1] - 1] = 0

print(sum(ans))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# 2020/05/03
# AtCoder Beginner Contest 166 - C

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

goodh = [0] * (n+1)
for i in range(m):
    wk_ab = list(map(int,input().split()))

    if h[wk_ab[0]-1] < h[wk_ab[1]-1]:
        goodh[wk_ab[0]] = 1
    elif h[wk_ab[0]-1] > h[wk_ab[1]-1]:
        goodh[wk_ab[1]] = 1
    else:
        goodh[wk_ab[0]] = 1
        goodh[wk_ab[1]] = 1

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

# Output
print(ans)

Submission status: Accepted

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

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

ans = 0
for i in range(n):
    if A[i] == 0:
        ans += 1
    else:
        pass
print(ans)

Submission status: Accepted

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

T = list(map(int, input().split())) # heights
G = [[] for i in range(N)]

for i 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):
    h = T[i]
    good = True
    for next in G[i]:
        if h <= T[next]:
            good = False
            break
    if good:
        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()))
c = [1]*n
for i in range(m):
  a,b = map(int,input().split())
  a -= 1
  b -= 1
  if h[a] >=  h[b]:
    c[b] = 0
  if h[a] <=  h[b]:
    c[a] = 0
print(sum(c))

Submission status: Accepted

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

Submission status: Accepted

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

ans = np.array(list(range(N)))

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

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
Hi = list(map(int, input().split()))
is_judge_list = [1 for i in range(N)]

for j in range(M):
    A, B = map(int, input().split())
    if Hi[A-1] > Hi[B-1]:
       is_judge_list[B-1] = 0 
    elif Hi[B-1] > Hi[A-1]:
        is_judge_list[A-1] = 0
    else:
        is_judge_list[A-1] = 0
        is_judge_list[B-1] = 0
print(is_judge_list.count(1))

Submission status: Accepted

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

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
import sys
from functools import lru_cache, cmp_to_key
from heapq import merge, heapify, heappop, heappush, nlargest, nsmallest
from math import ceil, floor, gcd, fabs, factorial, fmod, sqrt, inf, log
from collections import defaultdict as dd, deque, Counter as C
from itertools import combinations as comb, permutations as perm
from bisect import bisect_left as bl, bisect_right as br, bisect
from time import perf_counter
from fractions import Fraction
# sys.setrecursionlimit(pow(10, 6))
# sys.stdin = open("input.txt", "r")
# sys.stdout = open("output.txt", "w")
mod = pow(10, 9) + 7
mod2 = 998244353
def data(): return sys.stdin.readline().strip()
def out(*var, end="\n"): sys.stdout.write(" ".join(map(str, var))+end)
def l(): return list(sp())
def sl(): return list(ssp())
def sp(): return map(int, data().split())
def ssp(): return map(str, data().split())
def l1d(n, val=0): return [val for i in range(n)]
def l2d(n, m, val=0): return [l1d(n, val) for j in range(m)]


n, m = sp()
h = l()
graph = dd(set)
for i in range(m):
    u, v = sp()
    graph[u].add(v)
    graph[v].add(u)
answer = 0
for i in range(1, n+1):
    result = True
    for j in graph[i]:
        if h[j-1] >= h[i-1]:
            result = False
            break
    if result:
        answer += 1
out(answer)

Submission status: Accepted

Solution code:
def main():
    n,m=map(int,input().split())
    hh=list(map(int,input().split()))
    path={}
    for _ in range(m):
        a,b=map(int,input().split())
        if a not in path:
            path[a]={b}
        else:
            path[a].add(b)
        if b not in path:
            path[b]={a}
        else:
            path[b].add(a)
    c = 0
    for i,h in enumerate(hh,1):
        if all(h>hh[x-1] for x in path.get(i, set())):
            c += 1
    print(c)
main()

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
h = list(map(int, input().split()))
ok = [True] * 100001

for _ in range(m):
    a, b = map(int, input().split())
    if h[a-1] > h[b-1]:
        ok[b-1] = False
    elif h[b-1] > h[a-1]:
        ok[a-1] = False
    else:
        ok[a-1] = False
        ok[b-1] = False

count = 0

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

print(count)

Submission status: Accepted

Solution code:
def main():
    n, m = map(int, input().split())
    h = list(map(int, input().split()))
    a, b = [], []
    for _ in range(m):
        i, j = map(int, input().split())
        a.append(i)
        b.append(j)
    ans = solve(n, m, h, a, b)
    print(ans)


def solve(n, m, h, a, b):
    isgood = [True for _ in range(n)]
    for i, j in zip(a, b):
        i, j = i - 1, j - 1
        if h[i] > h[j]:
            isgood[j] = False
        elif h[i] < h[j]:
            isgood[i] = False
        else:
            isgood[i] = False
            isgood[j] = False
    ans = sum([1 for i in isgood if i])
    return ans


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
H = list(map(int,input().split()))
edge = [[]for _ in range(N)]
for _ in range(M):
  a,b = map(int,input().split())
  a -= 1
  b -= 1
  edge[a].append(b)
  edge[b].append(a)
can = [True]*N
ans = 0
for i,can_i in enumerate(can):
    if can_i:
        for nxt_i in edge[i]:
            if H[i] < H[nxt_i]:
                can[i] = False
            elif H[i] > H[nxt_i]:
                can[nxt_i] = False
            elif H[i] == H[nxt_i]:
                can[i] = False
                can[nxt_i] = False
        if can[i]:
            ans += 1
print(ans)

Submission status: Accepted

Solution code:
import sys

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

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

    for A,B in AB:
        A -= 1
        B -= 1
        if H[A] > H[B]:
            ans[B] = False
        elif H[A] < H[B]:
            ans[A] = False
        else:
            ans[A] = False
            ans[B] = False
    print(ans.count(True))

if __name__ == "__main__":
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
hights = list(map(int, input().split()))
lis = [0] * n

for i in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    if hights[b] > hights[a]:
        lis[a] = 1
    elif hights[a] > hights[b]:
        lis[b] = 1
    else:
        lis[a] = lis[b] = 1

count =0
for p in range(n):
    if lis[p] == 0:
        count += 1
        
print(count)

Submission status: Accepted

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

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

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

dp = [0] * N

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

    if height[a-1] < height[b-1]:
        dp[a-1] += 1
    elif height[b-1] < height[a-1]:
        dp[b-1] += 1
    else:
        dp[a-1] += 1
        dp[b-1] += 1
        

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

print(ans)

Submission status: Accepted

Solution code:
N, M = list(map(int,input().split()))
H = list(map(int,input().split()))
A, B = [], []
for i in range(M):
  temp = list(map(int,input().split()))
  A.append(temp[0])
  B.append(temp[1])
roadlist = []
for i in range(N):
  roadlist.append([])
for i in range(M):
  roadlist[A[i]-1].append(B[i]-1)
  roadlist[B[i]-1].append(A[i]-1)
ans = 0
for i in range(N):
  if(len(roadlist[i])==0):
    ans += 1
  else:
    flag = 0
    for j in range(len(roadlist[i])):
      if(H[i] <= H[roadlist[i][j]]):
        flag = 1
        break
    if(flag==0):
      ans += 1
print(ans)

Submission status: Accepted

Solution code:
import copy

n,m=map(int,input().split())
h=list(map(int,input().split()))
l=[]
for i in range(m):
    a,b=map(int,input().split())
    l.append([a,b])
    
ll=[0]*n

for j in l:
    if h[j[0]-1]>h[j[1]-1]:
        ll[j[1]-1]+=1
    elif h[j[0]-1]==h[j[1]-1]:
        ll[j[1]-1]+=1
        ll[j[0]-1]+=1
    else:
        ll[j[0]-1]+=1

ans=0

for k in ll:
    if k==0:
        ans+=1
print(ans)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
List=list(map(int,input().split()))
List.insert(0,0)
l=[1]*n
l.insert(0,0)
for i in range(m):
  s=list(map(int,input().split()))
  if List[s[0]]>List[s[1]]:
    l[s[1]]=0
  elif List[s[0]]<List[s[1]]:
    l[s[0]]=0
  else:
    l[s[1]]=0
    l[s[0]]=0
print(l.count(1))

Submission status: Accepted

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

import collections


def solve(n, m, hs, adj_list):
    res = 0
    for u, vs in enumerate(adj_list):
        heights = collections.Counter(hs[v] for v in vs)
        heights[hs[u]] += 1
        if max(heights.keys()) == hs[u] and heights[hs[u]] == 1:
            res += 1
    return res


def main():
    n, m = (int(z) for z in input().split())
    hs = [int(z) for z in input().split()]
    adj_list = [set() for _ in range(n)]
    for _ in range(m):
        a, b = (int(z) - 1 for z in input().split())
        adj_list[a].add(b)
        adj_list[b].add(a)
    res = solve(n, m, hs, adj_list)
    print(res)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
h = list(map(int, input().split()))
path = [[] for _ in range(n)]
pp = set()
for _ in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    if (a, b) in pp:
        continue
    else:
        pp.add((a, b))
        path[a].append(b)
    if (b, a) in pp:
        continue
    else:
        pp.add((b, a))
        path[b].append(a)
# print(path)
ans = 0
for i in range(n):
    ok = True
    for j in path[i]:
        if h[i] <= h[j]:
            ok = False
    if ok:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
@author: H_Hoshigi
"""
def main():
    N, M = map(int, input().split())
    H_list = list(map(int, input().split()))
    edge_list = [ [] for i in range(N)]
    # i番目の展望台と道でつながっている展望台の番号のリスト、のリスト。
    for i in range(M):
        A, B = map(int, input().split())
        edge_list[A-1].append(B-1)
        edge_list[B-1].append(A-1)
    answer = 0
    for i in range(N):
        H_i = H_list[i]
        No_i_is_good = True
        for j in edge_list[i]:
            if H_list[j] >= H_i:
                No_i_is_good = False
                break
        if No_i_is_good:
            answer += 1
    print(answer)

if __name__ == "__main__":
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
inputs = open(0).readlines()
n, m = map(int, inputs[0].split())
*H, = map(int, inputs[1].split())
AB = [map(int, ab.split())for ab in inputs[2:]]

C = [[] for _ in range(n)]
for a, b in AB:
    C[a-1].append(H[b-1])
    C[b-1].append(H[a-1])
ans = 0
for c, h in zip(C, H):
    ans += all(h > x for x in c)
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
N, M = map(int, input().split())
H_list = list(map(int, input().split()))

low_set = set()
for i in range(M):
    A, B = map(int, input().split())
    if H_list[A - 1] == H_list[B - 1]:
        low_set.add(A)
        low_set.add(B)
    elif H_list[A - 1] > H_list[B - 1]:
        low_set.add(B)
    else:
        low_set.add(A)

print(N - len(low_set))

Submission status: Accepted

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

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

View = [0] * N

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

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

print(ans)

Submission status: Accepted

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

count = 0
good_list = [i for i in range(1, n + 1)]
bad_list = []
for i in range(m):
    a, b = list(map(int, input().split()))

    if h[a - 1] < h[b - 1]:
        bad_list.append(a)
    elif h[a - 1] > h[b - 1]:
        bad_list.append(b)
    else:
        bad_list.append(a)
        bad_list.append(b)

print(len(set(good_list) - set(bad_list)))

Submission status: Accepted

Solution code:

from collections import deque
n,m = map(int, input().split())
h = tuple(map(int, input().split()))
G = [[] for _ in range(n+1)]
seen = [-1]*(n+1)
for i in range(m):
    a,b = map(int, input().split())
    G[a].append(b)
    G[b].append(a)
ans = 0
for j in range(1,n+1):
    tmp = h[j-1]
    flag = True
    for nq in G[j]:
        if h[nq-1]>= tmp:
            flag = False
            break
    if flag:
        ans +=1
print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

print(n-len(bad))

Submission status: Accepted

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

ans = 0
for i in range(n):
    if len(table[i]) > 0:
        if h[i] > max(table[i]):
            ans += 1
    else:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
import math
import collections

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

    ans = [1]*N

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

    #print(ans)
    print(sum(ans))
    return 0

if __name__ == '__main__':
    main()

Submission status: Accepted

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

connection = {}
for pair in pairs:
    if not pair[0] in connection:
        connection[pair[0]] = set()
    if not pair[1] in connection:
        connection[pair[1]] = set()
    connection[pair[0]].add(pair[1])
    connection[pair[1]].add(pair[0])

#print(connection)

ans = 0
for i, h in enumerate(H):
    candidates = []
    for c in list(connection.get(i+1,set())):
        candidates.append(H[c-1])
    #print(i, h, candidates)
    if len(candidates) == 0 or h > max(candidates):
        ans += 1
print(ans)

Submission status: Accepted

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

ary = [0 for i in range(n)]
chk = [False for i in range(n)]
for i in range(m):
	a, b = map(int, input().split())
	#chk[a-1] = True
	#chk[b-1] = True
	if h[a-1] < h[b-1]:
		ary[a-1] += 1
	elif h[a-1] > h[b-1]:
		ary[b-1] += 1
	else:
		ary[a-1] += 1
		ary[b-1] += 1

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

Submission status: Accepted

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

import sys

DEBUG = False

def read(t):
    return t(sys.stdin.readline().rstrip())


def read_list(t, sep = " "):
    return [t(s) for s in sys.stdin.readline().rstrip().split(sep)]


def dprint(*args, **kwargs):
    if DEBUG:
        print(*args, **kwargs)
    return


def main():
    n, m = read_list(int)
    heights = read_list(int)
    roads = [None] * m
    for i in range(m):
        roads[i] = tuple(read_list(int))

    is_good = [True] * n
    for (src, dst) in roads:
        src -= 1
        dst -= 1
        if heights[src] <= heights[dst]:
            is_good[src] = False
        if heights[src] >= heights[dst]:
            is_good[dst] = False
    print(len([i + 1 for i in range(n) if is_good[i]]))

if __name__ == "__main__":
    main()

Submission status: Accepted

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