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: Time Limit Exceeded

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

count = 0

#iは灯台i
for i in range(1,n+1):
    #道で繋がってる灯台をpairに収納
    pair = []
    for j in range(m):
        if i in road[j]:
            pair += list(set(road[j])-set([i]))

    higher = 0
    for k in range(len(pair)):
        if h[i-1] <= h[pair[k]-1]:
            higher += 1

    if higher == 0:
        count += 1

print(count)

Submission status: Time Limit Exceeded

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


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

obvs = list(range(1,N+1,1))

obvs_height = list(map(int, input().split()))
#print(obvs)

def get_height_of_obvs(i):
    return obvs_height[i-1]

def remove_obvs_if_exist(i):
    if i in obvs:
        obvs.remove(i)

while True:
    #print(obvs)
    path = list(map(int, input().strip().split()))
    if path==[]:
        break
    if get_height_of_obvs(path[0]) == get_height_of_obvs(path[1]):
        remove_obvs_if_exist(path[0])
        remove_obvs_if_exist(path[1])

    elif get_height_of_obvs(path[0]) > get_height_of_obvs(path[1]):
        remove_obvs_if_exist(path[1])
    elif get_height_of_obvs(path[0]) < get_height_of_obvs(path[1]):
        remove_obvs_if_exist(path[0])

print(len(obvs))

Submission status: Time Limit Exceeded

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

rode=[[0 for _ in range(N)] for _ in range(N)]

for j in range(M):
    a,b=map(int,input().split())
    rode[a-1][b-1]=rode[b-1][a-1]=1

def trv(i):
  maxh=H[i]
  for j in range(N):
    if rode[i][j]>0:
        if H[j]>=maxh:
          return False
  return True

goodv = [1 for i in range(N) if trv(i) ]
print(len(goodv))

Submission status: Time Limit Exceeded

Solution code:
n,m = list(map(int,input().split()))
h = list(map(int,input().split()))
a_list = []
b_list = []
good_list = list(range(1,n+1))
for i in range(m):
    a,b = list(map(int,input().split()))
    a_list.append(a)
    b_list.append(b)
    if a in good_list:
        if h[a-1] < h[b-1] or h[a-1] == h[b-1]:
            good_list.remove(a)
    if b in good_list:
        if h[a-1] > h[b-1] or h[a-1] == h[b-1]:
            good_list.remove(b)
print(len(good_list))

Submission status: Time Limit Exceeded

Solution code:
N,M = map(int,input().split())
H = list(map(int,input().split()))
List = []
for k in range(1,N+1):
  List.append(k)
for i in range(M):
  A,B = map(int,input().split())
  tmpA = H[A-1]
  tmpB = H[B-1]
  if(tmpA < tmpB):
    if(List.count(A) == 0):
      pass
    else:
      List.remove(A)
  elif(tmpA > tmpB):
    if(List.count(B) == 0):
      pass
    else:
      List.remove(B)
  else:
    if(List.count(A) == 0):
      pass
    else:
      List.remove(A)
    if(List.count(B) == 0):
      pass
    else:
      List.remove(B)
print(str(len(List)))

Submission status: Time Limit Exceeded

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

cnt =0
for i in range(N):
    flg = 0
    for j in range(M):
        if table[j][0] == i+1:
            if H[i] <= H[table[j][1]-1]:
                flg = 1
        if table[j][1] == i+1:
            if H[i] <= H[table[j][0]-1]:
                flg = 1
    if flg == 0:
        cnt += 1
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
a=[int(i) for i in input().split()]
s=0
b=[]
co=[]
for i in range(n):
  co.append([0 for iii in range(n)])
for i in range(n):
  b.append([0,0])
for i in range(m):
    p1,p2=map(int,input().split())
    if co[p1-1][p2-1]==0:
        co[p1-1][p2-1]=1
        co[p2-1][p1-1]=1
        b[p1-1][0]+=1
        b[p2-1][0]+=1
        if a[p1-1]>a[p2-1]:
            b[p1-1][1]+=1
        elif a[p1-1]<a[p2-1]:
            b[p2-1][1]+=1

