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()))
AB=[set() for i in range(N)]
#例2を見ると、同じ展望台を結ぶ複数の道がある
for i in range(M):
  A,B=map(int,input().split())
  A-=1
  B-=1
  AB[A].add(B)
  AB[B].add(A)
ans=0
for i in range(N):
  res=True
  for x in AB[i]:
    if H[i]<=H[x]:#同じ高さの展望台は条件を満たさない
      res=False
      break
  if res:
    ans+=1#チェックした結果、OKの展望台だけ、答に加える
print(ans)

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
H=list(map(int,input().split()))
AB=[set() for i in range(N)]
for i in range(M):
  A,B=map(int,input().split())
  A-=1
  B-=1
  AB[A].add(B)
  AB[B].add(A)
ans=0
for i in range(N):
  res=True
  for x in AB[i]:
    if H[i]<=H[x]:      
      res=False
      break
  if res:
    ans+=1
print(ans)

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
H=list(map(int,input().split()))
AB=[[] for i in range(N)]
for i in range(M):
  A,B=map(int,input().split())
  A-=1
  B-=1
  AB[A].append(B)
  AB[B].append(A)
ans=0
for i in range(N):
  res=True
  for x in AB[i]:
    if H[i]<=H[x]:      
      res=False
      break
  if res:
    ans+=1
print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

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

# 一つづつ展望台を見る必要はなく、道を見て条件に合わないものを除けば良い
ans_list = [True] * n
for i in range(m):
    if h[ab[i][0]] >= h[ab[i][1]]:
        ans_list[ab[i][1]] = False
    if h[ab[i][0]] <= h[ab[i][1]]:
        ans_list[ab[i][0]] = False
print(sum(ans_list))

Submission status: Accepted

Solution code:
n, m = list(map(int, input().split()))
heights = list(map(int, input().split()))
flags = [True] * n
count = 0
for _ in range(m):
  roots = list(map(int, input().split()))
  if heights[roots[0] - 1] > heights[roots[1] - 1]:
    flags[roots[1] - 1] = False
  elif heights[roots[0] - 1] < heights[roots[1] - 1]:
    flags[roots[0] - 1] = False
  else:
    flags[roots[1] - 1] = False
    flags[roots[0] - 1] = False
for flag in flags:
  if flag:
    count += 1
print(count)

Submission status: Accepted

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

Submission status: Accepted

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

good = [1 for i in range(N)]

for road in roads:
  if heights[road[0]-1] > heights[road[1]-1]:
    good[road[1]-1] = 0
  elif heights[road[0]-1] < heights[road[1]-1]:
    good[road[0]-1] = 0
  else:
    good[road[0]-1] = 0
    good[road[1]-1] = 0

print(sum(good))

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
H=list(map(int,input().split()))
ab=[0]*N
for i in range(M):
    a,b=map(int,input().split())
    ab[a-1]=max(ab[a-1],H[b-1])
    ab[b-1]=max(ab[b-1],H[a-1])
ans=0
for i in range(N):
    if ab[i]<H[i]:
        ans+=1
print(ans)

Submission status: Accepted

Solution code:
import copy
n, m =map(int, input().split())  #複数数値入力
list_h=list(map(int, input().split()))  #リスト入力
# 繰り返しリスト入力
a = []
for i in range(m):
    ai = list(map(int, input().split()))  #リスト入力
    a.append(ai)

for i in a:
    i.sort()
a = list(map(list, set(map(tuple, a))))

booler = [True] * n
for j in a:
    if list_h[j[0]-1] < list_h[j[1]-1]:
        booler[j[0]-1] = False
    elif list_h[j[0]-1] > list_h[j[1]-1]:
        booler[j[1]-1] = False
    else :
        booler[j[0]-1] = False
        booler[j[1]-1] = False
print(booler.count(True))

Submission status: Accepted

Solution code:
n, m =map(int,input().split())
s = list(map(int,input().split()))
t = [0]*n #展望台が良いと0
for __ in range(m):
  a, b =map(int,input().split())
  if s[a-1] >= s[b-1]:
    t[b-1] += 1
  if s[a-1] <= s[b-1]:
    t[a-1] += 1
print(t.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 _ in range(m)]
#print(h)
#print(ab)

l = [1 for _ in range(n)]
for i in ab:
  if h[i[0]-1] > h[i[1]-1]:
    l[i[1]-1] = 0
  elif h[i[1]-1] > h[i[0]-1]:
    l[i[0]-1] = 0
  else:
    l[i[1]-1] = 0
    l[i[0]-1] = 0

