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:
## parse input
N, M = map(int, input().split()) # throw N away
Hs = list(map(int, input().split())) # int[N]
Rs = [] # (int, int)[M]

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

## preperation
#height_conds = [False]*N*N # boolean[N, N] if Hs[fst] > Hs[snd]
#for i in range(N):
#  for j in range(i+1, N):
#    height_conds[i*N+j] = Hs[i] > Hs[j]
#    height_conds[j*N+i] = Hs[j] > Hs[i]

## main
goods = [True] * N

for r in Rs:
  a, b = r
  if goods[a]:
  	goods[a] = Hs[a]>Hs[b]#height_conds[a*N+b]
  if goods[b]:
  	goods[b] = Hs[b]>Hs[a]#height_conds[b*N+a]

counter = 0
for i in range(N):
  if goods[i]:
    counter += 1

print(counter)

Submission status: Accepted

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

ans = {}

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

    if h[a - 1] > h[b - 1]:
        ans[b - 1] = False
    elif h[a - 1] < h[b - 1]:
        ans[a - 1] = False
    else:
        ans[a - 1] = False
        ans[b - 1] = False

print(N - len(ans))

Submission status: Accepted

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

count = 0
for i in range(N):
    if H_val[i] != 0:
        count+= 1

print(count)

Submission status: Accepted

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

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

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

count = 0
for i in range(n):
    if h[i] > ma[i]:
        count+=1
print(count)

Submission status: Accepted

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

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

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

print(sum(x))

Submission status: Accepted

Solution code:
import numpy as np
import copy

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

    for itr in range(M):
        A, B = list(map(int, input().split()))
        if H[A- 1] == H[B- 1] :
            maxH[A- 1] = copy.copy(H[A- 1]) + 1
            maxH[B- 1] = copy.copy(H[A- 1]) + 1
        elif H[A- 1] > H[B- 1] :
            if maxH[A- 1] < H[A- 1] :
                maxH[A- 1] = copy.copy(H[A- 1])
            if maxH[B- 1] < H[A- 1] :
                maxH[B- 1] = copy.copy(H[A- 1])
        elif H[A- 1] < H[B- 1] :
            if maxH[A- 1] < H[B- 1] :
                maxH[A- 1] = copy.copy(H[B- 1])
            if maxH[B- 1] < H[B- 1] :
                maxH[B- 1] = copy.copy(H[B- 1])
    
    result = 0
    for itr in range(N):
        if H[itr] == maxH[itr] or maxH[itr] == 0:
            result += 1
    #print(maxH)
    print(result)

if __name__ == "__main__":
    main()

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
NM=list(map(int,input().split()))
H=list(map(int,input().split()))
A=[0 for i in range(NM[0])]
for i in range(NM[1]):
    ab=list(map(int,input().split()))
    A[ab[0]-1]=max(A[ab[0]-1],H[ab[1]-1])
    A[ab[1]-1]=max(A[ab[1]-1],H[ab[0]-1])
d=0
for i in range(NM[0]):
    if(H[i]>A[i]):
        d+=1
print(d)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
H = [int(n) for n in input().split()]

cur = [0]*N
chk = [0]*N
ans = 0

for i in range(M):
    a, b = [int(n)-1 for n in input().split()]
    if H[a] > H[b]:
        cur[a] += 1
    elif H[a] < H[b]:
        cur[b] += 1

    chk[a] += 1
    chk[b] += 1

for i in range(N):
    if cur[i] == chk[i]:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
H = list(map(int, input().split()))
good = set(range(N))
for _ in range(M):
    a, b = [int(x) - 1 for x in input().split()]
    if H[a] < H[b]:
        good -= {a}
    elif H[b] < H[a]:
        good -= {b}
    if H[a] == H[b]:
        good -= {a, b}
print(len(good))

Submission status: Accepted

Solution code:
import sys
l = sys.stdin.readline().strip()
N, M = map(int, l.split())
impossible = set()

