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()))
t = [set() for _ in range(n)]

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

ans = 0
for i in range(n):
    now_t = h[i]
    if t[i]:
        if all([now_t > h[tall] for tall in t[i]]):
            ans += 1
    else:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:

from sys import stdin
import sys
sys.setrecursionlimit(10**8)

def nextLine(): return next(stdin)
def nextStrList(): return nextLine().split()
def nextIntList(): return [int(_) for _ in nextStrList()]

from collections import defaultdict

def main():
	n,m=nextIntList()
	hs=nextIntList()
	
	pairHeight=defaultdict(lambda:0)
	for mi in range(m):
		a,b=nextIntList()
		
		pairHeight[a]=max(hs[b-1],pairHeight[a])
		pairHeight[b]=max(hs[a-1],pairHeight[b])

	c=0
	for ni in range(1,n+1):
		if pairHeight[ni]<hs[ni-1]:
			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()))
bad_towers = set()
for _ in range(M):
    A, B = map(int, input().split())
    if H[A-1] > H[B-1]:
        bad_towers.add(B)
    elif H[A-1] < H[B-1]:
        bad_towers.add(A)
    else:
        bad_towers.add(A)
        bad_towers.add(B)
print(N - len(bad_towers))

Submission status: Accepted

Solution code:

#n個の展望台
#mこの道
n,m=map(int,input().split())
#展望台の高さ
h=list(map(int,input().split()))

#print(h)
#全て良い展望台と仮定、
result=[1]*n

for _ in range(m):
    #aとbをつなぐ
    a,b=map(int,input().split())
    a=a-1
    b=b-1

    if h[a]<h[b]:
        result[a]=0
    elif h[b]<h[a]:
        result[b]=0
    else:
        result[a]=0
        result[b]=0


cnt=0
for item in result:
    if item==1:
        cnt+=1

#print(result)
print(cnt)

Submission status: Accepted

Solution code:
N, M = [int(i) for i in input().split()]
H = {i: int(h) for i, h in enumerate(input().split(), 1)}
t = {k: 0 for k in H.keys()}

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

print(sum(H[k] > v for k, v in t.items()))

Submission status: Accepted

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

for n in range(N):
    neib[n]=[]

#print(neib)
#print()
for m in range(M):
    A, B = map(int, input().split())
    neib[A-1].append(H[B-1])
    neib[B-1].append(H[A-1])
    
count = 0
#print(neib)
#print()

for k, v in neib.items():
    if len(v)==0:
        count += 1
    elif H[k] > max(v):
        count += 1
print(count)

Submission status: Accepted

Solution code:
NM = input().split()
N = int(NM[0])
M = int(NM[1])
L = input().split()
H_list = list(map(int, L))

lower_set = set() #低いものに属すもの最後に全体から引き算

for i in range(M):
    AB = input().split()
    A_offset = int(AB[0]) - 1
    B_offset = int(AB[1]) - 1

    if H_list[A_offset] - H_list[B_offset] > 0:
        lower_set.add(AB[1])
    elif H_list[A_offset] - H_list[B_offset] == 0:
        lower_set.add(AB[0])
        lower_set.add(AB[1])
    else:
        lower_set.add(AB[0])

print(N - len(lower_set))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
dd = {}
for i in range(1, N+1):
    dd[i] = []
temp = list(map(int, input().split()))
li_h = [0]
li_h.extend(temp)
for i in range(M):
    a, b= map(int, input().split())
    dd[a].append(b)
    dd[b].append(a)
#print(dd)
ans = 0
d = {}
for i in range(1, N+1):
    d[i] = True
for i in range(1, N+1):
        if not d:
            continue
        else:
            for k in dd[i]:
                if li_h[k] < li_h[i]:
                    d[k] = False
                elif li_h[k] == li_h[i]:
                    d[k] = False
                    d[i] = False
                    break
                else:
                    d[i] = False
                    break
            if d[i]:
                ans += 1
                #print(i)
            else:
                continue
print(ans)