print(sum(l))

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
ans= 0
hs = list(map(int, input().split()))
ds = {}
ok = True
for i in range(m):
    a,b = map(int, input().split())
    if(a in ds):
        ds[a].append(b)
    if(b in ds):
        ds[b].append(a)
    if(a not in ds):
        ds[a] = [b]
    if(b not in ds):
        ds[b] = [a]
for i in range(1, n+1):
    if(i not in ds):
        ans +=1
    else:
        for l in ds[i]:
            if(hs[i-1] <= hs[l-1]):
                ok = False
        if(ok):
            ans +=1
        ok = True
print(ans)

Submission status: Accepted

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

for i in range(m):
    x1, y1 = [int(i) for i in input().split()]
    ab[x1-1].append(y1-1)
    ab[y1-1].append(x1-1)

ans = 0

for i in range(n):
    ok = 1
    for j in range(len(ab[i])):
        #print(i)
        if h[i] >h[ab[i][j]]:
            continue
        else:
            ok = 0
            break

    if ok == 1:
        #print(i)
        ans += 1

print(ans)

Submission status: Accepted

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

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

Submission status: Accepted

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

def main():
    N, M = map(int, input().split())
    H = list(map(int, input().split()))
    good = [True] * N
    for i in range(M):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        if H[a] > H[b]:
            good[b] = False
        elif H[b] > H[a]:
            good[a] = False
        else:
            good[a] = False
            good[b] = False
    # print(good)
    ans = 0
    for i in range(N):
        if good[i]:
            ans += 1
    print(ans)



if __name__ == "__main__":
    main()

Submission status: Accepted

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

ab = [0]*n
for i in range(m):
  a,b = map(int, input().split())
  ab[a-1] = max(ab[a-1], h[b-1])
  ab[b-1] = max(ab[b-1], h[a-1])

ans = 0
for i in range(n):
  if ab[i] < h[i]:
    ans += 1
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#inport
import sys
import numpy as np
from collections import deque


#input
N,M = [int(x) for x in sys.stdin.readline().split()]
h = [int(x) for x in sys.stdin.readline().split()]

hills = np.ones(N)

for _ in range(M):
    a, b = [int(x) for x in sys.stdin.readline().split()]
    if h[a-1] > h[b-1] :
        hills[b-1] = 0
    elif h[b-1] > h[a-1]:
        hills[a-1] = 0
    else:
        hills[a-1] = 0
        hills[b-1] = 0

print(int(np.sum(hills)))

Submission status: Accepted

Solution code:
def main():
    n, m = map(int, input().split())
    h = list(map(int, input().split()))
    to = [0]*n
    ans = 0
    for i in range(m):
        a, b = map(int, input().split())
        a, b = a-1, b-1
        to[a] = max(to[a], h[b])
        to[b] = max(to[b], h[a])
    for i, hi in enumerate(h):
        if hi > to[i]:
            ans += 1
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

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

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

ab = [map(int, input().split()) for _ in range(m)]
a, b = [list(i) for i in zip(*ab)]

#print(a)

ans=[0]*n
cot=0
t=0
s=0
for i in range(m):
    t=a[i]
    s=b[i]
    if h[t-1]>h[s-1]:
        ans[s-1]=1
    elif h[t-1]<h[s-1]:
        ans[t-1]=1
    else :
        ans[s-1]=1
        ans[t-1]=1
for e in range(n):
    if ans[e]==0:
        cot+=1
#print(ans)
print(cot)

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)]

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

ans = 0
for idx, e_list in enumerate(edges):
    bl = True
    if len(e_list) != 0:
        for e in e_list:
            if H[idx] <= H[e]:
                bl = False
    if bl:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
import glob

# 問題ごとのディレクトリのトップからの相対パス
REL_PATH = 'ABC\\166\\C'

# テスト用ファイル置き場のトップ
TOP_PATH = 'C:\\AtCoder'

class Common:

    problem = []
    index = 0

    def __init__(self, rel_path):
        self.rel_path = rel_path

    def initialize(self, path):
        file = open(path)
        self.problem = file.readlines()
        self.index = 0
        return

    def input_data(self):
        try:
            IS_TEST
            self.index += 1
            return self.problem[self.index-1]

        except NameError:
            return input()

    def resolve(self):
        pass

    def exec_resolve(self):
        try:
            IS_TEST
            for path in glob.glob(TOP_PATH + '\\' + self.rel_path + '/*.txt'):
                print("Test: " + path)
                self.initialize(path)
                self.resolve()
                print("\n\n")
        except NameError:
            self.resolve()