for i in b:
  if i[0]==i[1]:

      s+=1
#print(b)
print(s)

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split(' '))
H = list(map(int, input().split(' ')))
MICHI = []
for m in range(M):
    MICHI.append(tuple(map(int, input().split(' '))))

# 展望台接続関係マップ
setsuzokumap = [[0 for i in range(N)] for j in range(N)]

for m in MICHI:
    setsuzokumap[m[0] - 1][m[1] - 1] = 1

# print(setsuzokumap)

good_tenboudai = [None] * N

# すべての展望台を調べる
for n in range(N):
    # 未判断の展望台を調べる
    if good_tenboudai[n] is None:
        # すべての接続パターンを調べる
        for m in range(N):
            # 接続あり
            if setsuzokumap[n][m] == 1:
                # 接続先が良い展望台ならば、この展望台は自動的によくない
                if good_tenboudai[m] == 1:
                    good_tenboudai[n] = 0
                else:
                    # 接続先の高さが自分以下だったら接続先は必ずよくない
                    if H[m] <= H[n]:
                        good_tenboudai[m] = 0

                    # 自分の高さが接続先以下だったらよくない
                    if H[n] <= H[m]:
                        good_tenboudai[n] = 0

# 最後まで良くないと判定されなかったのが良いの
for n in range(N):
    if good_tenboudai[n] is None:
        good_tenboudai[n] = 1

print(sum(good_tenboudai))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

adj = [[0 for _ in range(N)] for _ in range(N)]

for line in Mlist:
    adj[line[0]-1][line[1]-1] = 1
    adj[line[1]-1][line[0]-1] = 1

# for i in range(N):
#     adj[i][i] = 1

Hmatrix = [Hlist for _ in range(N)]
target = np.array(Hmatrix)*np.array(adj)
index_list = [i for i in range(len(adj)) if sum(adj[i]) != 0]

count = N - len(index_list)
for i in index_list:
    if max(target[i]) < Hlist[i]:
        count += 1
print(count)

Submission status: Time Limit Exceeded

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

flag = 0
X = 0

for a in range(1, N+1):
    for b in grid:
        if b[0] == a:
            if H[b[1]-1] >= H[a-1]:
                break
        elif b[1] == a:
            if H[b[0]-1] >= H[a-1]:
                break
    else:
        X += 1

print(X)

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
ans_list = list(range(1,N+1))
HList = list(map(int, input().split()))
rootList = []

for i in range(M):
  a, b = map(int, input().split())
  H_a = HList[a-1]
  H_b = HList[b-1]
  if(a in ans_list):
    if(H_b > H_a or H_b == H_a):
      ans_list.remove(a)
  if(b in ans_list):
    if(H_a > H_b or H_b == H_a):
      ans_list.remove(b)

print(len(ans_list))

Submission status: Time Limit Exceeded

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

inputLine=input()
H=inputLine.split(" ")
for i in range(len(H)):
    H[i]=int(H[i])

root=[]
for i in range(M):
    inputLine=input()
    A=int(inputLine.split(" ")[0])
    B=int(inputLine.split(" ")[1])

    root.append([A,B])
    root.append([B,A])

root.sort()    

allObservatoryCheck=[]
for i in range(N):
    allObservatoryCheck.append(True)

for i in range(N):

    for j in range(len(root)):
        
        if root[j][0] == i + 1:
            if H[i] <= H[root[j][1] - 1]:
                allObservatoryCheck[i] = False

        if root[j][0] > i + 1:
            break

result = 0
for i in range(N):
    if allObservatoryCheck[i] == True:
        result += 1

print(result)

Submission status: Time Limit Exceeded

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

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

    ans = 0
    for j in range(N):
        if not A[j]:
            ans += 1
            continue

        now = H[j]
        if (now > max(A[j])):
            ans += 1

    print(ans)


resolve()

Submission status: Time Limit Exceeded