l = sys.stdin.readline().strip()
heights = [-1] + list(map(int, l.split()))

for i in range(M):
    l = sys.stdin.readline().strip()
    A, B = map(int, l.split())
    if A==B:
        continue
    if heights[A] == heights[B]:
        impossible.add(A)
        impossible.add(B)
    elif heights[A] < heights[B]:
        impossible.add(A)
    else:
        impossible.add(B)

print (N - len(impossible))

Submission status: Accepted

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

ans={}
for i in range(M):
    a,b=map(int,input().split())
    if hl[a-1]<=hl[b-1]:
        ans[a]=False
    if hl[a-1]>=hl[b-1]:
        ans[b]=False
    #print(ans)

print(N-len(ans))

Submission status: Accepted

Solution code:
#k=int(input())
n,m=map(int,input().split())
hl=list(map(int,input().split()))
#l=[list(map(int,input().split())) for i in range(n)]
dic={}
for i in range(m):
    a,b=map(int,input().split())
    if hl[a-1] <= hl[b-1]:
        dic[a]=False
    if hl[b-1] <= hl[a-1]:
        dic[b]=False

print(n-len(dic))

Submission status: Accepted

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

cnt = 0
for i in range(n):
    if all(h[i] > h[j] for j in G[i]):
        cnt += 1
print(cnt)

Submission status: Accepted

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

h=list(map(int,input().split()))
G=[[] for i in range(n)]
for _ in range(m):
 x,y=map(int,input().split())
 x=x-1
 y=y-1
 G[x].append(y)
 G[y].append(x)

ans=0

for i in range(n):
 
 for j in G[i]:
  if h[j]>=h[i]:
   break
 else:
  ans=ans+1
print(ans)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
mp = {}
arr= [ int(o) for o in input().split()]
for i in range (n):
    mp[i+1]=arr[i]
s = set()
# print(mp)
while m>0:
    a,b=map(int,input().split())
    if(mp[a]<mp[b]):
        s.add(a)
    elif(mp[b]<mp[a]):
        s.add(b)
    else:
        s.add(a)
        s.add(b)
    m-=1
print(n-len(s))

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
a=[0]
a= a + list(map(int,input().split()))
v=[[] for i in range(n+1)]
for t in range(m):
	x,y=map(int,input().split())
	v[x].append(y)
	v[y].append(x)
ans=0
for i in range(1,n+1):
	c=1
	for j in v[i]:
		if a[j]>=a[i]:
			c=0
	if c:
		ans+=1
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict


n, m = map(int, input().split())
*h, = map(int, input().split())
d = defaultdict(list)
for i in range(m):
    a, b = map(int, input().split())
    d[a - 1].append(b - 1)
    d[b - 1].append(a - 1)
# print(d)
ans = 0

for i in range(n):
    is_good = True
    for lighthouse in d[i]:
        # print(f"{i}: {h[i]} vs. {lighthouse}: {h[lighthouse]}")
        if h[i] > h[lighthouse]:
            continue
        is_good = False
        # print(f"{i} is not good.")
        break

    if is_good:
        # print(f"{i} is good.")
        ans += 1

print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import copy
n,m = map(int,input().split())
ht = [x for x in input().split()]
hl = {x + 1 : int(ht[x]) for x in range(len(ht))}
mx = {h:0 for h in hl}
for i in range(m):
    l,r = map(int,input().split())
    mx[l] = max(mx[l],hl[r])
    mx[r] = max(mx[r],hl[l])
cnt = 0
for h in hl:
    if mx[h] < hl[h]:
        cnt += 1
print(cnt)

Submission status: Accepted

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

h = [int(s) for s in input().split()]


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

for i in range(m):
    ar = [int(s) for s in input().split()]
    gr[ar[0]-1].append(ar[1])
    gr[ar[1]-1].append(ar[0])
    
#print(h)
#print(gr)
ans = n