class C(Common):

    def resolve(self):

        N, M = map(int, self.input_data().split())
        H = list(map(int, self.input_data().split()))
        H.insert(0,0)
        node = [None]*M
        for i in range(M):
            node[i] = list(map(int, self.input_data().split()))

        node_list = [[] for i in range(N+1)]

        for n in node:
            node_list[n[0]].append(n[1])
            node_list[n[1]].append(n[0])

        count = 0
        for i in range(1,N+1):
            for j in node_list[i]:
                if H[i] <= H[j]:
                    break
            else:
                count += 1

        print(str(count))

solver = C(REL_PATH)
solver.exec_resolve()

Submission status: Accepted

Solution code:
N,M = (int(x) for x in input().split())
H   = [int(x) for x in input().split()]
Way = [[] for I in range(N)]
for T in range(0,M):
    A,B = (int(x) for x in input().split())
    Way[A-1].append(B)
    Way[B-1].append(A)
    
Count = 0
for TT in range(0,N): 
    if all(H[TT]>Ele for Ele in [H[I-1] for I in Way[TT]]):
        Count = Count+1
print(Count)

Submission status: Accepted

Solution code:
from collections import defaultdict
d = defaultdict(list)
n, m = map(int, input().split())
h = list(map(int, input().split()))

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

ans = 0
for k, v in d.items():
  h_a = h[k - 1]
  k = 1
  for e in v:
    h_b = h[e - 1]
    if h_a > h_b:
      next
    else:
      k = 0
      break
  ans += k
ans += n - len(d)
print(ans)

Submission status: Accepted

Solution code:
import sys
def main():
    N,M=tuple(map(int,sys.stdin.readline().split()))
    H=list(map(int,sys.stdin.readline().split()))
    E=[[] for _ in [0]*N]
    for _ in [0]*M:
        a,b=tuple(map(lambda x:int(x)-1,sys.stdin.readline().split()))
        E[a].append((b,(H[b]-H[a])))
        E[b].append((a,(H[a]-H[b])))
    res=0
    for e in E:
        if len(e)==0:res+=1
        else:
            if all(list(map(lambda x:x[1]<0,e))):res+=1
    print(res)
if __name__=='__main__':main()

Submission status: Accepted

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

def ppp(n,m,h,ab):
    g = [1] * n
    for l,r in ab:
        if h[l-1] >= h[r-1]:
            g[r-1] = 0
        if h[l-1] <= h[r-1]:
            g[l-1] = 0
    print(sum(g))
if __name__ == "__main__":
    n,m = map(int,input().split())
    h = list(map(int,input().split()))
    ab = [list(map(int,input().split())) for _ in range(m)]
    ppp(n,m,h,ab)

Submission status: Accepted

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

def ppp(n,m,h,ab):
    g = [1] * n
    for l,r in ab:
        if h[l-1] >= h[r-1]:
            g[r-1] = 0
        if h[l-1] <= h[r-1]:
            g[l-1] = 0
    print(sum(g))
if __name__ == "__main__":
    n,m = map(int,input().split())
    h = list(map(int,input().split()))
    ab = [list(map(int,input().split())) for _ in range(m)]
    ab_sorted = sorted(ab)
    ppp(n,m,h,ab_sorted)

Submission status: Accepted

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

def peaks(n,m,h,ab):
    g = [0] * n
    path = [ [] for i in range(n)]
    #print(ab)
    for l,r in ab:
        path[l-1].append(r)
        path[r-1].append(l)

    #print(path)

    for i,p in enumerate(path):
        if p == []:
            g[i] = 1
            continue
        
        for j in p:
            #print(i+1,j,h[i],h[j-1])
            if h[i] > h[j-1]:
                g[i] = 1
            else:
                g[i] = 0
                break
    print(sum(g))

if __name__ == "__main__":
    n,m = map(int,input().split())
    h = list(map(int,input().split()))
    ab = [list(map(int,input().split())) for _ in range(m)]
    ab_sorted = sorted(ab)
    peaks(n,m,h,ab_sorted)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
