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()))
i = 0
ABs = []
while True:
  if M <= i:
    break
  ABs.append(list(map(int, input().split())))
  i += 1
r = [0] * N

for A, B in ABs:
  if Hs[A-1] <= Hs[B-1]:
    r[A-1] = -1

  if Hs[B-1] <= Hs[A-1]:
    r[B-1] = -1

print(r.count(0))

Submission status: Accepted

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

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

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

ans = 0

for i,e in enumerate(edges):
    flag = True
    for j in e:
        if h[j] >= h[i]:
            flag = False
    if flag:
        ans += 1

print(ans)

Submission status: Accepted

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

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

ans = {}

for _ in range(M):
    a, b = map(int, input().split())
    if H[a-1] > H[b-1]:
        ans[str(b)] = 1
    elif H[b-1] > H[a-1]:
        ans[str(a)] = 1
    else:
        ans[str(a)] = 1
        ans[str(b)] = 1

print(N - len(ans))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import numpy as np

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

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

score_ = 0
for i, adjs in enumerate(adj_list):
    is_max = True
    for adj in adjs:
        if score[i] <= score[adj]:
            is_max = False
    if is_max:
        score_+=1
print(score_)

Submission status: Accepted

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

g = {}
for i in range(1, n+1):
    g[i] = 0

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

ans = 0
for i in range(1, n+1):
    if h[i-1] > g[i]:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
import numpy

n,m = map(int,input().split(" "))
h = [int(e) for e in input().split(" ")]
ab = []
tenbou = {}
best = 0

for i in range(1,n+1):
    tenbou[i] = []
for i in range(m):
    ab.append([int(e) for e in input().split(" ")])

for road in ab:
    tenbou[road[0]].append(road[1])
    tenbou[road[1]].append(road[0])

for i in tenbou:
    tmp = 0
    for j in tenbou[i]:
        if (h[i-1] <= h[j-1]):
            tmp += 1
    if tmp == 0:
        best += 1
print(best)

Submission status: Accepted

Solution code:

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

    td = {}
    goodtd = {}
    for i in range(N):
        td[i+1] = Hs[i]
        goodtd[i+1] = 0


    for i in range(M):
        A, B = map(int, input().split())
        if td[A] < td[B]:
            if A in goodtd:
                del goodtd[A]
        elif td[B] < td[A]:
            if B in goodtd:
                del goodtd[B]
        elif td[B] == td[A]:
            if A in goodtd:
                del goodtd[A]
            if B in goodtd:
                del goodtd[B]
    
    print(len(goodtd))

solve()

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
high = list(map(int, input().split()))
road = [list(map(int, input().split())) for i in range(M)]
p=[True for _ in range(N)]

for i in road:
    if high[i[0]-1]<=high[i[1]-1] and p[i[0]-1]==True:
        p[i[0]-1]=False
        
    if high[i[0]-1]>=high[i[1]-1] and p[i[1]-1]==True:
        p[i[1]-1]=False

print(p.count(True))

Submission status: Accepted

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

#print(N)
#print(M)
#print(Hs)
#print(loads)

ans = 0

hoge = [0] * N

for load in loads:
    if(Hs[load[0]-1] < Hs[load[1]-1]):
        hoge[load[0] -1] += 1
    
    elif(Hs[load[0]-1] > Hs[load[1]-1]):
        hoge[load[1]-1] +=1

    else:
        hoge[load[0] -1] += 1
        hoge[load[1]-1] +=1
#print(hoge)
print(hoge.count(0))

Submission status: Accepted

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

s = set()
for i in range(M):
    if H[A[i] - 1] - H[B[i] - 1] <= 0:
        s.add(A[i])
    if H[B[i] - 1] - H[A[i] - 1] <= 0:
        s.add(B[i])
ans = N - len(s)
print(ans)

Submission status: Accepted

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

roads = []
for i in range(n): roads.append([])

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

ans = 0
for i in range(n):
    flg = True
    for j in roads[i]:
        if h[i] <= h[j]:
            flg = False
            break
    if flg: ans += 1

print(ans)

Submission status: Accepted

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

a = list()
b = list()

for x in range(0, m):
    A, B = map(int, input().split())
    a.append(A)
    b.append(B)

check = [0]*n

for x, y in zip(a, b):
    if check[x-1] != -1:
        if h[x-1] > h[y-1]:
            check[x-1] = 1
        else:
            check[x-1] = -1
    if check[y-1] != -1:
        if h[x-1] < h[y-1]:
            check[y-1] = 1
        else:
            check[y-1] = -1