Submission status: Accepted

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

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]:
        ans[b[i]-1] = 0
    elif h[a[i]-1] < h[b[i]-1]:
        ans[a[i]-1] = 0
    else:
        ans[b[i]-1] = 0
        ans[a[i]-1] = 0

print(sum(ans))

Submission status: Accepted

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

Tlist = []

for count in range(N):
    Tlist.append([])

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

ans = 0
for count in range(N):
    flag = True
    for count2 in range(len(Tlist[count])):
        if Hlist[count] <= Hlist[Tlist[count][count2]-1]:
            flag = False
            break
    if flag == True:
        ans = ans + 1

print(ans)

Submission status: Accepted

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

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

print(sum(judge))

Submission status: Accepted

Solution code:
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))

N, M = MAP()
H = LIST()
lights = [0] * N
for _ in range(M):
    a, b = MAP()
    a -= 1; b -= 1
    if lights[a] == 0:
        if H[a] <= H[b]:
            lights[a] += 1
    if lights[b] == 0:
        if H[b] <= H[a]:
            lights[b] += 1

print(lights.count(0))

# ans = 0
# for i in range(N):
#     flag = True
#     j = 0
#     while flag or j < len(AB):
#         a, b = AB[j][0], AB[j][1]
#         if a == i and H[a] <= H[b]:
#             flag = False
#             break

#         j += 1
#         if j == len(AB):
#             break

#     if flag:
#         ans += 1
# import deque





# print(ans)

Submission status: Accepted

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


def solve(N: int, M: int, H: "List[int]", A: "List[int]", B: "List[int]"):
    mountains = {i:'WIN' for i in range(N)}
    for road in range(M):
        if H[A[road]] < H [B[road]]:
            mountains[A[road]] = 'LOSE'
        elif H[A[road]] == H[B[road]]:
            mountains[A[road]] = 'LOSE'
            mountains[B[road]] = 'LOSE'
        elif H[A[road]] > H[B[road]]:
            mountains[B[road]] = 'LOSE'
    count = 0
    for i in range(N):
        if mountains[i] == 'WIN':
            count += 1
    print(count)
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    H = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    A = [int()] * (M)  # type: "List[int]"
    B = [int()] * (M)  # type: "List[int]"
    for i in range(M):
        A[i] = int(next(tokens)) - 1
        B[i] = int(next(tokens)) - 1
    solve(N, M, H, A, B)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

# print(H)

data = []

for i in range(N):
  data.append([])

# print(data)
  
for i in range(M):
  way1, way2 = map(int, input().split(" "))
  data[way1-1].append(way2)
  data[way2-1].append(way1)

  
count = 0
for i in range(N):
  is_higher = False
  mountain_hights = [0]
  for j in data[i]:
    mountain_hights.append(H[j - 1])
  if H[i] > max(mountain_hights):
    count += 1

print(count)

Submission status: Accepted

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

h = list(map(int,input().split()))
for i in range(1,m+1):
  ab = list(map(int,input().split()))
  if (h[ab[0]-1] > h[ab[1]-1]):
    tenbou[ab[1]-1]=0
  if (h[ab[0]-1] < h[ab[1]-1]):
    tenbou[ab[0]-1]=0
  if (h[ab[0]-1] == h[ab[1]-1]):
    tenbou[ab[0]-1]=0
    tenbou[ab[1]-1]=0   
#  print (ab, tenbou)

print(tenbou.count(1))

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
H = [0] + list(map(int, input().split())) 
AB = [tuple(map(int, input().split())) for _ in range(M)]
good_num = N
pair = [set(e)  for e in set(AB)]
bad_tenbodai = []
for a,b in pair:
    i, j = H[a], H[b]
    if i < j:
        bad_tenbodai.append(a)
    elif i == j:
        bad_tenbodai.extend([a,b])
    else:
        bad_tenbodai.append(b)
print(N - len(set(bad_tenbodai)))

Submission status: Accepted