Solution code:
N, M = [int(x) for x in input().split()]
H = [int(x) for x in input().split()]
mat = [[0 for i in range(N)] for j in range(N)]
for j in range(M):
    a, b = [int(x) for x in input().split()]
    mat[a - 1][b - 1] = H[b - 1]
    mat[b - 1][a - 1] = H[a - 1]

count = 0
for i in range(N):
    h = H[i]
    max_h = max(mat[i])
    if h > max_h:
        count += 1
print(count)

Submission status: Time Limit Exceeded

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

# calc
d = [[0 for _ in range(n)] for _ in range(n)]
for i in range(m):
    d[a[i]-1][b[i]-1] = 1 
    d[b[i]-1][a[i]-1] = 1 

# print(d)
ans = 0 
for i in range(n):
    ok = True
    for j in range(n):
        if d[i][j] == 1:
           if h[i] <= h[j]:
               ok = False
               break
    if ok: 
        ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def resolve():
    # 整数 1 つ
    # n = int(input())
    # 整数複数個
    n, m = list(map(int, input().split()))
    # 整数 N 個 (改行区切り)
    # N = [int(input()) for i in range(N)]
    # 整数 N 個 (スペース区切り)
    H = list(map(int, input().split()))
    # 整数 (縦 H 横 W の行列)
    R = [list(map(int, input().split())) for i in range(m)]

    cnt = 0
    for i in range(1, n+1):
        highst = True
        for r in R:
            if r[0] == i:
                if H[i-1] <= H[r[1]-1]:
                    highst = False
                    break
            if r[1] == i:
                if H[i-1] <= H[r[0]-1]:
                    highst = False
                    break

        if highst == True:
            cnt += 1

    print(cnt)
resolve()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
# スペース区切りの整数の入力
N, M = map(int, input().split())
# 文字列の入力
H_list = list(map(int, input().split()))
#print(H_list)
#開業されたN個要素を受け付ける
road_list = []
for i in range(M):
    road_list.append(list(map(int, input().split())))
#print(road_list)
ans = 0
for i in range(N):
    #print(i+1)
    flg = 1
    for road in road_list:
        if i+1 in road:
            if i+1 == road[0] and H_list[road[0]-1] <= H_list[road[1]-1]:
                flg=0
            elif i+1 == road[1] and H_list[road[1]-1] <= H_list[road[0]-1]:
                flg=0
    if flg==1:
        #print("flg")
        ans=ans+1
print(ans)

Submission status: Time Limit Exceeded

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

for i in range(0, N):
    for a, b in dai:
        if i+1 == a:
            if H[a - 1] > H[b - 1]:
                continue
            else:
                plus[i] = -1
                break
        if i+1 == b:
            if H[b - 1] > H[a - 1]:
                continue
            else:
                plus[i] = -1
                break
print(len(set(plus))-1)

Submission status: Time Limit Exceeded

Solution code:
N,M=map(int,input().split())#展望台ｎこ、m本の道
H=list(map(int,input().split()))#hyouko
I=[i for i in range(1,N+1)]
tenbo={}
for h,i in zip(H,I):
  tenbo[i]=h#{1:2m,2:3m}
#print('tembo',tenbo)
mitis=[]
for _ in range(M):
  mitis.append(list(map(int,input().split())))
#print('mitis',mitis)
count=0
ans=0
ikeru=0
for i in range(1,N+1):
  for miti in mitis:
#    print('miti',miti)
    if i in miti:
#      print('pass')
      ikeru+=1
      if miti[0]==i:
        if tenbo[miti[0]]>tenbo[miti[1]]:
          count+=1
      elif miti[1]==i :
         if tenbo[miti[1]]>tenbo[miti[0]]:
          count+=1
  if count==ikeru:
    ans+=1
#  print(count)
  count=0
  ikeru=0
print(ans)

Submission status: Time Limit Exceeded

Solution code:
a=input().split()
N=int(a[0])
M=int(a[1])
H_list=input().split()
H_list=[int(i) for i in H_list]
path_list=[]
for i in range(M) :
  b=input().split()
  path_list.append([int(b[0]),int(b[1])])
count=0