h_list = [[int(h), []] for h in input().split()]
for i in range(m):
    a, b = map(int, input().split())
    h_list[a - 1][1].append(b - 1)
    h_list[b - 1][1].append(a - 1)
ans = 0
for h in h_list:
    if all([h[0] > h_list[h_][0] for h_ in h[1]]):
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
def main():
    n, m = map(int, input().split())
    h = list(map(int, input().split()))
    to = [0]*(n+1)
    ans = 0
    for _ in range(m):
        a, b = map(int, input().split())
        to[a] = max(to[a], h[b-1])
        to[b] = max(to[b], h[a-1])
    for i, hi in enumerate(h, 1):
        if hi > to[i]:
            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()))
p = [1]*n
max = 0
for i in range(m):
    a, b = map(int, (input().split()))
    if h[a-1] <= h[b-1]:
        p[a-1] = 0
    if h[a-1] >= h[b-1]:
        p[b-1] = 0
print(sum(p))

Submission status: Accepted

Solution code:
def main():
    n, m = map(int, input().split())
    h = list(map(int, input().split()))
    to = [0]*(n+1)
    ans = 0
    for _ in range(m):
        a, b = map(int, input().split())
        to[a] = max(to[a], h[b-1])
        to[b] = max(to[b], h[a-1])
    for i, hi in enumerate(h, 1):
        t = to[i]
        if t == 0 or hi > t:
            ans += 1
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import copy

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

#print("p = {}".format(p))

height = copy.copy(h)
for i in p:
    index0 = i[0]
    index1 = i[1]
    if h[index0] < h[index1]:
        height[index0] = -1
    elif h[index0] > h[index1]:
        height[index1] = -1
    elif h[index0] == h[index1]:
        height[index0] = -1
        height[index1] = -1

#print("height = {}".format(height))

ret = 0
for i in range(n):
    if height[i] == h[i]:
        ret += 1

print("{}".format(ret))

Submission status: Accepted

Solution code:
n,m=map(int, input().split(" "))
tower=list(map(int, input().split(" ")))
road=[list(map(int, input().split(" "))) for i in range(m)]
kosuu = [0 for i in range(n)]
temp = [0 for i in range(n)]
ans=0
for i in range(m):
  kosuu[road[i][0] - 1] += 1
  kosuu[road[i][1] - 1] += 1
for i in range(m):
  if tower[road[i][0] - 1] > tower[road[i][1] - 1]:
    temp[road[i][0] - 1] += 1
  elif tower[road[i][0] - 1] < tower[road[i][1] - 1]:
    temp[road[i][1] - 1] += 1
count = 0
for i in range(n):
  #print(n)
  if kosuu[i] == temp[i]:
    count += 1
print(count)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
tenbo_height = list(map(int, input().split()))
adj_height = [0]*N

for i in range(M):
  #road[0] = start, road[1] = goal
  road = list(map(int, input().split()))
  adj_height[road[0]-1] = max(adj_height[road[0]-1], tenbo_height[road[1]-1])
  adj_height[road[1]-1] = max(adj_height[road[1]-1], tenbo_height[road[0]-1])
  
good_tenbo = 0
for tenbo in range(N):
  if ((tenbo_height[tenbo] > adj_height[tenbo])) or (adj_height[tenbo] == 0):
    good_tenbo += 1
print(good_tenbo)

Submission status: Accepted

Solution code:
n,m=[int(x) for x in input().split()]
h=[int(x) for x in input().split()]
road=[[]*1 for i in range(n)]
for i in range(m):
  a=[int(x) for x in input().split()]
  road[a[0]-1].append(a[1]-1)
  road[a[1]-1].append(a[0]-1)
good=[]
for i in range(n):
  if road[i]==[]:
    good.append(i)
  else:
    check=[]
    for j in road[i]:
      if h[i]<=h[j]:
        check.append(False)
    if check==[]:
      good.append(i)
print(len(good))

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 = list(map(int, readline().split()))

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

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 = list(map(int, readline().split()))
ab = [list(map(int, input().split())) for _ in range(m)]
l = [1]*n
for i in range(m):
    if h[ab[i][0] - 1] < h[ab[i][1] - 1]:
        l[ab[i][0] - 1] = 0
    elif h[ab[i][0] - 1] > h[ab[i][1] - 1]:
        l[ab[i][1] - 1] = 0
    else:
        l[ab[i][0] - 1] = 0
        l[ab[i][1] - 1] = 0
print(sum(l))