Solution code:
INT = lambda: int(input())
INTM = lambda: map(int,input().split())
STRM = lambda: map(str,input().split())
STR = lambda: str(input())
LIST = lambda: list(map(int,input().split()))
LISTS = lambda: list(map(str,input().split()))
def do():
    n,m=INTM()
    h=LIST()
    hantei=[1]*n
    for i in range(m):
        a,b=INTM()
        a=a-1
        b=b-1
        if h[a]>h[b]:
            hantei[b]=0
        elif h[a]<h[b]:
            hantei[a]=0
        else:
            hantei[a]=0
            hantei[b]=0
    print(sum(hantei))

    
if __name__ == '__main__':
    do()

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 = set()
for i in range(M):
  a = A[i]-1
  b = B[i]-1
  if H[a]>H[b]:
    s.add(b)
  elif H[a] == H[b]:
    s.add(a)
    s.add(b)
  else:
    s.add(a)
print(N - len(s))

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
H = list(map(int, input().split()))
res_count = [0] * N
appear_count = [0] * N

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

print(res_count.count(0))

Submission status: Accepted

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

Submission status: Accepted

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

H2_list=[0]*N

for i in range(M):
  A,B = map(int,input().split())
  if H_list[A-1]<H_list[B-1]:
    #print(H_list[A-1],"<",H_list[B-1])
    H2_list[A-1]=-1
  elif H_list[A-1]==H_list[B-1]:
    H2_list[A-1]=-1
    H2_list[B-1]=-1
  else:
    #print(H_list[A-1],">",H_list[B-1])
    H2_list[B-1]=-1


print(N-H2_list.count(-1))
#print(H2_list)

Submission status: Accepted

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

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

way_list = []
for i in range(m):
    org = list(map(int, input().split()))
    org.sort()
    way_list.append(org)

bad = []

for j in range(m):
    way = way_list[j]
    if h_list[way[0]-1] > h_list[way[1]-1]:
        bad.append(way[1])
    elif h_list[way[0]-1] < h_list[way[1]-1]:
        bad.append(way[0])
    else:
        bad.append(way[0])
        bad.append(way[1])

bad = list(set(bad))
print(n - len(bad))

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# [[i],..]でi番目の展望台につながっている展望台をリストアップしていく
N,M=map(int,input().split())
H=list(map(int,input().split()))
L=[[] for i in range(N)]
for _ in range(M):
    a,b = map(int,input().split())
    L[a-1].append(b-1)
    L[b-1].append(a-1)
score=0
for i,l in enumerate(L):
    if not l:
        score+=1
        continue
    my_max=H[i]
    is_max=True
    for li in l:
        if H[li]>=my_max:
            is_max=False
            break
    if is_max:
        score+=1
print(score)

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)]
ab = list(map(list, set(map(tuple, ab))))
ans = [True] * n

for a, b in ab:
    if h[a-1] == h[b-1]:
        ans[a-1] = False
        ans[b-1] = False
    elif h[a-1] < h[b-1]:
        ans[a-1] = False
    else:
        ans[b-1] = False

print(ans.count(True))

Submission status: Accepted

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

Submission status: Accepted

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

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

print(cnt.count(0))

Submission status: Accepted

Solution code:
N,M = map(int,input().split()) 
H = list(map(int,input().split()))
lst = [[] for _ in range(N)]
for i in range(M):
    A,B = map(int,input().split())
    lst[A-1].append(B-1)
    lst[B-1].append(A-1)
cnt = 0
for i in range(N):
    if len(lst[i]) == 0:
        cnt += 1
    else:
        flg = True
        for j in lst[i]:
            if H[i] <= H[j]:
                flg = False
        if flg:
            cnt += 1
print(cnt)

Submission status: Accepted

Solution code:
b0=input().split()
N=int(b0[0])
L=int(b0[1])

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

nl=[0 for x in range(N)]
for l in range(L):
  l0=input().split()
  h1=int(l0[0])-1
  h2=int(l0[1])-1
  if hl[h1]>hl[h2]:
    nl[h2]+=1
  elif hl[h1]<hl[h2]:
    nl[h1]+=1
  else:
    nl[h1]+=1
    nl[h2]+=1