print(len(list(filter(lambda x: x != -1, check))))

Submission status: Accepted

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

for mm in range(m):
    a, b = list(map(int, input().split()))
    if h_list[a-1] - h_list[b-1] < 0:
        hh_list[a-1] = 0
    if h_list[b-1] - h_list[a-1] < 0:
        hh_list[b-1] = 0
    if h_list[a-1] == h_list[b-1]:
        hh_list[a-1] = 0
        hh_list[b-1] = 0

counter = 0
for hh in hh_list:
    if hh >= 1:
        counter += 1
print(counter)

Submission status: Accepted

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

route = [[H[i]] for i in range(N)]

for i in range(M):
    A, B = map(int, input().split())
    A = A - 1
    B = B - 1
    route[A].append(H[B])
    route[B].append(H[A])

ans = 0
for i in range(len(route)):
    if route[i].count(H[i]) != 1:
        continue
    if H[i] == max(route[i]):
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
import networkx as nx
N, M = list(map(int, input().strip().split()))
labels = list(map(int, input().strip().split()))
G = nx.empty_graph(N)
for _ in range(M):
	edge = tuple(map(int, input().strip().split()))
	G.add_edge(edge[0]-1,edge[1]-1)
for nidx, label in enumerate(labels):
	G.nodes[nidx]['high'] = label

good_list = []
for nidx in G.nodes:
	neighbors_high = [0]
	for neighbor in G.neighbors(nidx):
		neighbors_high.append(G.nodes[neighbor]['high'])
	if G.nodes[nidx]['high'] > max(neighbors_high):
		good_list.append(nidx)

print(len(good_list))

Submission status: Accepted

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

Submission status: Accepted

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

ans = 0
i = 0
 
for one in H:
 
  i += 1
  if one == []:
    ans += 1
  else:
    for k in one:
      if k >= h[i-1]:
        break
    else:
      ans += 1
        
print(ans)

Submission status: Accepted

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

all_tenbo = list(range(1, N+1))
not_good = []

for i in range(M):
    A, B = map(int, input().split())
    if H[A-1] <= H[B-1]:
        not_good.append(A)
    if H[B-1] <= H[A-1]:
        not_good.append(B)

print(len(list(set(all_tenbo)-set(not_good))))

Submission status: Accepted

Solution code:
n,m = map(int, input().split())
h = list(map(int, input().split()))
graph = [[] for i in range(n)]
count = 0
for i in range(m):
    x,y = map(int, input().split())
    graph[x-1].append(y-1)
    graph[y-1].append(x-1)
for i in range(n):
    yoi = True
    for j in graph[i]:
        if h[i] >h[j]:
            pass
        else:
            yoi = False
            break
    if yoi:
        count += 1
print(count)

Submission status: Accepted

Solution code:
def main():
    n, m = [int(e) for e in input().split()]
    H = [int(e) for e in input().split()]
    AB = [[int(e) for e in input().split()] for i in range(m)]

    W = [0] * n
    for ab in AB:
        a, b = ab
        ha, hb = H[a - 1], H[b - 1]
        if ha > hb:
            W[b - 1] = 1

        elif ha < hb:
            W[a - 1] = 1

        else:
            W[a - 1] = 1
            W[b - 1] = 1

    print(W.count(0))


if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

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

R = []
for nn in range(N):
  s = set()
  R.append(s)
for i in range(M):
  aa, bb = map(int, input().split())
  R[aa-1].add(bb)
  R[bb-1].add(aa)

good = 0
for nn in range(N):
  hh = H[nn]
  s = set()
  for mm in R[nn]:
    s.add(H[mm-1])
  if(len(s) == 0):
    good += 1
  elif(max(s) < hh):
    good += 1

print(good)

Submission status: Accepted

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

flag = [0 for _ in range(n)]
for i in range(m):
    a, b = map(int, input().split())
    a, b = a-1, b-1
    if a==b:continue
    if h[a] > h[b]:
        flag[b] = -1
    elif h[a] == h[b]:
        flag[a] = -1
        flag[b] = -1
    else:
        flag[a] = -1
        
cnt = 0
for i in range(n):
    if flag[i] != -1:
        cnt += 1
print(cnt)

Submission status: Accepted

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

good = list(range(1,N+1))
good = [1]*N