c=list(range(1,N+1))
for i in path_list :
    if H_list[i[0]-1]>H_list[i[1]-1] :
        if  i[1] in c :
            c.remove(i[1])
    elif H_list[i[0]-1]<H_list[i[1]-1]  :
        if i[0] in c :
            c.remove(i[0])
    else :
        if i[0] in c :
            c.remove(i[0])
        if i[1] in c :
            c.remove(i[1])
print(len(c))

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
from collections import deque

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

cnt = 0
for i in range(1,N+1):
    tmp = deque()
    for j in AB:
        if i in j:
            tmp.extend(j)
    tmp = list(set(tmp))
#    print(i,tmp)

    top_flag = True
    for k in tmp:
        if i == k:
            continue
        if H[i-1] <= H[k-1]:
            top_flag = False
    if top_flag == True:
        cnt += 1

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N,M=map(int,input().split())
H=list(map(int,input().split()))
C=[[0] * N for i in range(N)]
ans=0
for _ in range(M):
    A,B=map(int,input().split())
    C[A-1][B-1]=1
    C[B-1][A-1]=1

for i in range(N):
    D=C[i]
    if sum(D)>=1:
        d=np.array(D)
        m=max(d*H)
        if H[i]>m:
            ans+=1
    else:
        ans+=1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
if __name__ == "__main__":
    N, M = list(map(int, input().split()))
    H = list(map(int, input().split()))
    adj_mat = [[0 for i in range(N)] for i in range(N)]
    for i in range(M):
        a, b = list(map(int, input().split()))
        adj_mat[a-1][b-1] = 1
        adj_mat[b-1][a-1] = 1
    num = 0
    for i in range(N):
        temp = [0 for i in range(N)]
        for j in range(N):
            temp[j] = adj_mat[i][j] * H[j]
        if H[i] > max(temp):
            num += 1
    print(num)

Submission status: Time Limit Exceeded

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

def RD(): return sys.stdin.read()
def II(): return int(input())
def MI(): return map(int,input().split())
def LI(): return list(map(int,input().split()))
def TI(): return tuple(map(int,input().split()))
def RN(N): return [input().strip() for i in range(N)]


def main():
    N, M = MI()
    H = LI()
    H.insert(0,0)
    A = [0]*M
    B = [0]*M
    ans = 0
    for i in range(M):
        A[i], B[i]=MI()
    for i in range(1,N+1):
        #print("hi",i,H[i])
        ng = 0
        for j in range(M):
            if A[j] == i:
                if H[i]<=H[B[j]]:
                    ng += 1
                    #print(i, "no")
                    break
            if B[j] == i:
                if H[i]<=H[A[j]]:
                    ng += 1
                    break
        if ng == 0:
            ans += 1
    print(ans)


    


if __name__ == "__main__":
	main()

Submission status: Time Limit Exceeded

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

for i in range(M):
    A,B=map(int,input().split())
    C=H[A-1]
    D=H[B-1]
    if C>D:
        li.append(B)
    elif D>C:
        li.append(A)
    else:
        li.append(A)
        li.append(B)

for j in range(N):
    if j+1 in li:
        pass
    else:
        ans.append(j+1)

print(len(ans))

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-
#
# FileName: 	C
# CreatedDate:  2020-05-03 21:27:46 +0900
# LastModified: 2020-05-03 21:47:49 +0900
#


import os
import sys


def main():
    n,m = map(int,input().split())
    h = list(map(int,input().split()))
#    color=[0]*n
    matrix = list([0]*n for _ in range(n))
    for i in range(m):
        a,b = map(int,input().split())
        matrix[a-1][b-1]=1
        matrix[b-1][a-1]=1
    
    count=0
    flag=0
    for i in range(n):
        for j in range(n):
            if matrix[i][j]==1 and h[i]<=h[j] :
                flag=1
                break
        if flag==0:
#            color[i]=1
            count+=1
        flag=0
    print(count)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

# input
n, m = map(int, input().split())
h = list(map(int, input().split()))
a = [0 for _ in range(m)]
b = [0 for _ in range(m)]
for i in range(m):
    a[i], b[i] = map(int, input().split())