A=0
for nn in nl:
  if nn==0:
    A+=1
    
print(A)

Submission status: Accepted

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

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
    elif h[b-1]>h[a-1]:
        ans[a-1] = 0
    else:
        #print("a")
        ans[a-1] = 0
        ans[b-1] = 0
print(ans.count(1))

Submission status: Accepted

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

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

for j in range(M):
  a, b = map(int,input().split())
  if(H[a-1] == H[b-1]):
    good[a-1] += 1
    good[b-1] += 1
  elif(H[a-1] < H[b-1]):
    good[a-1] += 1
  else:
    good[b-1] += 1
count = 0
for i in range(N):
  if(good[i] == 0):
    count += 1
print(count)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
h=input().split()
out=[]
ab=[0]*m
for i in range(m):
  ab[i]=input().split()
  if int(h[int(ab[i][0])-1])==int(h[int(ab[i][1])-1]):
    out.append(ab[i][0])
    out.append(ab[i][1])
  elif int(h[int(ab[i][0])-1])>int(h[int(ab[i][1])-1]):
    out.append(ab[i][1])
  else:
    out.append(ab[i][0])


out=set(out)
print(n-len(out))

Submission status: Accepted

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

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

ans = set()
for i in range(n):
    stack = table[i]
    highest = h[i]
    flag = True
    for t in table[i]:
        if highest <= h[t]:
            flag = False
            break
    if flag:
        ans.add(i)
print(len(ans))

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(1000000)


def main():
    n, m = map(int, input().split())
    h_list = list(map(int, input().split()))
    not_good = set()
    for i in range(m):
        a, b = map(int, input().split())
        # ll.append((a-1, b-1))
        x = a-1
        y = b-1
        hx = h_list[x]
        hy = h_list[y]
        if hx == hy:
            not_good.add(x)
            not_good.add(y)
        elif hx > hy:
            not_good.add(y)
        else:
            not_good.add(x)

    print(n - len(not_good))


main()

Submission status: Accepted

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

Submission status: Accepted

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

for _  in range(m):
  a,b=list(map(int,input().split()))
  if H[a-1]>H[b-1]:
    A[b-1]=0
  elif H[a-1]<H[b-1]:
    A[a-1]=0
  else:
    A[a-1]=0
    A[b-1]=0
#print(H,A)
print(n-A.count(0))

Submission status: Accepted

Solution code:
from heapq import heapify, heappush, heappop
from heapq import _heapify_max, _heappop_max
import heapq

def _heappush_max(heap, item):
    heap.append(item)
    heapq._siftdown_max(heap, 0, len(heap)-1)

"""
method:
    heapify(x): ヒープに変換
    heappush(heap, item): itemをheapにpush
    heappop(heap): heapから最小値を取得 空の場合はIndexError
note:
    max heapにする場合は、prefix: _ とsuffix: _maxをつければ良い
"""
def main():
    n, m = map(int, input().split())
    h = [0] + list(map(int, input().split()))
    ans = [[] for _ in range(n+1)]
    for _ in range(m):
        a, b = map(int, input().split())
        _heappush_max(ans[a], h[b])
        _heappush_max(ans[b], h[a])
    out = 0
    for ai, hi in zip(ans[1:], h[1:]):
        if (not ai) or hi > _heappop_max(ai):
            out += 1
    print(out)

if __name__ == "__main__":
    main()

Submission status: Accepted

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

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

def main():
    mod=10**9+7
    N,M=MI()
    H=LI()
    adj=[[]for _ in range(N)]
    for i in range(M):
        a,b=MI()
        a-=1
        b-=1
        adj[a].append(b)
        adj[b].append(a)
        
    used=[0]*N
    Hi=[[0,0]for _ in range(N)]
    for i in range(N):
        Hi[i][0]=H[i]
        Hi[i][1]=i
        
    Hi.sort(reverse=True)
    
    ans=0
    for i in range(N):
        v=Hi[i][1]
        HH=Hi[i][0]
        if used[v]==0:
            temph=0
            used[v]=1
            for nv in adj[v]:
                temph=max(H[nv],temph)
                used[nv]=1
            if HH>temph:
                ans+=1
                
    print(ans)
        
    

