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:
# coding: utf-8

s = list(map(int, input().split(" ")))

tnb = s[0]
mc = s[1]

hk = list(map(int, input().split(" ")))
v = []
for i in range(mc) :
    tmp = list(map(int, input().split(" ")))
    x = tmp[0] - 1
    y = tmp[1] - 1
    ap = y
    if hk[x] < hk[y] :
        ap = x
        v.append(ap)
        continue
    elif hk[x] == hk[y] :
        v.append(x)
        v.append(y)
        continue
    v.append(ap)

ans = tnb - len(set(v))
print(ans)

Submission status: Accepted

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

for i in range(M):
    a,b=map(int, input().split())
    li[a].append(b)
    li[b].append(a)
sum = 0

for i in range(N):
    if len(li[i+1]) == 1:
        sum += 1
    else:
        n = False
        for j in range(len(li[i+1])-1):

            if H[i] <= H[li[i+1][j+1]-1]:
                n = True
                break
        if n == False:

            sum+=1

print(sum)

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
H=list(map(int,input().split()))
box=[[] for i in range(N)]
count=0
for i in range(M):
    a,b=map(int,input().split())
    box[a-1].append(b-1)
    box[b-1].append(a-1)
for i in range(N):
    queue=box[i]
    hmax=H[i]
    count+=1
    for x in queue:
        if H[x]>=hmax:
            count-=1
            break
print(count)

Submission status: Accepted

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

Submission status: Accepted

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

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

a = [list(map(int,input().split())) for i in range(m)]

good = [1] * (n+1)


for i in a:
    if h[i[0]-1] < h[i[1]-1]:
        good[i[0]] = 0
    elif h[i[0]-1] > h[i[1]-1]:
        good[i[1]] = 0
    else:
        good[i[0]] = 0
        good[i[1]] = 0

print(good.count(1)-1)

Submission status: Accepted

Solution code:
import sys
from random import choice,randint
inp=sys.stdin.readline
out=sys.stdout.write
flsh=sys.stdout.flush
 
sys.setrecursionlimit(10**9)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]
 
def MI(): return map(int, inp().strip().split())
def LI(): return list(map(int, inp().strip().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines().strip()]
def LI_(): return [int(x)-1 for x in inp().strip().split()]
def LF(): return [float(x) for x in inp().strip().split()]
def LS(): return inp().strip().split()
def I(): return int(inp().strip())
def F(): return float(inp().strip())
def S(): return inp().strip()
def pf(s): return out(s+'\n')
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)

def main():
    n,m=MI()
    h = LI()
    d = dict()
    for i in range(1,n+1):
        d[i]=[]
    for i in range(m):
        a,b=MI()
        d[a].append(b)
        d[b].append(a)
    # print(d)
    c=0
    for i in d:
        x = h[i-1]
        f=0
        for j in d[i]:
            if h[j-1]>=x:
                f=1
                break
        if f==0:
            c+=1
    print(c)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
H=list(map(int,input().split()))
AB=[]
Dict={}
for i in range(N):
    Dict[i+1]=H[i]
for i in range(M):
    AB.append(list(map(int,input().split())))
    
ng=set()
for i in AB:
    a,b=i[0],i[1]
    if Dict[a]<=Dict[b]:
        ng.add(a)
    if Dict[b]<=Dict[a]:
        ng.add(b)
print(len(set(Dict.keys())-ng))

Submission status: Accepted

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

cnt = []
for i in range(m):
    if H[M[i][0]-1] < H[M[i][1]-1]:
        cnt.append(M[i][0])
    elif H[M[i][0]-1] > H[M[i][1]-1]:
        cnt.append(M[i][1])
    else:
        cnt.append(M[i][0])
        cnt.append(M[i][1])
        
import collections
c = collections.Counter(cnt)
print(n-len(c))

Submission status: Accepted

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

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

print(s.count(1))

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
l=list(map(int,input().split()))
d=dict({})
for i in range(m):
  a,b=map(int,input().split())
  if a in d:
    d[a].append(l[b-1])
  else:
    d[a]=[l[b-1]]
  if b in d:
    d[b].append(l[a-1])
  else:
    d[b]=[l[a-1]]
for x in d.keys():
  z=max(d[x])
  if l[x-1]>z:
    pass
  else:
    n-=1
print(n)

Submission status: Accepted

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

Submission status: Accepted

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

ans = [1] * n