for i in range(n):
    ar = gr[i]
    mx = h[i]
    for j in ar:
        if(h[j-1] >= mx):
            ans -= 1
            break

print(ans)

Submission status: Accepted

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

kotae=[True]*N

for j in range(M):
  A, B = list(map(int, input().split()))
  if H[A-1] > H[B-1]:
    kotae[B-1]=False
  if H[A-1] < H[B-1]:
    kotae[A-1]=False
  if H[A-1] == H[B-1]:
    kotae[B-1]=False
    kotae[A-1]=False
ans = 0

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

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
h = list(map(int,input().split()))
x = [list(map(int,input().split())) for nesya in range(m)]
k = [1]*n
for route in x:
  h1 = route[0]-1
  h2 = route[1]-1
  if h[h1] < h[h2]:
    k[h1] = 0
  elif h[h1] > h[h2]:
    k[h2] = 0
  else:
    k[h1] = 0
    k[h2] = 0
print(sum(k))

Submission status: Accepted

Solution code:
N, M = (int(x) for x in input().split())
H = [int(x) for x in input().split()]

high = set()
low = set()
lonely = set()

for i in range(M):
	i1, i2 = [int(x) for x in input().split()]
	if H[i1 - 1] > H[i2 - 1]:
		high.add(i1)
		low.add(i2)
	elif H[i1 - 1] < H[i2 - 1]:
		high.add(i2)
		low.add(i1)
	else:
		low.add(i1)
		low.add(i2)
	lonely.add(i1)
	lonely.add(i2)

result = len((high - low)) + (N  - len(lonely))
print(result)

Submission status: Accepted

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

H_t = input().split()
H = [int(s) for s in H_t]
#print(H)

ma = [0]*N

good_count = 0

#print(H_M)

for j in range(M):
    a, b = map(int, input().split())
    
    ma[a-1] = max(ma[a-1], H[b-1]) # つながった展望台の中で一番高い展望台を保持する
    ma[b-1] = max(ma[b-1], H[a-1]) 
    
    
for i in range(N):
    if H[i] > ma[i]:
        good_count +=1
print(good_count)

Submission status: Accepted

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


def main():
    n, m = map(int, readline().rstrip().split())
    hList = list(map(int, readline().rstrip().split()))
    hAns = [1] * n
    for i in range(m):
        a, b = map(int, readline().rstrip().split())
        if hList[a - 1] > hList[b - 1]:
            hAns[b - 1] = 0
            continue
        if hList[a - 1] < hList[b - 1]:
            hAns[a - 1] = 0
            continue
        hAns[a - 1] = 0
        hAns[b - 1] = 0
    print(sum(hAns))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    n, m = map(int, input().split())
    hList = list(map(int, input().split()))
    hAns = [1] * n
    for i in range(m):
        a, b = map(int, input().split())
        if hList[a - 1] > hList[b - 1]:
            hAns[b - 1] = 0
            continue
        if hList[a - 1] < hList[b - 1]:
            hAns[a - 1] = 0
            continue
        hAns[a - 1] = 0
        hAns[b - 1] = 0
    print(sum(hAns))


if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

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

for j in range(M):
    if H[List[j][0]-1]>H[List[j][1]-1]:
        sup_list[List[j][1]-1]=0
    elif H[List[j][0]-1]==H[List[j][1]-1]:
        sup_list[List[j][0]-1]=0
        sup_list[List[j][1]-1]=0
    else:
        sup_list[List[j][0]-1]=0


print(sum(sup_list))

Submission status: Accepted

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

root = [[] for i in range(N)]
for i in range(M):
  #root[A[i]-1].append(B[i])
  root[A[i]-1].append(H[B[i]-1])
  root[B[i]-1].append(H[A[i]-1])

count = 0
for i in range(N):
  if len(root[i]) == 0:
    count+=1
  else:
    if H[i] > max(root[i]):
      count+=1
print(count)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from math import sqrt

n,m = map(int,input().split())
graph=dict()
heights = list(map(int,input().split()))