main()

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
H=list(map(int,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-1)
    tenbo[B-1].append(A-1)
   
for i in range(N):
    flg=1
    for j in range(len(tenbo[i])):
        if H[i]<=H[tenbo[i][j]]:
            flg=0
            break
    if flg:
        ans+=1
        
        
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
n, m = map(int, input().split())
tenboudai = [True for i in range(n)]

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

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

for path in path_list:
    if h_list[path[0]] < h_list[path[1]]:
        tenboudai[path[0]] = False
    elif h_list[path[1]] < h_list[path[0]]:
        tenboudai[path[1]] = False
    else:
        tenboudai[path[0]] = False
        tenboudai[path[1]] = False

print(tenboudai.count(True))

Submission status: Accepted

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

l=[True]*n

for x in a:
    if h[x[0]-1]>=h[x[1]-1]:l[x[1]-1]=False
    if h[x[0]-1]<=h[x[1]-1]:l[x[0]-1]=False

cnt=0
for y in l:
    if y:cnt+=1
print(cnt)

Submission status: Accepted

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

def main():
  n, m = map(int, input().split())
  tower_list = []
  for h in map(int, input().split()):
    tower_list.append([0,h,[]])
  
  count = n
  
  for _ in range(m):
    t1, t2 = map(int, input().split())
    if tower_list[t1-1][0] == 0:
      if tower_list[t1-1][1] <= tower_list[t2-1][1]:
        tower_list[t1-1][0] = 1
        n -= 1
    if tower_list[t2-1][0] == 0:
      if tower_list[t2-1][1] <= tower_list[t1-1][1]:
        tower_list[t2-1][0] = 1
        n -= 1
    
  return n

if __name__=='__main__':
  print(main())

Submission status: Accepted

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

B=list(set(B))
print(len(A)-len(B))

Submission status: Accepted

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

H = np.array(list(map(int, input().split())))
# print(H)

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

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
list1 = list(map(int, input().split()))
list2 = [list(map(int, input().split())) for _ in range(M)]
dict1 = {i+1:[] for i in range(N)}
#print(dict1)
for l in list2:
    dict1[l[1]].append(l[0])
    dict1[l[0]].append(l[1])
res = 0
for i in range(N):
    a =  1
    if dict1 == []:
        res += 1
        continue
    for j in dict1[i+1]:
        if list1[i] <= list1[j-1]:
            a = 0
    if a == 1:
        res+=1
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):
  a, b = map(int, input().split())
  A.append(a)
  B.append(b)
  
list_ans = [1] * n;

for i in range(m):
  #左の山の方が右の山より小さい時
  if H[A[i] - 1] < H[B[i] - 1]:
    list_ans[A[i] - 1] = 0;
	
  #右の山の方が小さい時
  elif H[A[i] - 1] > H[B[i] - 1]:
    list_ans[B[i] - 1] = 0;
  
  #両方同じ時
  else:  
    list_ans[A[i] - 1] = 0;
    list_ans[B[i] - 1] = 0;
  
print(sum(list_ans))

Submission status: Accepted

Solution code:
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 = a - 1
    b = b - 1
    if not H[a] > H[b]:
        good[a] = False
    if not H[a] < H[b]:
        good[b] = False

print(sum([1 if good[i] else 0 for i in range(N)]))

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
h = list(map(int, input().split()))
ab = [tuple(map(int, input().split())) for _ in range(m)]
dic = {}
ban = {}
for i in range(m):
    a = ab[i][0]
    b = ab[i][1]

    if dic.get(a):
        dic[a] = max(dic[a], h[b - 1])
    else:
        dic[a] = h[b - 1]

    if dic.get(b):
        dic[b] = max(dic[b], h[a - 1])
    else:
        dic[b] = h[a - 1]