Submission status: Accepted

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

#memo:解説の解法と見比べる

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)]

top = [1]*n
for i in range(m):
    if h[ab[i][0]-1] < h[ab[i][1]-1]:
        top[ab[i][0]-1] = 0
    elif h[ab[i][0]-1] > h[ab[i][1]-1]:
        top[ab[i][1]-1] = 0
    else:
        top[ab[i][0]-1] = 0
        top[ab[i][1]-1] = 0

print(sum(top))

Submission status: Accepted

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

H=[0]                           #各丘の高さ(index1は文中の1)
for h in hs:
    H.append(int(h))


P=[[0]*1 for i in range(N+1)]   #各丘からの道 二次元配列 (index1は文中の1)
count=0
for p in range(len(P)):
    P[p][0]=p                   #P[][0] 各配列の要素1は自身の丘の数字
# print(P)

for m in range(M):
    pathfrom,pathto= map (int,input().split())
    P[pathfrom].append(H[pathto])
    P[pathto].append(H[pathfrom])
for i in range(1,len(P)):
    if len(P[i])==1:
        count+=1
    else:
        P[i][0]=H[i]
        _rP=P[i][1:]
        if P[i][0]>max(_rP):
            count+=1
print(count)

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
H = list(map(int,input().split()))
H.insert(0,0)
AB =  [list(map(int,input().split(" "))) for _ in range(M)]
links = [[] for _ in range(N+1)]

for a,b in AB:
  links[a].append(b)
  links[b].append(a)

res = [True] * (N+1)
res[0] = False

for i in range(1,N+1):
  for j in links[i]:
    if H[i] <= H[j]:
      res[i] = False

ans = res.count(True)
print(ans)

Submission status: Accepted

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

cnt = 0
for i in range(1, n+1):
    for j in g[i]:
        if h[j-1] >= h[i-1]:
            break
    else:
        cnt += 1

print(cnt)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N, M = [int(i) for i in input().split(' ')]
H = [-1]
H.extend([int(i) for i in input().split(' ')])

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

for _ in range(1, M + 1):
    A, B = [int(i) for i in input().split(' ')]
    links[A].add(H[B])
    links[B].add(H[A])

count = 0
for i in range(1, N + 1):
    if len(links[i]) == 0:
        count += 1
        continue
    if H[i] > max(links[i]):
        count += 1

print(count)

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:

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

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

S = [True]*N

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

print(sum(S))

Submission status: Accepted

Solution code:

def main():
    N, M = map(int,input().split(' '))
    H = list(map(int,input().split(' ')))
    H.insert(0, 0)
    ma = [0]*(N+1)

    for _ in range(M):
        A, B = map(int,input().split(' '))
        ma[A]=max(ma[A],H[B])
        ma[B]=max(ma[B],H[A])

    ans = 0
    for i in range(1,N+1):
        if H[i] > ma[i]:
            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()))
ans = [0]*N
for _ in range(M):
    A, B = map(int,input().split())
    if H[A-1] >= H[B-1]:
        ans[B-1] = 1
    if H[A-1] <= H[B-1]:
        ans[A-1] = 1
print(ans.count(0))

Submission status: Accepted

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

for v in range(1, n+1):
  for u in g[v]:
    if arr[u]>=arr[v]:
      break
  else:
    ans+=1
    
print(ans)

Submission status: Accepted

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

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

cnt=0
for i in range(N):
    f=True
    for g in G[i]:
        if H[i]<=H[g]:
            f=False
            break
    if f:
        cnt+=1

print(cnt)

Submission status: Accepted

Solution code:
N,X=map(int,input().split())
L=list(map(int,input().split()))

#S = [[0 for j in range(3)] for i in range(2)]　2行3列の場合
S = [[0 for j in range(1)] for i in range(N)]
for i in range(N):
    S[i][0]=L[i]
for i in range(X):
    A,B=map(int,input().split())
    A-=1
    B-=1
    S[A].append(L[B])
    S[B].append(L[A])

count=0

for i in range(N):
    nagasa=len(S[i])
    max_H=0
    if nagasa==1:
        count+=1
    else:
        for j in range(nagasa):
            if j!=0:
                if max_H<S[i][j]:
                    max_H=S[i][j]
        if S[i][0]>max_H:
            count+=1
    
print(count)

Submission status: Accepted