for j in range(M):
  a,b=map(int, input().split())
  #print(a,b)
  if H[a-1]>H[b-1]:
    #good.remove(b)
    good[b-1] = 0
  elif H[a-1]<H[b-1]:
    #good.remove(a)
    good[a-1] = 0
  elif H[a-1]==H[b-1]:
    good[a-1] = 0
    good[b-1] = 0
  #print(good)
  
print(sum(good))

Submission status: Accepted

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

# 展望台の接続を辞書で整理する
## 辞書の初期化
temp_dic = {}
for x in range(1,n+1):
    temp_dic[x] = []

for a,b in road_list:
    temp_dic[a].append(hight_list[b-1])
    temp_dic[b].append(hight_list[a-1])

good_points = 0
for k,v in temp_dic.items():
    if len(v) == 0:
        good_points += 1
        continue

    if hight_list[k-1] > max(v):
        good_points += 1

print(good_points)

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
High = list(map(int,input().split()))
Path = [None]*M
for i in range(M):
    #hyoujun-ka
    Path[i] =list(map(int,input().split()))
    Path[i][0]-=1
    Path[i][1]-=1

Graph = [None]*N
for i in range(N):
    Graph[i] =[]
for i in range(M):
    Graph[Path[i][0]].append(Path[i][1])
    Graph[Path[i][1]].append(Path[i][0])
for i in range(N):
    Graph[i] = set(Graph[i])
    Graph[i] = list(Graph[i])


ans=0
for i in range(N):
    if len(Graph) == 0:
        ans+=1
    else:
        for j in range(len(Graph[i])):
            if High[i] <= High[Graph[i][j]]:
                break
        else:
            ans+=1
print(ans)

Submission status: Accepted

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

for i in range(n):
    if visited[i] != 0:
        continue
    if v[i] == []:
        ans += 1
        visited[i] = 1
    else:
        for j in v[i]:
            visited[j] = 1
            if h[j] >= h[i]:
                visited[j] = 0
                break
        else:
            ans += 1
        visited[i] = 1
print(ans)

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
h = list(map(int,input().split()))
h_c = [0 for i in range(n)]
a=[]
b=[]
for i in range(m):
    a_1,b_1 = list(map(int,input().split()))
    a.append(a_1)
    b.append(b_1)

for i in range(m):
    if h[a[i]-1] <= h[b[i]-1]:
        h_c[a[i]-1]+=1
    if h[b[i]-1] <= h[a[i]-1]:
        h_c[b[i]-1]+=1


print(h_c.count(0))

Submission status: Accepted

Solution code:
def resolve():
    '''
    code here
    '''
    N, M = [int(item) for item in input().split()]

    H_list = [int(item) for item in input().split()]

    path_list = [[int(item) for item in input().split()] for _ in range(M)]

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

    for A, B in path_list:
        path_list2[A] += [B]
        path_list2[B] += [A]

    temp_list = []
    for item in path_list2:
        temp_list.append(list(set(item)))
    
    path_list2 = temp_list

    # print(path_list2)

    def nice(i):
        if len(path_list2[i]) >= 1:
            for j in path_list2[i]:
                if H_list[i-1] <= H_list[j-1]:
                    return False
            else:
                return True
                
        else:
            return True


    cnt = 0
    for i in range(N):
        if nice(i+1):
            cnt += 1
            # print(i+1)
    
    print(cnt)


if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
height = input().split()
area = [[] for i in range(N)]
for i in range(M):
    road = input().split()
    for place in road:
        area[int(road[0])-1].append(int(height[int(road[1])-1]))
        area[int(road[1])-1].append(int(height[int(road[0])-1]))
counter = 0
for i in range(N):
    if not area[i]:
        counter=counter+1
    elif int(height[i]) > max(area[i]):
        counter=counter+1
print(counter)

Submission status: Accepted

Solution code:
def main():
    input1 = input().split()
    N = int(input1[0])
    M = int(input1[1])

    H = [0]*N
    input2 = input().split()
    for i in range(N):
        H[i] = int(input2[i])
    
    A = [0]*M
    B = [0]*M
    for i in range(M):
        input3 = input().split()
        A[i] = int(input3[0])
        B[i] = int(input3[1])

    mountain = [0]*N
    for i in range(M):
        if H[A[i]-1] <= H[B[i]-1]:
            mountain[A[i]-1] = 1
        if H[B[i]-1] <= H[A[i]-1]:
            mountain[B[i]-1] = 1
    result = 0
    for i in range(N):
        if mountain[i] == 0:
            result += 1
            
    print(result)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from sys import stderr