ans = 0
for i in range(n):
    if dic.get(i + 1):
        if dic[i + 1] < h[i]:
            ans += 1
    else:
        ans += 1
print(ans)

Submission status: Accepted

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

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

ans = N
for i in range(len(tenbou)):
    for val in tenbou[i+1]:
        if(H[i] <= H[val-1]):
            ans -= 1
            break
print(ans)

Submission status: Accepted

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

for i in range(M):
    if H[AB[i][0]-1]==H[AB[i][1]-1]:
        count.append(AB[i][1])
        count.append(AB[i][0])
    elif H[AB[i][0]-1]<H[AB[i][1]-1]:
        count.append(AB[i][0])
    else:
        count.append(AB[i][1])

loser = list(set(count))

print(N-len(loser))

Submission status: Accepted

Solution code:
line = input().split(" ")
#展望台の個数
N = int(line[0])
#道の個数
M = int(line[1])

isnum = [True] * N

h_list = input().split(" ")
count = 0
for i in range (M):
  a = input().split(" ")
  if int(h_list[int(a[0])-1]) == int(h_list[int(a[1])-1]):
    isnum[int(a[0]) - 1] = False
    isnum[int(a[1]) - 1] = False
    continue
  elif int(h_list[int(a[0])-1]) < int(h_list[int(a[1])-1]):
    isnum[int(a[0]) - 1] = False
  elif int(h_list[int(a[0])-1]) > int(h_list[int(a[1])-1]):
    isnum[int(a[1]) - 1] = False
n = sum(x==True for x in isnum)
print(n)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
High = list(map(int, input().split()))
Road =[[]for i in range(N)]
ans = 0

for i in range(M):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    if a in Road[b]:
        continue
    Road[a].append(b)
    Road[b].append(a)

for i in range(N):
    now = High[i]
    flag = True
    for j in Road[i]:
        if now <= High[j]:
            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()))
l = [i for i in range(n)]
ans = set(l)
for i in range(m):
  a, b = map(int, input().split())
  a = a-1
  b = b-1
  if h[a] > h[b]:
    ans.discard(b)
  elif h[a] == h[b]:
    ans.discard(a)
    ans.discard(b)
  else:
    ans.discard(a)

print(len(ans))

Submission status: Accepted

Solution code:
# cook your code here
from collections import defaultdict
n,m=map(int,raw_input().split())
a=map(int,raw_input().split())
d={}
a=[0]+a
d = defaultdict(list) 
for i in range(m):
    u,v=map(int,raw_input().split())
    


    d[u].append(a[v]) 
    d[v].append(a[u]) 
      
    


c=0
#print d
for i in range(1,n+1):
	if i in d:
		if a[i]>max(d[i]):
			c+=1
	
	else:
		c+=1

print c

Submission status: Accepted

Solution code:
nm = input('')
n=int(nm.split(' ')[0])
m=int(nm.split(' ')[1])
hs = input('').split(' ')

abmap = {}
for i in range(m):
    ab = input('')
    a = int(ab.split(' ')[0])
    b = int(ab.split(' ')[1])
    if a in abmap.keys():
        abmap[a].append(b)
    else:
        abmap[a] = [b]
    if b in abmap.keys():
        abmap[b].append(a)
    else:
        abmap[b] = [a]

ytb_cnt=0
for a,b in abmap.items():
    ah = int(hs[a-1])
    ytb = 1
    for bn in b:
        bh = int(hs[bn-1])
#        print("{}[{}]->{}[{}]".format(a,ah,b,bh))
        if ah <= bh:
            ytb=0
    if ytb == 1:
        ytb_cnt+=1
for h in range(len(hs)):
    if not (h+1) in abmap.keys():
#        print("{} is no root".format(h+1))
        ytb_cnt+=1
print(ytb_cnt)

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
	elif h[a-1]<h[b-1]:
		ans[a-1]=0
	else:
		ans[b-1]=0
		ans[a-1]=0
print(ans.count(1))

Submission status: Accepted

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