for _ in range(m):
  a, b = map(int, input().split())
  a -= 1
  b -= 1
  if hs[a] < hs[b]:
    ans[a] = 0
  elif hs[a] == hs[b]:
    ans[a] = 0
    ans[b] = 0
  else:
    ans[b] = 0

print(sum(ans))

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
heights=list(map(int,input().split()))
heights_w=sorted([(h,i+1) for i,h in enumerate(heights)])[::-1]
cons={i+1:set() for i in range(n)}
for _ in range(m):
  a,b=map(int,input().split())
  cons[a].add(b)
  cons[b].add(a)

debug=False
watched=set()
res=0
if debug: res_m=set()
for h,i in heights_w:
  if i in watched:
    continue
  watched.add(i)
  flg=True
  for con in cons[i]:
    if debug: print(h,heights[con-1],i,con)
    flg=(flg and h>heights[con-1])
    watched.add(con)
  if debug: print(i,h,flg)
  if flg:
    if debug: res_m.add(i)
    res+=1
if debug: print(heights_w,cons,res_m)
print(res)

Submission status: Accepted

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

ans = [True for i in range(n)]

for x, y in zip(a, b):
    if h[x-1] < h[y-1]:
        ans[x-1] = False
    elif h[x-1] > h[y-1]:
        ans[y-1] = False
    elif h[x-1] == h[y-1]:
        ans[x-1] = False
        ans[y-1] = False

print(ans.count(True))

Submission status: Accepted

Solution code:
from collections import deque

def readlines(n):
    for _ in range(n):
        a, b = map(int, input().split())
        yield a-1, b-1

def main():
    n, m = map(int, input().split())
    H = list(map(int, input().split()))
    r = [True] * n
    for a, b in readlines(m):
        if H[a] < H[b]:
            r[a] = False
        elif H[b] < H[a]:
            r[b] = False
        else:
            r[a] = False
            r[b] = False

    print(r.count(True))


main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
S = [1 for i in range(N)]
SS = 0
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())
for i in range(M):
    if H[A[i]-1] < H[B[i]-1]:
        S[A[i]-1] = 0
    elif H[A[i]-1] > H[B[i]-1]:
        S[B[i]-1] = 0
    else:
        S[A[i]-1] = 0
        S[B[i]-1] = 0
for i in range(N):
    if S[i] == 1:
        SS += 1
print(SS)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
hs = list(map(int, input().split()))
counter = [True] * n

for _ in range(m):
  # abs += list(map(int, input().split()))
  a, b = map(int, input().split())
  a -= 1
  b -= 1
  if hs[a] < hs[b]:
    counter[a] = False
  elif hs[a] > hs[b]:
    counter[b] = False
  else:
    counter[a], counter[b] = False, False
print(sum(counter))

Submission status: Accepted

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

# # a = []
# # b = []

dic = {}
count = 0

for i in range(m):
    aa, bb = map(int,input().split())
    # a.append(aa)
    # b.append(bb)
    if aa not in dic:
        dic[aa] = set()
        dic[aa].add(bb)
    else:
        dic[aa].add(bb)

    if bb not in dic:
        dic[bb] = set()
        dic[bb].add(aa)
    else:
        dic[bb].add(aa)

for k in dic.keys():
    left = h[k-1]
    right = 0
    for i in dic[k]:
        if h[i-1] >= right:
            right = h[i-1]

    if left > right:
        count += 1

count += n - len(dic)

print(count)

Submission status: Accepted

Solution code:
raw_input = list(map(int, input().split()))
n = raw_input[0]
m = raw_input[1]
h = list(map(int, input().split()))
loads = {i+1: [] for i in range(n)}
for _ in range(m):
    raw_input = list(map(int, input().split()))
    a = raw_input[0]
    b = raw_input[1]
    loads[a].append(h[b-1])
    loads[b].append(h[a-1])
# print(loads)
counter = 0
for k, v in loads.items():
    if len(v) == 0:
        counter += 1
    elif max(v) < h[k-1]:
        counter += 1
print(counter)

Submission status: Accepted

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

for i in range(M):
    if H[AB[i][0]-1] == H[AB[i][1]-1]:
        Hi[AB[i][1]-1] = 0
        Hi[AB[i][0]-1] = 0
    elif H[AB[i][0]-1] > H[AB[i][1]-1]:#dictにするか？
        Hi[AB[i][1]-1] = 0
    elif H[AB[i][0]-1] < H[AB[i][1]-1]:
        Hi[AB[i][0]-1] = 0