for i in range(m):
    u,v = map(int,input().split())
    if(graph.get(u-1,0) == 0):
        graph[u-1]=[v-1]
    else:
        graph[u-1].append(v-1)
    if (graph.get(v - 1, 0) == 0):
        graph[v - 1] = [u - 1]
    else:
        graph[v - 1].append(u - 1)
ans=0
for key in graph:
    flag=True
    for obs in graph[key]:
        if(heights[key]<=heights[obs]):
            flag=False
            break
    if(flag):
        ans+=1
ans += (n-len(graph.keys()))
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)]

good_list = [1]*N
for i in range(M):
    if H[AB[i][0]-1] > H[AB[i][1]-1]:
        good_list[AB[i][1]-1] = 0
    elif H[AB[i][0]-1] == H[AB[i][1]-1]:
        good_list[AB[i][0] - 1] = 0
        good_list[AB[i][1] - 1] = 0
    else:
        good_list[AB[i][0] - 1] = 0

print(good_list.count(1))

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
h = list(map(int,input().split()))
x = [1]*n
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(x.count(1))

Submission status: Accepted

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

A=[0]*(N+1)
for i in range(M):
    x,y=map(int,input().split())
    A[x]=max(A[x],H[y-1])
    A[y]=max(A[y],H[x-1])

count=0
for i in range(1,N+1):
    if H[i-1]>A[i]:
        count+=1

print(count)

Submission status: Accepted

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

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

bad_two = set(bad)
ans = n - len(bad_two)
print(ans)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
good = [True for _ in range(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]):
    good[b-1] = False
  if(h[a-1] <= h[b-1]):
    good[a-1] = False
print(good.count(True))

Submission status: Accepted

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

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

obser = {}

for i in range(1, n+1):
    obser[i] = []

for i in range(m):
    obser[a[i]].append(b[i])
    obser[b[i]].append(a[i])
    
ans = 0

for i in range(1, n+1):
    target_height = h[i-1]
    invest_obser = obser[i]
    count = 0
    for obs in invest_obser:
        if target_height > h[obs-1]:
            count += 1
    if len(invest_obser) == count:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
import itertools
import math
import fractions
import functools
n, m = map(int, input().split())
h = list(map(int, input().split()))
ab = []
for i in range(m):
    ai, bi = map(int, input().split())
    ab.append([ai-1,bi-1])

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

print(v.count(True))

Submission status: Accepted

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

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

print(ans)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
arr=[0]+list(map(int,input().split()))
g=[[] for _ in range(n+1)]
for _ 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()))
road = []
for i in range(M):
    road.append(list(map(int,input().split())))

bad_ob = []

for i in range(M):
    if H[road[i][0]-1] > H[road[i][1]-1]:
        bad_ob.append(road[i][1]-1)
    elif H[road[i][0]-1] < H[road[i][1]-1]:
        bad_ob.append(road[i][0]-1)
    else:
        bad_ob.append(road[i][0]-1)
        bad_ob.append(road[i][1]-1)


print(N-len(set(bad_ob)))

Submission status: Accepted

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

n, m = map(int, input().split())
h = list(map(int, input().split()))
g = collections.defaultdict(list)
good = [True] * n
for i in range(m):
	a, b = map(int, input().split())
	a -= 1
	b -= 1
	g[a].append(b)
	g[b].append(a)
for i in range(n):
	found = False
	for j in g[i]:
		if h[j] >= h[i]:
			found = True
			break
	if found:
		good[i] = False
res = sum(good)
print(res)

Submission status: Accepted

Solution code:
import numpy as np

n,m = map(int,input().split())
h = list(map(int,input().split()))
ok = [0]*n

for i in range(m):
    a,b = map(int,input().split())
    a -=1
    b -=1
    if h[a] >= h[b]: ok[b] = 1
    if h[b] >= h[a]: ok[a] = 1