# calc
d = [[0 for _ in range(n)] for _ in range(n)]
for i in range(m):
    d[a[i]-1][b[i]-1] = 1 
    d[b[i]-1][a[i]-1] = 1 

# print(d)
ans = 0 
for i in range(n):
    ok = True
    for j in range(n):
        if d[i][j] == 1:
           if h[i] <= h[j]:
               ok = False
               break
    if ok: 
        ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
# 展望台N
# 道M
N, M = map(int, input().split())

# 展望台の高さ
H = list(map(int, input().split()))

n = [[0] * N for i in range(N)]

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

cnt = 0
for i in range(N):
  if H[i] > max(n[i]):
    cnt +=1
    
print(cnt)

Submission status: Time Limit Exceeded

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

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

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

for i in range(M):
    a, b = map(int, input().split())
    if H[a-1] > H[b-1]:
        try:
            ans.remove(str(b))
        except Exception as e:
            continue
    elif H[b-1] > H[a-1]:
        try:
            ans.remove(str(a))
        except Exception as e:
            continue
    else:
        try:
            ans.remove(str(a))
            try:
                ans.remove(str(b))
            except Exception as e:
                continue
        except Exception as e:
            try:
                ans.remove(str(b))
            except Exception as e:
                continue

print(len(ans))

Submission status: Time Limit Exceeded

Solution code:
#N　展望台の数　M　道の数
N,M = map(int, input().split())
#高さ
H =list(map(int,input().split()))

ans=0

#道
J=[""]*M
for i in range(M):
  J[i]=(list(map(int, input().split())))

for i in range(1,N+1):
  dic={}
  flg = 0
  for j in J:    
    if j[0] == i:
      dic.setdefault(j[1],0)
      dic[j[1]]+=1 
    elif j[1] == i:
      dic.setdefault(j[0],0)
      dic[j[0]]+=1
  
  if len(dic) == 0:
    ans+=1
  else:
    for k,v in dic.items():
      if H[k-1] >= H[i-1]:
        flg = 1
    if flg == 0:
      ans+=1

    
print(ans)
    
#    for k,v in dic.items():
#      if not v > 1:
#        if H[k-1] >= H[i-1]:
#          flg = 1
#    if flg == 0:
#      ans.append(i)

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
H = list(map(int, input().split()))
l = []
for i in range(M):
    A, B = map(int, input().split())
    if(H[A-1]>H[B-1]):l.append(B-1)
    elif(H[A-1]==H[B-1]):
      l.append(A-1)
      l.append(B-1)
    else:l.append(A-1)
l = list(set(l))
dellist = lambda items, indexes: [item for index, item in enumerate(items) if index not in indexes]
print(len(dellist(H,l)))

Submission status: Time Limit Exceeded

Solution code:
n,m = map(int, input().split())
heights = list(map(int, input().split()))
roads = list()
for _ in range(m):
  road = list(map(int, input().split()))
  roads.append(road)

sum = 0
for i in range(n):
  tallest = True
  for road in roads:
    if i+1 in road:
      if road.index(i+1) == 0:
        to = road[1]
      else:
        to = road[0]
      if heights[i] <= heights[to-1]:
        tallest = False
        break
  if tallest:
    sum += 1

print(sum)

Submission status: Time Limit Exceeded

Solution code:
n,m =map(int, input().split())
h = list(map(int, input().split()))
l = [input() for _ in range(m)]
list = []
for i in range(m):
  a,b =map(int, l[i].split())
  list.append([a,b])
count = 0
for j in range(n):
  near = []
  for k in range(m):
    if list[k][0] == j + 1:
      if h[j] < h[list[k][1]-1]:
        break
      near.append(h[list[k][1]-1])
    elif list[k][1] == j + 1:
      if h[j] < h[list[k][0]-1]:
        break
      near.append(h[list[k][0]-1])
  else:
    if len(near) == 0: count = count + 1
    elif h[j] > max(near): count = count + 1
    continue