print(sum(Hi))

Submission status: Accepted

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

G = [[] for i in range(N)]

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

ans = 0

for i in range(N):
    self_h = H[i]

    self_max_flag = True

    for to in G[i]:
        if (self_h <= H[to]):
            self_max_flag = False
        
    if (self_max_flag):
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys
import collections

mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000

d = collections.deque()
def LI(): return list(map(int, sys.stdin.readline().split()))

class UnionFind():
    # 作りたい要素数nで初期化
    # 使用するインスタンス変数の初期化
    def __init__(self, n):
        self.n = n
        # root[x]<0ならそのノードが根かつその値が木の要素数
        # rootノードでその木の要素数を記録する
        self.root = [-1]*(n+1)
        # 木をくっつける時にアンバランスにならないように調整する
        self.rnk = [0]*(n+1)

    # ノードxのrootノードを見つける
    def Find_Root(self, x):
        if(self.root[x] < 0):
            return x
        else:
            # ここで代入しておくことで、後の繰り返しを避ける
            self.root[x] = self.Find_Root(self.root[x])
            return self.root[x]
    # 木の併合、入力は併合したい各ノード
    def Unite(self, x, y):
        # 入力ノードのrootノードを見つける
        x = self.Find_Root(x)
        y = self.Find_Root(y)
        # すでに同じ木に属していた場合
        if(x == y):
            return 
        # 違う木に属していた場合rnkを見てくっつける方を決める
        elif(self.rnk[x] > self.rnk[y]):
            self.root[x] += self.root[y]
            self.root[y] = x

        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            # rnkが同じ（深さに差がない場合）は1増やす
            if(self.rnk[x] == self.rnk[y]):
                self.rnk[y] += 1
    # xとyが同じグループに属するか判断
    def isSameGroup(self, x, y):
        return self.Find_Root(x) == self.Find_Root(y)

    # ノードxが属する木のサイズを返す
    def Count(self, x):
        return -self.root[self.Find_Root(x)]

N, M = LI()
H = LI()
route = []
for i in range(M):
    a, b = LI()
    a -= 1
    b -= 1
    route.append((a,b))

N_path = [[] for i in range(N)]
for a, b in route:
    N_path[a].append(b)
    N_path[b].append(a)

# print(H)
ans = 0
for i in range(N):
    for path in N_path[i]:
        if H[path] >= H[i]:
            break
    else:
        ans += 1
print(ans)



# uf = UnionFind(N)
# for a, b in route:
#     uf.Unite(a, b)

# ans = 0
# good_obs = []
# for i in range(N):
#     print(good_obs)
#     if len(good_obs) == 0:
#         good_obs.append(i)
#     else:
#         for obs in good_obs:
#             print(obs, i)
#             if uf.isSameGroup(obs, i):
#                 if H[obs] == H[i]:
#                     good_obs.append(i)
#                     break
#                 elif H[obs] > H[i]:
#                     pass
#                 elif H[obs] < H[i]:
#                     good_obs.remove(obs)
#                     good_obs.append(i)
# print(good_obs)
# print(len(good_obs))

Submission status: Accepted

Solution code:
import math
import collections
#X=int(input())
N,M=map(int,input().split())
S=[[]for i in range(N)]
# for i in range(Q):
H=list(map(int,input().split()))
#     S[i]=a
# ans=0
# print()
ans=0
for i in range(M):
    A, B = map(int, input().split())
    S[A-1].append(H[B-1])
    S[B - 1].append(H[A - 1])
#print(S)
for i in range(N):
    if len(S[i])==0:
        ans+=1
        continue
    elif H[i]>max(S[i]):
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
n,m = map(int, input().split())
h = list(map(int,input().split()))
hbox = []
for i in h:
    a = [i]
    hbox.append(a)
for j in range(m):
    a,b = map(int, input().split())
    hbox[a-1].append(h[b-1])
    hbox[b-1].append(h[a-1])
ans = 0
for l in range(n):
    hbox[l] = sorted(hbox[l])
for k in range(n):
    if h[k] == hbox[k][-1] and not(hbox[k][-1] in set(hbox[k][:-1])):
        ans += 1
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from heapq import heappush
N, M = map(int, input().split())
H = list(map(int, input().split()))
x = [True] * N
for _ in range(M):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    if H[a] == H[b]:
        x[a] = False
        x[b] = False
    elif H[a] > H[b]:
        x[b] = False
    else:
        x[a] = False