nplist = np.array(ok)
print(np.count_nonzero(nplist == 0))

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N,M = [int(x.strip()) for x in input().split()]
h_list = [int(x.strip()) for x in input().split()]
ok_list = [True] * N

for i in range(M):
    A,B = [int(x.strip()) for x in input().split()]
    if (h_list[A-1] == h_list[B-1]):
        ok_list[A-1] = False
        ok_list[B-1] = False
    elif (h_list[A-1] < h_list[B-1]):
        ok_list[A-1] = False
    else:
        ok_list[B-1] = False

ans = sum(v for v in ok_list)
print(ans)

Submission status: Accepted

Solution code:
class Mount():
    def __init__(self, i, H):
        self.i = i
        self.H = H
        self.rel_H = []
        self.max_H = 0

    def add_rel_H(self, H):
        self.rel_H.append(H)
        if self.max_H < H:
            self.max_H = H

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

d_mount = {}
for i, H in enumerate(input().split()):
	d_mount[i+1] = Mount(i+1, int(H))
    
inputs = [input() for i in range(M)]
for l in inputs:
    A = int(l.split()[0])  # mount id
    B = int(l.split()[1])  # mount id
    d_mount[A].add_rel_H(d_mount[B].H)
    d_mount[B].add_rel_H(d_mount[A].H)

count = 0
for k, v in d_mount.items():
    if len(v.rel_H) == 0:
        count += 1
    elif v.max_H < v.H:
        count += 1
        
print(count)

Submission status: Accepted

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

g = [True for _ in range(N)]
for _ in range(M):
    a, b = [int(_)-1 for _ in input().split()]
    if(H[a] <= H[b]):
        g[a] = False
    if(H[b] <= H[a]):
        g[b] = False
ans = g.count(True)
print(ans)

Submission status: Accepted

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

if __name__ == '__main__':
 	main()

Submission status: Accepted

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

Submission status: Accepted

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

n, m = [int(x) for x in input().split()]
h = [int(x) for x in input().split()]
g = [[] for _ in range(n)]
for _ in range(m):
    a, b = [int(x) for x in input().split()]
    g[a - 1].append(b - 1)
    g[b - 1].append(a - 1)
ans = 0
for i in range(n):
    flag = 1
    for j in g[i]:
        if h[j] >= h[i]:
            flag = 0
            break
    if flag:
        ans += 1
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
l=list(map(int,input().split()))
a=[0]*n
for i in range(m):
    x,y=map(int,input().split())
    a[x-1]=max(l[y-1],a[x-1])
    a[y-1]=max(l[x-1],a[y-1])
ans=0
for i in range(n):
    if l[i]>a[i]:
        ans+=1 
print(ans)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
hills = list(map(int, input().split()))
t_or_f = [True] * len(hills)

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

print(sum(t_or_f))

Submission status: Accepted

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

print(HP.count(0))

Submission status: Accepted

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

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

ans=0
for i in range(n):
 if h[i]>crime[i]:
  ans+=1

print(ans)

Submission status: Accepted

Solution code:
#coding: utf-8
N, M = map(int, input().split())
H = list(map(int, input().split()))
ans = [True for _ in range(N)]
for i in range(M):
    a, b = map(int, input().split())
    if H[a-1] <= H[b-1]:
        ans[a-1] = False
    if H[b-1] <= H[a-1]:
        ans[b-1] = False
print(sum(ans))

Submission status: Accepted

Solution code:
import collections
N,M=map(int,input().split())    
H=list(map(int,input().split()))
ans=[1]*N
for _ in range(M):
    AB=list(map(int,input().split()))
    if H[AB[0]-1] < H[AB[1]-1]:
        ans[AB[0]-1]=0
    elif H[AB[0]-1] > H[AB[1]-1]:
        ans[AB[1]-1]=0
    else:
        ans[AB[0]-1]=0
        ans[AB[1]-1]=0
#c=collections.Counter(ans)
print(ans.count(1))

Submission status: Accepted