def debug(*args):
    print(*args, file=stderr)

n_observatory_num, m_roads_num = map(int, input().split())
hi_heights = list(map(int, input().split()))

# def get_height_for(a_observaotry):
#     return hi_heights[a_observaotry+1]

ab_roads_fromto = [map(int, input().split()) for _ in range(m_roads_num)]


observatory_x_connected_to = {}

for a, b in ab_roads_fromto:
    a -= 1
    b -= 1
    if not a in observatory_x_connected_to:
        observatory_x_connected_to[a] = []
    if not b in observatory_x_connected_to:
        observatory_x_connected_to[b] = []

    observatory_x_connected_to[a].append(b)
    observatory_x_connected_to[b].append(a)

# debug(observatory_x_connected_to)

result = 0
for observatory_i, observatory_i_height in enumerate(hi_heights):
    # observatory_i_height = get_height_for(observatory_i)
    if not observatory_i in observatory_x_connected_to:
        # debug('good no connection' + str(observatory_i))
        result += 1
        continue

    good = True
    for connected_to in observatory_x_connected_to[observatory_i]:
        if observatory_i_height <= hi_heights[connected_to]:
            good = False
            # debug('not good' + str(observatory_i))
            break
    
    if good:
        # debug('good highest' + str(observatory_i))
        result += 1

print(result)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
height = list(map(int,input().split()))
def loadmake(a, b, load):
    if a in load.keys():
        load[a].append(b)
    else:
        load[a] = [b]
load = {}
for m in range(M):
    a, b = map(int, input().split())
    loadmake(a-1, b-1, load)
    loadmake(b-1,a-1,load)
oklist = [1]*N
for n in range(N):
    if n in load.keys():
        for l in load[n]:
            if height[l] >= height[n]:
                oklist[n] = 0
print(sum(oklist))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N, M = (int(i) for i in input().split())
H = [int(x) for x in input().split()]
#roads = [[int(i) for i in input().split()] for i in range(N)]
ans = set()
for i in range(1, N+1):
    ans.add(i)

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

Submission status: Accepted

Solution code:
import copy

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

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

print(len(li)-li.count(0))

Submission status: Accepted

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

import collections

lis_h, all_h = [], [0]*n
for j in range(m):
  a,b = map(int, input().split())
  all_h[a-1]+=1
  all_h[b-1]+=1

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

#two_ = [j+1 for j,k in enumerate(all_h) if all_h[j]>1 ]
print(n-len(set(lis_h)))

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.buffer.readline
arr = []
n,m= list(map(int,readline().rstrip().split()))
h = readline().rstrip().decode().split()
for i in range(m):
  k,l= list(map(int,readline().rstrip().split()))
  if int(h[k-1]) > int(h[l-1]):
    arr.append(l)
  elif int(h[k-1]) < int(h[l-1]):
    arr.append(k)
  else:
    arr.append(l)
    arr.append(k)
print(n-len(set(arr)))

Submission status: Accepted

Solution code:
from collections import deque
n, m = map(int, input().split())
h = list(map(int, input().split()))
edges = [[] for i in range(n+1)]
for i in range(m):
    a, b = map(int, input().split())
    edges[a-1].append(b-1)
    edges[b-1].append(a-1)
check = [0]*n
q = deque()
for i in range(n):
    q.append(i)
ans = 0
while q:
    node = q.pop()
    if check[node] != 0:
        continue
    else:
        check[node] = 1
        count = 0
        for v in edges[node]:
            q.append(v)
            if h[node] > h[v]:
                check[v] = 1
                count += 1
            elif h[node] == h[v]:
                check[v] = 1
        if count == len(edges[node]):
            ans += 1
print(ans)

Submission status: Accepted

Solution code:
import sys,bisect,string,math,time,functools,random
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
from itertools import permutations,combinations,groupby
def Golf():*a,=map(int,open(0))
def I():return int(input())
def S_():return input()
def IS():return input().split()
def LS():return [i for i in input().split()]
def LI():return [int(i) for i in input().split()]
def LI_():return [int(i)-1 for i in input().split()]
def NI(n):return [int(input()) for i in range(n)]
def NI_(n):return [int(input())-1 for i in range(n)]
def StoLI():return [ord(i)-97 for i in input()]
def ItoS(n):return chr(n+97)
def LtoS(ls):return ''.join([chr(i+97) for i in ls])
def GI(V,E,ls=None,Directed=False,index=1):
    org_inp=[];g=[[] for i in range(V)]
    FromStdin=True if ls==None else False
    for i in range(E):
        if FromStdin:
            inp=LI()
            a,b,c=(inp+[1])[:3]
            org_inp.append(inp)
        else:
            index=0
            a,b,c=(ls[i]+[1])[:3]
        if index==1:a-=1;b-=1
        aa=(a,c);bb=(b,c);g[a].append(bb)
        if not Directed:g[b].append(aa)
    return g,org_inp