Solution code:
N,M = list(map(int,input().split()))
H =list(map(int,input().split()))
a =[0]*M
b =[0]*M
key = [-1]*N
count =0
for i in range(M):
	a[i],b[i]= list(map(int,input().split()))
path=[0][0]*(N)
for i in range(M):

	if H[a[i]-1]>=H[b[i]-1]:
		key[b[i]-1] = 1
	if H[b[i]-1]>=H[a[i]-1]:
		key[a[i]-1] =1


for i in range(N):
	if key[i]==-1:
		count +=1
print(count)

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
A = [0] + list(map(int,input().split()))
B = [ [] for _ in range(n + 1) ]
for _ in range(m):
    s,e = map(int,input().split())
    B[s].append(A[e])
    B[e].append(A[s])
ans = 0
for i in range(1,n+1):
    if len(B[i]) == 0:
        ans += 1
    elif max(B[i]) < A[i]:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
import collections

N, M = map(int,input().split())
Hl = list(map(int,input().split()))
l0 = [1]*N

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

count = 0
for value in l0:
    count += value

print(count)

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
H = [0]*N
H_top = [1]*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]:
        H_top[B-1] = 0
    if H[A-1] <= H[B-1]:
        H_top[A-1] = 0
print(sum(H_top))

Submission status: Accepted

Solution code:
n, m = (int(i) for i in input().split())
h = [int(i) for i in input().split()]
ab = [[int(i) for i in input().split()] for i in range(m)]
ma = []
for i in range(n):
    ma.append(0)
for i in range(m):
    a = ab[i][0]
    b = ab[i][1]
    ma[a-1] = max(ma[a-1],h[b-1])
    ma[b-1] = max(ma[b-1],h[a-1])
ans = 0
for i in range(n):
    ans += (h[i]>ma[i])
print(ans)

Submission status: Accepted

Solution code:
# ABC 166 C

N,M =map(int,input().split())
H= [int(j) for j in input().split()]
AB = []
for _ in range(M):
    a,b = map(int,input().split())
    AB.append([a,b])
    AB.append([b,a])
AB.sort(key=lambda s:s[0])
cnt =0
last_a = AB[0][0]
a_cnt = [0] *N
h_cnt = [0] *N
for a,b in AB:
    a-=1
    b-=1
    a_cnt[a] =a_cnt[a]+1
    if H[a] >H[b]:
        h_cnt[a]=h_cnt[a]+1
    
for i,a in enumerate(a_cnt):
    if h_cnt[i]==a:
        cnt+=1
print(cnt)

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
high = list(map(int,input().split()))
num = []
for i in range(m):
  mountain = list(map(int,input().split()))
  if high[mountain[0] - 1] < high[mountain[1] - 1]:
    num.append(mountain[0])
  elif high[mountain[0] - 1] == high[mountain[1] - 1]:
    num.append(mountain[0])
    num.append(mountain[1])
  else:
    num.append(mountain[1])
ans = [0]*n
for i in num:
  ans[i -1] = 1
cnt = 0
for i in ans:
  if i == 0:
    cnt += 1
print(cnt)

Submission status: Accepted

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

Submission status: Accepted

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

for i in range(M):
  a,b = list(map(int, input().split()))
  a,b = a-1, b-1
  E[a].append(b)
  E[b].append(a)
  
ans = 0

for i in range(N):
  flg = True
  for p in E[i]:
    if H[i] > H[p]:
      continue
    else:
      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()))

t = [0]*N
for i in range(M):
   a, b = map(int, input().split())
   t[a-1] = max(t[a-1], H[b-1])
   t[b-1] = max(t[b-1], H[a-1])

res = 0
for i in range(N):
    if H[i] > t[i]:
        res += 1

print(res)

Submission status: Accepted

Solution code:
N, M = list(map(int, input().split()))
tenbodai = [H for H in list(map(int, input().split()))]
tenbodai_trail = [set() for i in range(len(tenbodai))]
 
for _ in range(M): #展望台と繋がる道のリストを作成
    trail = list(map(int, input().split()))
    tenbodai_trail[trail[0] - 1].add(trail[1] - 1)
    tenbodai_trail[trail[1] - 1].add(trail[0] - 1)
    
count = 0
for i in range(len(tenbodai)): #全探索
    flag = True
    for trail in tenbodai_trail[i]: # i:現在の展望台の番号, trail:繋がる展望台の番号
        if tenbodai[i] <= tenbodai[trail]:
            flag = False
            break
    if flag:
        count += 1
print(count)