ans = 0
for i in range(N):
    if x[i]:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
H = [int(x) for x in input().split()]
AB = [[int(x) for x in input().split()]for i in range(M)]
good = [-1]*N   
for j in range(M):
  if H[AB[j][0]-1] > H[AB[j][1]-1]:
    good[AB[j][0]-1] *= 1
    good[AB[j][1]-1] *= 0
  elif H[AB[j][0]-1] < H[AB[j][1]-1]:
    good[AB[j][0]-1] *= 0
    good[AB[j][1]-1] *= 1
  else:
    good[AB[j][0]-1] *= 0
    good[AB[j][1]-1] *= 0
print(good.count(-1)+good.count(1))

Submission status: Accepted

Solution code:
# Peaks
N, M = map(int, input().split())
H = list(map(int, input().split()))
Good = [True] * N

for _ in range(M):
    n1, n2 = map(int, input().split())

    n1 = n1 - 1
    n2 = n2 - 1

    if H[n1] == H[n2]:
        Good[n1] = False
        Good[n2] = False
    elif H[n1] < H[n2]:
        Good[n1] = False
    else:
        Good[n2] = False

print(Good.count(True))

Submission status: Accepted

Solution code:
N, M = map(int,input().split())
H = list(map(int, input().split()))
L = []
for i in range(M):
  L.append(list(map(int, input().split())))
  
H = [0] + H
A = [0] + [1] * N

for i in range(M):
  if H[L[i][0]] > H[L[i][1]]:
    A[L[i][1]] = 0
  elif H[L[i][0]] < H[L[i][1]]:
    A[L[i][0]] = 0
  else:
    A[L[i][0]] = 0
    A[L[i][1]] = 0
print(A.count(1))

Submission status: Accepted

Solution code:
if __name__=='__main__':
    n,m = map(int,input().split())
    h = [int(x) for x in input().split()]
    a = []
    b = []
    good_obs = [True for i in range(n)]
    for i in range(m):
        x,y = map(int,input().split())
        a.append(x)
        b.append(y)
        if h[x-1]<=h[y-1]:
            good_obs[x-1]=False
        if h[x-1]>=h[y-1]:
            good_obs[y-1]=False
    print(good_obs.count(True))

Submission status: Accepted

Solution code:
class Observatory:
    def __init__(self, height, around=[]):
        self.height = height
        x = []
        self.around = x
    def is_good(self, li, dic):
        flag = True
        for i in self.around:
            o = li[i-1]
            if o.height >= self.height:
                flag = False
            else:
                dic[i-1] = False
        return flag

n, m = map(int, input().split())
h = [int(i) for i in input().split()]
observatories = [Observatory(h[i]) for i in range(n)]
dic = {}
for i in range(n):
    dic[i] = True

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

for i in range(n):
    o = observatories[i]
    if dic[i]:
        if o.is_good(observatories, dic):
            ans += 1

print(ans)

Submission status: Accepted

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

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

paths = []
for i in range(M):
    paths.append(list(map(int, input().split())))
    paths[-1][0] -= 1
    paths[-1][1] -= 1
    
bad = set()

for path in paths:
  if H[path[0]] == H[path[1]]:
    bad.add(path[0])
    bad.add(path[1])
  elif H[path[0]] > H[path[1]]:
    bad.add(path[1])
  else:
    bad.add(path[0])
        
print(N-len(bad))

Submission status: Accepted

Solution code:
# coding=UTF-8
from collections import deque
from operator import itemgetter
from bisect import bisect_left, bisect
import itertools
import sys
import math
import numpy as np
import time
sys.setrecursionlimit(10**6)
input = sys.stdin.readline


def main():
    n, m = map(int, input().split())
    h = [int(x) for x in input().split()]
    tenbo = [[] for _ in range(n)]
    ans = 0
    for i in range(m):
        a, b = map(int, input().split())
        tenbo[a - 1].append(b)
        tenbo[b - 1].append(a)
    for i in range(n):
        flg = 0
        if len(tenbo[i]) == 0:
            ans += 1
            continue
        for j in tenbo[i]:
            if h[i] <= h[j-1]:
                flg = 1
                break
        if flg == 0:
            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()))
table = [[] for i in range(n)]
for i in range(m):
    a, b = map(int, input().split())
    table[a-1].append(b-1)
    table[b-1].append(a-1)