def GGI(h,w,search=None,replacement_of_found='.',mp_def={'#':1,'.':0},boundary=1):
#h,w,g,sg=GGI(h,w,search=['S','G'],replacement_of_found='.',mp_def={'#':1,'.':0}) # sample usage
    mp=[boundary]*(w+2);found={}
    for i in range(h):
        s=input()
        for char in search:
            if char in s:
                found[char]=((i+1)*(w+2)+s.index(char)+1)
                mp_def[char]=mp_def[replacement_of_found]
        mp+=[boundary]+[mp_def[j] for j in s]+[boundary]
    mp+=[boundary]*(w+2)
    return h+2,w+2,mp,found
def TI(n):return GI(n,n-1)
def bit_combination(k,n=2):
    rt=[]
    for tb in range(n**k):
        s=[tb//(n**bt)%n for bt in range(k)];rt+=[s]
    return rt
def show(*inp,end='\n'):
    if show_flg:print(*inp,end=end)

YN=['YES','NO'];Yn=['Yes','No']
mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
#sys.setrecursionlimit(10**7)
input=lambda: sys.stdin.readline().rstrip()

class Comb:
    def __init__(self,n,mo=10**9+7):
        self.fac=[0]*(n+1)
        self.inv=[1]*(n+1)
        self.fac[0]=1
        self.fact(n)
        for i in range(1,n+1):
            self.fac[i]=i*self.fac[i-1]%mo
            self.inv[n]*=i
            self.inv[n]%=mo
        self.inv[n]=pow(self.inv[n],mo-2,mo)
        for i in range(1,n):
            self.inv[n-i]=self.inv[n-i+1]*(n-i+1)%mo
        return
    
    def fact(self,n):
        return self.fac[n]
        
    def invf(self,n):
        return self.inv[n]

    def comb(self,x,y):
        if y<0 or y>x:
            return 0
        return self.fac[x]*self.inv[x-y]*self.inv[y]%mo

class Tree:
    def __init__(self,inp_size=None,init=True):
        if init:
            self.stdin(inp_size)
        return

    def stdin(self,inp_size=None):
        if inp_size==None:
            self.size=int(input())
        else:
            self.size=inp_size
        self.edges,_=GI(self.size,self.size-1)
        return
    
    def listin(self,ls):
        self.size=len(ls)+1
        self.edges,_=GI(self.size,self.size-1,ls)
        return

    def __str__(self):
        return  str(self.edges)

    def dfs(self,x,func=lambda prv,nx,dist:prv+dist,root_v=0):
        q=deque()
        q.append(x)
        v=[-1]*self.size
        v[x]=root_v
        while q:
            c=q.pop()
            for nb,d in self.edges[c]:
                if v[nb]==-1:
                    q.append(nb)
                    v[nb]=func(v[c],nb,d)
        return v

    def EulerTour(self,x,func=lambda prv,nx,dist:prv+dist,root_v=0):
        q=deque()
        q.append((-1,x))
        v=[None]*self.size
        v[x]=root_v
        et=[]
        while q:
            cb,ce=q.pop()
            et.append(ce)
            for nb,d in self.edges[ce]:
                if v[nb]==None:
                    q.append((nb,ce))
                    q.append((ce,nb))
                    v[nb]=func(v[ce],nb,d)
        vid=[[-1,-1]for i in range(self.size)]
        for i,j in enumerate(et):
            if vid[j][0]==-1:
                vid[j][0]=i
            else:
                vid[j][1]=i
        return v,et,vid
    
    def LCA_init(self,depth,et):
        self.st=SegTree(self.size*2-1,func=min,ide=inf)
        for i,j in enumerate(et):
            self.st.update(i,j)
        self.LCA_init_stat==True
        return
    
    def LCA(self,root,x,y):
        if self.LCA_init_stat==False:
            depth,et,vid=self.EulerTour(root)
            self.LCA_init(depth,et)
        return self.st.query(x,y+1)

show_flg=False
show_flg=True


n,m=LI()
h=LI()
ans=0
g=[[]for i in range(n)]
for i in range(m):
    a,b=LI_()
    
    if h[a]>=h[b]:
        g[b].append(a)
    if h[b]>=h[a]:
        g[a].append(b)


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

Submission status: Accepted

Solution code:
input_NM = input().split(' ')
N = int(input_NM[0])
M = int(input_NM[1])
input_H = input().split(' ')
H = []
for i in range(len(input_H)):
  H.append(int(input_H[i]))
  
good = [1 for i in range(N)]#1:good,0:bad

for i in range(M):
  input_AB = input().split(' ')
  A = int(input_AB[0])
  B = int(input_AB[1])
  HA = H[A-1]
  HB = H[B-1]
#  min_AB = min(A,B)
  if HA > HB:
    min_AB = B-1
    if good[min_AB] == 1:
      good[min_AB] = 0
  elif HA < HB:
    min_AB = A-1
    if good[min_AB] == 1:
      good[min_AB] = 0
  else:
    if good[A-1] ==1:
      good[A-1] = 0
    if good[B-1] ==1:
      good[B-1] = 0

ng = 0
for i in range(len(good)):
  if good[i] != 0:
    ng = ng + 1

print(ng)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
H = list(map(int,input().split()))
Road = [sorted(list(map(int, input().split()))) for _ in range(M)]
num = N
Mem = [0 for _ in range(N)]
for j in range(M):
  if H[Road[j][0]-1] > H[Road[j][1]-1] and Mem[Road[j][1]-1] != 1:
    num -= 1
    Mem[Road[j][1]-1] = 1
  elif H[Road[j][1]-1] > H[Road[j][0]-1] and Mem[Road[j][0]-1] != 1:
    num -= 1
    Mem[Road[j][0]-1] = 1
  elif H[Road[j][1]-1] == H[Road[j][0]-1]:
    if Mem[Road[j][0]-1] != 1 and Mem[Road[j][1]-1] != 1:
      num -= 2
      Mem[Road[j][0]-1] = 1
      Mem[Road[j][1]-1] = 1
    elif Mem[Road[j][0]-1] == 1 and Mem[Road[j][1]-1] == 1:
      continue
    else:
      num -= 1
      Mem[Road[j][0]-1] = 1
      Mem[Road[j][1]-1] = 1
print(num)

Submission status: Accepted

Solution code:
import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

""" 道は一本！ """

N, M = map(int, readline().split())
H = [0] + list(map(int, readline().split()))
A = [0] * (N + 1)

m = map(int, read().split())
for a, b in zip(m, m):
    for _ in range(2):
        A[a] = max(A[a], H[b])
        a, b = b, a

print(sum(x > y for x, y in zip(H, A)))

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
R = lambda: map(int, input().split())
n, m = R()
h = [None, *R()]
g = [0] + [1] * n
for _ in range(m):
  a, b = R()
  g[a] &= h[a] > h[b]
  g[b] &= h[b] > h[a]
print(sum(g))

Submission status: Accepted

Solution code:

def input_from_console():
    n, m = map(int, input().split())
    ab_list = []
    h_list = map(int, input().split())
    for i in range(m):
        a,b = map(int, input().split())
        ab_list.append((a, b))
    return n, m, list(h_list), list(ab_list)


def solve(n, m, h_list, ab_list):
    good_observatory = [True] * n
    for (a, b) in ab_list:
        if h_list[a-1] < h_list[b-1]:
            good_observatory[a - 1] = False
        if h_list[a-1] > h_list[b-1]:
            good_observatory[b - 1] = False
        if h_list[a-1] == h_list[b-1]:
            good_observatory[a - 1] = False
            good_observatory[b - 1] = False

    return sum(good_observatory)


def main():
    n, m, h_list, ab_list = input_from_console()
    print(solve(n, m, h_list, ab_list))


if __name__ == "__main__":
    import sys

    if sys.gettrace():  # Check if the python interpreter is in debug mode or not.
        check_cases()
    else:
        main()

Submission status: Accepted

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

kyuryo = [set() for _ in range(N)]
for michi in range(M):
    kyuryo[A[michi]].add(B[michi])
    kyuryo[B[michi]].add(A[michi])

nice_count = 0
for tenbodai in range(N):
    for neighbor in kyuryo[tenbodai]:
        if H[neighbor] >= H[tenbodai]:
            break
    else:
        nice_count += 1

print(nice_count)