Solution code:
"""
Peaks
AtCoder丘陵にはN個の展望台があり、展望台iの標高はHiです。
また、異なる展望台どうしを結ぶM本の道があり、道jは展望台Ajと展望台Bjを結んでいます。
展望台iが良い展望台であるとは、展望台iから一本の道を使って辿り着けるどの展望台よりも展望台iの方が標高が高いことをいいます。
展望台iから一本の道を使って辿り着ける展望台が存在しない場合も、展望台iは良い展望台であるといいます。
良い展望台がいくつあるか求めてください。
"""
N, M = map(int, input().split())
H = list(map(int, input().split()))
# 全展望台が良いと仮定する(良い=1, 悪い=0)
n = [1] * N
# 各道について
for i in range(M):
    a,b = map(int, input().split())
    # 道について高さを評価し、低い方は良い展望台ではない
    if H[a-1] >= H[b-1]:
        n[b-1] = 0
    if H[a-1] <= H[b-1]:
        n[a-1] = 0
print(sum(n))

Submission status: Accepted

Solution code:
# Problem C - Peaks

# input
N, M = map(int, input().split())
h_list = list(map(int, input().split()))

# initialization
ans_list = [1]*N
ans = 0

# count
for m in range(M):
    a, b = map(int, input().split())
    if h_list[a-1]>h_list[b-1]:
        ans_list[b-1] = -1
    elif h_list[a-1]<h_list[b-1]:
        ans_list[a-1] = -1
    else:
        ans_list[a-1] = -1
        ans_list[b-1] = -1

# check
for a in ans_list:
    if a>0:
        ans += 1

# output
print(ans)

Submission status: Accepted

Solution code:
"""
~~ author : dokueki
~~ created : 10~05~2020
"""

import sys
INT_MAX = sys.maxsize
INT_MIN = -(sys.maxsize)-1
sys.setrecursionlimit(10**7)
mod = 1000000007


def IOE():
    sys.stdin = open("input.txt", "r")
    sys.stdout = open("output.txt", "w")


def main():
    n, m = map(int, sys.stdin.readline().split())
    h = list(map(int, sys.stdin.readline().split()))
    ans = [True]*n
    for i in range(m):
        a, b = map(int, sys.stdin.readline().split())
        a -= 1
        b -= 1
        if h[a] < h[b]:
            ans[a] = False
        elif h[a] > h[b]:
            ans[b] = False
        else:
            ans[a], ans[b] = False, False
    print(sum(ans))


if __name__ == "__main__":
    try:
        IOE()
    except:
        pass
    main()

Submission status: Accepted

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

print(ans)

Submission status: Accepted

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

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

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

for v in range(N):
    flag = True
    
    for nv in G[v]:
        flag &= H[v]>H[nv]
    
    if flag:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
H_list = list(map(int, input().split()))
Check_list = ["OK" for i in range(N)]
for i in range(M):
    A, B = map(int, input().split())
    if H_list[A-1] > H_list[B-1]:
        Check_list[B-1] = "NG"
    elif H_list[A-1] < H_list[B-1]:
        Check_list[A-1] = "NG"
    elif H_list[A-1] == H_list[B-1]:
        Check_list[A-1] = "NG"
        Check_list[B-1] = "NG"
S = 0
for i in range(N):
    if Check_list[i] == "OK":
        S += 1
print(S)

Submission status: Accepted

Solution code:
from sys import stdin
import math
import fractions
from collections import deque
from collections import Counter
import itertools

INF = 10 ** 10

N, M = [int(x) for x in stdin.readline().rstrip().split()]
# 展望台iの標高
H = [0] + [int(x) for x in stdin.readline().rstrip().split()]
AB = [list(map(int, stdin.readline().rstrip().split())) for _ in range(M)]

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

for A, B in AB:
    near_max[A] = max(near_max[A], H[B])
    near_max[B] = max(near_max[B], H[A])

ans = 0

for i in range(1, N+1):
    if H[i] > near_max[i]:
        ans += 1

print(ans)