count = 0
for i in range(len(table)):
    for j in range(len(table[i])):
        if h[table[i][j]] >= h[i]:
            break
    else:
        count += 1
print(count)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
H = list(map(int, input().split()))
adj = [[] for _ in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    adj[a-1].append(H[b-1])
    adj[b-1].append(H[a-1])
cnt = 0
for idx in range(N):
    if len(adj[idx]) == 0:
        cnt += 1
    elif max(adj[idx]) < H[idx]:
        cnt += 1

print(cnt)

Submission status: Accepted

Solution code:

n,m= map(int, input().split())
h = list( map(int, input().split()))
ab = [map(int,input().split()) for i in range(m)]


# s = input()

# n,m,q = map(int, input().split())
# abcd = [map(int, input().split())for _ in range(q)]

# a = list(map(int, input().split()))
G = {}

for a,b in ab:
    if a-1 not in G:
        G[a-1]={b-1}
    else:
        G[a-1].add(b-1)
    if b-1 not in G:
        G[b-1]={a-1}
    else:
        G[b-1].add(a-1)
ans=0
for i in range(n):
    if i not in G:
        ans +=1
        continue
    visited = G[i]
  
    height = h[i]
    flag = True
    for j in visited:
        if j == i:
            continue
        else:
            if h[j] >= height:
                flag =False
                break
    if flag :
        ans +=1
print(ans)

Submission status: Accepted

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

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

cnt = 0
for i in range(n):
    if g[i] == []:
        mx = 0
    else:
        mx = max(g[i])
    if h[i] > mx:
        cnt += 1 

print(cnt)

Submission status: Accepted

Solution code:
from collections import defaultdict
import sys
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9 + 7
eps = 10**-7


def inp():
    return int(input())


def inpl():
    return list(map(int, input().split()))


N, M = inpl()
hh = inpl()

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

for _ in range(M):
    A, B = inpl()
    A -= 1
    B -= 1
    lines[A].append(B)
    lines[B].append(A)

ans = 0

for s in range(N):
    sh = hh[s]

    for t in lines[s]:
        th = hh[t]
        if sh > th:
            continue
        else:
            break
    else:
        ans += 1

print(ans)

Submission status: Accepted

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

l = H.copy()
for i 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
  elif H[A-1] == H[B-1]:
    l[A-1] = 0
    l[B-1] = 0
print(N - l.count(0))

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)]
goodt = [1] * n
for i in range(m):
  if h[ab[i][0]-1] < h[ab[i][1]-1]:
    goodt[ab[i][0]-1] = 0
  elif h[ab[i][0]-1] > h[ab[i][1]-1]:
    goodt[ab[i][1]-1] = 0
  else:
    goodt[ab[i][0]-1] = 0
    goodt[ab[i][1]-1] = 0

print(sum(goodt))

Submission status: Accepted

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

if __name__ == "__main__":
    N, M = MI()
    H = LI()
    roots = []
    for _ in range(M):
        roots.append(LI())
    result = [True] * N
    for root in roots:
        if H[root[0]-1] > H[root[1]-1]:
            result[root[1]-1] = False
        elif H[root[0]-1] < H[root[1]-1]:
            result[root[0]-1] = False
        else:
            result[root[0]-1] = False
            result[root[1]-1] = False
    print(result.count(True))

Submission status: Accepted

Solution code:
n, M = map(int, input().split())
H = map(int, input().split())
ranking = []
order = [0] * n
good = [1] * n

for num, h in enumerate(H):
    ranking.append((num, h))
ranking.sort(key=lambda x: x[1])
for num, tpl in enumerate(ranking):
    order[tpl[0]] = (num, tpl[1])
#print(ranking, order, good)
for m in range(M):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    if order[a][1] > order[b][1]:
        good[b] *= 0
    elif order[a][1] < order[b][1]:
        good[a] *= 0
    else:
        good[a] *= 0
        good[b] *= 0
#print(good)
print(sum(good))

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
h_list = list(map(int, input().split()))
route = {i:[] for i in range(1, n+1)}
for _ in range(m):
    a, b = map(int, input().split())
    route[a].append(b)
    route[b].append(a)  

ans = 0

for f, ts in  route.items():
    hi_flag = True
    for t in ts:
        if h_list[f-1] <= h_list[t-1]:
            hi_flag = False
            break
    if hi_flag:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