print(count)

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
H = list(map(int, input().split()))
adj = set()
for i in range(M):
    a, b = map(int, input().split())
    adj.add((min(a-1, b-1), max(a-1, b-1)))

ans = 0
for i in range(N):
    u = H[i]
    check = True
    for a, b in adj:
        if i == a:
            if not u > H[b]:
                check = False
        elif i == b:
            if not u > H[a]:
                check = False
        else:
            pass
    if check:
        ans += 1
print(ans)

Submission status: Time Limit Exceeded

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

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

way = [[0 for j in range(n)] for i in range(n)]




for i in range(m):
    a,b  = map(int, input().split())
    way[a-1][b-1] += 1
    way[b-1][a-1] += 1
    
#print(way)
goodcount = 0

for i in range(n): #i本目を調べてる
    good = 1
    for j in range(n): #j本目と比べてる
        #print("!", i,j)
        if i != j and way[i][j] != 0:
            #print(height[i], height[j])
            if height[i] <= height[j]:
                good = 0
                
    if good == 1:
        goodcount += 1
        #print(i)
        
print(goodcount)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

n,m = map(int, input().split())

highs = list(map(int, input().split()))
towers = list(range(n))

d = defaultdict(list)

for i in range(m):
    v = list(map(int, input().split()))
    d[v[0]].append(v[1])
    d[v[1]].append(v[0])

count = 0
for k, v in d.items():
    nums = []
    
    if towers.count(k-1) > 0:
        towers.remove(k-1)
    for i in v:
        nums.append(highs[i-1])
    if highs[k-1] > max(nums):
        count += 1

print(count+len(towers))

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python3
# -*- coding: utf-8 -*-

import numpy as np
# from itertools import *
# from collections import *

# S = input().split()
# N = int(input().split())
# N, K = [int(x) for x in input().split()]

N, M = [int(x) for x in input().split()]

H = np.array([int(x) for x in input().split()])

Road = []
for m in range(M):
    Road.append([int(x) for x in input().split()])

Road = np.array(Road)

good = 0

for n in range(N):
    l1 = (np.ravel(Road[Road[:, 0] == n+1])-1).tolist()
    l1.extend((np.ravel(Road[Road[:, 1] == n+1])-1).tolist())
    l1 = list(set(l1))
    if len(H[l1]) == 0:
        good += 1
        continue;

    l1.remove(n)
    if max(H[l1]) < H[n]:
        good += 1

print(good)

Submission status: Time Limit Exceeded

Solution code:
from dataclasses import dataclass


@dataclass
class Tembodai:
    id: int
    height: int


@dataclass
class Route:
    frm: int
    to: int


N, M = [int(x) for x in input().strip().split(" ")]
H = [int(x) for x in input().strip().split(" ")]
AB = [
    [int(x) for x in input().strip().split(" ")]
    for _ in range(M)
]

tembodai_all = {i: Tembodai(i, h) for i, h in enumerate(H)}
route_list = []
for ab in AB:
    route_list.append(Route(ab[0] - 1, ab[1] - 1))
    route_list.append(Route(ab[1] - 1, ab[0] - 1))

ok = []
for i, t in tembodai_all.items():
    routes = [r for r in route_list if r.frm == i]
    if len(routes) == 0:
        ok.append(i)
        continue
    higher = [r for r in routes if tembodai_all[r.to].height >= t.height]
    if len(higher) == 0:
        ok.append(i)
        continue
print(len(ok))

Submission status: Time Limit Exceeded

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

G = [[0] * N for i in range(N)]
#print(G)

for i in range(M):
  a, b = [int(j) for j in input().split()]
  #print(a, b)
  G[a-1][b-1] = 1
  G[b-1][a-1] = 1

#for g in G:
#  print(g)
NG = []  
for ixa, g in enumerate(G):
  #print(g)
  ha = H[ixa]
  for ixb, gg in enumerate(g):
    if gg == 0:
      continue    
    hb = H[ixb]
    if ha <= hb:
      if ixa not in NG:
        NG.append(ixa)
        break
#print(NG)    
print(N - len(NG))

Submission status: Time Limit Exceeded

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