def q3():
    n, m = [int(i) for i in input().split(" ")]
    height_list = [int(i) for i in input().split(" ")]
    heights = {}
    for index, height in enumerate(height_list):
        heights[index + 1] = height
    # print(heights)

    roads = defaultdict(lambda: set())
    for i in range(m):
        a, b = [int(i) for i in input().split(" ")]
        roads[a].add(b)
        roads[b].add(a)
    # print(roads)

    good = set()
    bad = set()
    for start, dests in roads.items():
        # print("------")
        # print(start, dests, good, bad)
        # not in bad?
        if start in bad:
            continue
        start_is_good = True
        for obs in dests:
            if heights[start] <= heights[obs]:
                start_is_good = False
                break
        if start_is_good:
            good.add(start)
            bad |= dests
        else:
            bad.add(start)

    for i in range(1, n+1):
        if i not in bad:
            good.add(i)
    
    # print(good)
    # print(bad)

    print(len(good))

q3()

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
hyoko = list(map(int,input().split()))
road=[list(map(int,input().split())) for i in range(m)]
ans=[1]*n

for j in road:
    a, b = j
    if hyoko[a-1] > hyoko[b-1]:
        ans[b-1] = 0
    elif hyoko[a-1] == hyoko[b-1]:
        ans[a-1] = 0
        ans[b-1] = 0
    else:
        ans[a-1] = 0
print(sum(ans))

Submission status: Accepted

Solution code:
nm = input().split()
n = int(nm[0])
m = int(nm[1])
h = input().split()
r = [1] * len(h)
for i in range(m):
	ab = input().split()
	a = int(ab[0])
	b = int(ab[1])

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

cnt = 0

for i in r:
	if int(i) == 1:
		cnt += 1
# print(r)
print(cnt)

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
heightlist = list(map(int,input().split()))
#heightlistの[i]がi-1の展望台の高さ
rinsetulist = []
for _ in range(n):
    rinsetulist.append([])

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

count = 0
for i in range(n):
    if rinsetulist[i] == []:
        count += 1
    elif heightlist[i] > max(rinsetulist[i]):
        count += 1

print(count)

Submission status: Accepted

Solution code:
from collections import defaultdict as dd
N,M = map(int,input().split())
HH = list(map(int,input().split()))

make = set([])

hs_dic = dd(list)

for m in range(M):
    a,b = input().split()
    ah = HH[int(a)-1]
    bh = HH[int(b)-1]
    if ah > bh:
        make.add(b)
    elif ah < bh:
        make.add(a)
    
    hs_dic[a].append(b)
    hs_dic[b].append(a)

yoi = 0

keys = hs_dic.keys()
yoi += N - len(list(keys))

# print(yoi)

kkeys = set(keys) - make

# print(hs_dic.items())
# print(kkeys)

for kk in kkeys:
    bs = hs_dic[kk]
    ah = HH[int(kk)-1]
    ismax = 1
#     print("ah:",ah)
    for b in bs:
        bh = HH[int(b)-1]
#         print("---:",bh)
        if bh >= ah:
            ismax = 0
            break
    yoi += ismax
    
print(yoi)

Submission status: Accepted

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

for i in AB:
    D[i[0]].append(i[1])
    D[i[1]].append(i[0])

for i in range(1,N+1):
    hantei = 0
    fur = D[i]
    for j in fur:
        if H[i-1] <= H[j-1]:
            hantei = 1
            break
    if hantei == 0:
        #print(i)
        count += 1

print(count)

Submission status: Accepted

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

tmp = input().split()

H = [0]*N
Flag = [1]*N

for h in range(N):
    H[h] = int(tmp[h])

for i in range(M):
    tmp = input().split()
    A = int(tmp[0])-1
    B = int(tmp[1])-1
    if H[A] < H[B]:
        Flag[A] = 0
    if H[A] > H[B]:
        Flag[B] = 0
    if H[A] == H[B]:
        Flag[A] = 0
        Flag[B] = 0

print(sum(Flag))

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
h = list(map(int, input().split()))
peaks = {}
for i in range(n):
    peaks[i] = []
for j in range(m):
    a, b = map(int, input().split())
    peaks[a-1].append(b-1)
    peaks[b-1].append(a-1)
cnt = 0
for key, value in peaks.items():
    maxVal = 0
    for num in value:
        if h[num] > maxVal:
            maxVal = h[num]
        else:
            continue
    if h[key] > maxVal:
        cnt += 1
print(cnt)

Submission status: Accepted

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

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

Submission status: Accepted

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