n, m = map(int, input().split())
h = list(map(int, input().split()))
not_good = []
for i in range(m):
    a, b = map(int, input().split())
    if h[a - 1] > h[b - 1]:  # bはダメ
        if b not in not_good:
            not_good.append(b)
    elif h[a - 1] == h[b - 1]:
        if a not in not_good:
            not_good.append(a)
        if b not in not_good:
            not_good.append(b)
    else:
        if a not in not_good:
            not_good.append(a)
ans = 0
not_good = list(set(not_good))
for i in range(1, n + 1):
    if i not in not_good:
        ans += 1
        # print(i, end=" ")
print(ans)

Submission status: Time Limit Exceeded

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

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

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

for i in N_list:
    if i in checked:
        continue
    this_h = H_list[i-1]
    other_h = 0
    row = mapMat[i-1]
    indexs = [i for i, x in enumerate(row) if x == 1]
    for ix in indexs:
        tmp = H_list[ix]
        if other_h < tmp:
            other_h = tmp
    if this_h > other_h:
        good.append(i)
        for ix in indexs:
            checked.append(ix+1)

print(len(good))

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop
from itertools import permutations, accumulate
from math import sqrt, ceil, floor
from bisect import bisect_left, bisect_right
from copy import deepcopy
from operator import itemgetter
from fractions import gcd
import sys
def I(): return int(input())  # '123' -> 123
def Is(): return map(int, input().split())  # '123 456' -> 123, 456
def LI(): return list(map(int, input().split()))  # '123 456' -> [123, 456]
def TI(): return tuple(map(int, input().split()))  # '123 456' -> (123, 456)
def IR(n): return [I() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def TIR(n): return [TI() for _ in range(n)]
def S(): return input()
def Ss(): return input().split()  # 'aa bb' -> 'aa','bb' or ['aa','bb']
def LS(): return list(input())  # 'abc123' -> ['a','b','c','1','2','3']
def SR(n): return [S() for _ in range(n)]
def SsR(n): return [Ss() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
sys.setrecursionlimit(1000000)
MOD = 1000000007
INF = float('inf')

N, M = Is()
H = LI()
AB = [[0]*N for _ in range(N)]
for i in range(M):
    a, b = Is()
    a -= 1
    b -= 1
    AB[a][b] = 1
    AB[b][a] = 1

# print(AB)
ans = 0
notgood = [False]*N

for i in range(N):
    if notgood[i]:
        continue
    for j in range(N):
        if AB[i][j] != 0:
            if H[i] > H[j]:
                notgood[j] = True
            elif H[i] < H[j]:
                notgood[i] = True
                break
            else:
                notgood[i] = True
                notgood[j] = True
                break
    else:
        ans += 1

print(ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
h=list(map(int,input().split()))
a=[]
b=[]
for i in range(m):
    aa,bb=map(int,input().split())
    a.append(aa-1)
    b.append(bb-1)
ans=0
t=[False]*n
for i in range(n):
    if(t[i]):continue
    flag=True
    for j in range(m):
        if(a[j]==i):
            if(h[i]<=h[b[j]]):
                flag=False
                break
            else:t[b[j]]=True
        if(b[j]==i):
            if(h[i]<=h[a[j]]):
                flag=False
                break
            else:t[a[j]]=True
    if(flag):
        ans+=1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N , M = map(int,input().split())
Height = [h_i for h_i in map(int,input().split())]
Roots = []
for j in range(M):
    root = [c_i for c_i in map(int,input().split())]
    #if root[0] > root[1]:
    #    root.reverse()
    Roots +=[root]
#print(Height,"\n",Roots)

connections=[]
for i in range(1,N+1):
    site = []
    for root in Roots:
        if root[0]==i:
            site+=[root[1]]
        elif root[1]==i:
            site+=[root[0]]
    connections+=[site]
#print(connections)

counter = 0
for i in range(N):
    counter2 = 0
    for site in connections[i]:
        if Height[i] <= Height[site-1]:
            counter2 += 1
    if counter2 == 0:
        counter+=1
#        print(i+1,counter2)
print(counter)