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:

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

    route = dict()
    for i in range(M):
        A, B = map(int, input().split())
        if A in route:
            route.get(A, set()).add(B)
        else:
            route[A] = set([B])
        if B in route:
            route.get(B, set()).add(A)
        else:
            route[B] = set([A])

    counter = 0
    for k, mountains in route.items():
        if H[k-1] > max([H[i-1] for i in mountains]):
            counter +=1
        
    counter += N - len(route.keys())

    print(counter)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
arr=[int(i) for i in input().split()]
hashmap=dict()
count=dict()
visited=dict()
for key in range(1,n+1):
  hashmap[key]=arr[key-1]

result=n
for i in range(m):
  a,b=map(int,input().split())
  if hashmap[a]<hashmap[b]:
    if visited.get(a)==None:
        result-=1
        visited[a]=1
  elif hashmap[b]<hashmap[a]:
    if visited.get(b)==None:
        result-=1
        visited[b]=1
  else:
      if visited.get(a)==None:
          result-=1
          visited[a]=1
      if visited.get(b)==None:
          result-=1          
          visited[b]=1
    
print(result)

Submission status: Accepted

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

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

for i in range(m):
    if l[i][1] not in x[l[i][0]-1]:
        x[l[i][0]-1].append(l[i][1])

for j in range(m):
    if l[j][0] not in x[l[j][1]-1]:
        x[l[j][1]-1].append(l[j][0])

y = 0
for a in range(n):
    for c in range(len(x[a])):
        if h[a] <= h[x[a][c]-1]:
            break
    else:
        y += 1

print(y)

Submission status: Accepted

Solution code:

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

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

Submission status: Accepted

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

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

    if h[a - 1] < h[b - 1]:
        t[a - 1] = 0
    elif h[a - 1] > h[b - 1]:
        t[b - 1] = 0
    else:
        t[a - 1] = 0
        t[b - 1] = 0

print(t.count(1))

Submission status: Accepted

Solution code:
def c():
    N, M = map(int, input().split())
    # H がグラフの頂点 0, 1, 2, 3, ..., N-1
    H = list(map(int, input().split()))

    # A,B が辺
    G = {}
    for i in range(M):
        A, B = map(int, input().split())
        G[A-1] = max(G.get(A-1, 0), H[B-1])
        G[B-1] = max(G.get(B-1, 0), H[A-1])
    cnt = 0
    for j in range(N):
        if j in G.keys() and H[j] > G[j]:
            cnt += 1
        elif j not in G.keys():
            cnt += 1
    print(cnt)


##########
if __name__ == "__main__":
    c()

Submission status: Accepted

Solution code:
n, m = map(int,input().split())
h = list(map(int,input().split()))
ab = [list(map(int,input().split())) for _ in range(m)]
result = {i + 1 for i in range(n)}

for a, b in ab:
    if h[a-1] < h[b-1]:
        result.discard(a)
    elif h[a-1] > h[b-1]:
        result.discard(b)
    else:
        result.discard(a)
        result.discard(b)

print(len(result))

Submission status: Accepted

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

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

print(n-len(noset))

Submission status: Accepted

Solution code:
N, M = map(int,input().split())
H = list(map(int,input().split()))
flag = [1] * N

for __ in range(M):
    A, B = map(int,input().split())

    if H[A - 1] < H[B - 1]:
        flag[A - 1] = 0
    elif H[A - 1] > H[B - 1]:
        flag[B - 1] = 0
    elif H[A - 1] == H[B - 1]:
        flag[A - 1] = 0
        flag[B - 1] = 0
        
print(sum(flag))

Submission status: Accepted

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

flags = [True]*n

for i in range(m):
    if h[ab[i][0]-1] < h[ab[i][1]-1]:
        flags[ab[i][0]-1] = False
    elif h[ab[i][0]-1] > h[ab[i][1]-1]:
        flags[ab[i][1]-1] = False
    else:
        flags[ab[i][0]-1] = False
        flags[ab[i][1]-1] = False
    # print(ab[i][0]-1, ab[i][1]-1)
    # print(h[ab[i][0]-1], h[ab[i][1]-1])
    # print(flags)
print(flags.count(True))

Submission status: Accepted

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

ans = [0]*n
for w in way:
    a = w[0]
    b = w[1]
    if h[a-1] < h[b-1]:
        ans[a-1] += 1
    elif h[a-1] > h[b-1]:
        ans[b-1] += 1
    else:
        ans[a-1] += 1
        ans[b-1] += 1

count = 0
for a in ans:
    if a == 0:
        count += 1
print(count)

Submission status: Accepted

Solution code:
# ABC166 C

def main():
    n, m = map(int, input().split())
    H = list(map(int, input().split()))
    
    towers = []
    for _ in range(n):
        towers.append([])
    
    good_tower_count = 0

    for _ in range(m):
        a, b = map(int, input().split())
        #print(a, b)
        towers[a-1].append(b-1)
        towers[b-1].append(a-1)
        #print(towers)
    
    # for each of the towers
    for i in range(n):
        good_flags = []

        # check if the tower is taller than the neighbour towers
        for j in range(len(towers[i])):
            if H[i] > H[towers[i][j]]:
                good_flags.append(True)
            else:
                good_flags.append(False)
        
        if (False not in good_flags) or len(towers[i]) == 0:
            good_tower_count += 1
            #print(i)
    
    print(good_tower_count)
    


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def get_unique_list(seq):
    seen = []
    return [x for x in seq if x not in seen and not seen.append(x)]

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

AB_unique=list(map(list, set(map(tuple, AB))))

AB_road=[[] for i in range(N)]
for AB in AB_unique:
    if H[AB[0]-1] > H[AB[1]-1]:
        AB_road[AB[1]-1].append(AB[0])
    elif H[AB[0]-1] < H[AB[1]-1]:
        AB_road[AB[0]-1].append(AB[1])
    else:
        AB_road[AB[1]-1].append(AB[0])
        AB_road[AB[0]-1].append(AB[1])

print(AB_road.count([]))

Submission status: Accepted

Solution code:
from collections import deque

N,M = map(int,input().split())
H = [0] + [int(i) for i in input().split()]

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

G = {}

for i in range(1,N+1):
    G[i] = []
for i in range(M):
    G[data[i][0]].append(data[i][1])
    G[data[i][1]].append(data[i][0])

ans = 0
for i in range(1,N+1):
    for j in G[i]:
        if H[i] > H[j]:
            continue
        else:
            break
    else:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
N, M = list(map(int, input().split()))
H = list(map(int, input().split()))
A_B=[]
for i in range(M):
  a, b = list(map(int, input().split()))
  A_B.append([a,b])
flag=[1 for i in range(N)]
for i in range(len(A_B)):
  if H[A_B[i][0]-1] - H[A_B[i][1]-1] >0:
    flag[A_B[i][0]-1] *= 1
    flag[A_B[i][1]-1] *= 0
  elif H[A_B[i][0]-1] - H[A_B[i][1]-1]==0:
    flag[A_B[i][0]-1] *= 0
    flag[A_B[i][1]-1] *= 0
  else:
    flag[A_B[i][0]-1] *= 0
    flag[A_B[i][1]-1] *= 1
print(sum(flag))

Submission status: Accepted

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

Submission status: Accepted

Solution code:

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

H = list(map(int, input().split()))
E = [[] for i in range(N)]

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


Good = [True for i in range(N)]
for i in range(N):
    for e in E[i]:
        if H[e] >= H[i]:
            Good[i] = False

print(sum(Good))

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
h = [int(x) for x in input().split()]
ls = []
for _ in range(m):
    ls.append([int(x) for x in input().split()])


obscanreach = [[] for _ in range(n)]
for x in ls:
    obscanreach[x[0]-1].append(x[1])
    obscanreach[x[1]-1].append(x[0])

res = 0
for i,x in enumerate(obscanreach):
    check = 0
    if not x:
        res += 1
        continue
    for ev in x:
        check = max(check, h[ev-1])
    if h[i] > check:
        res += 1
print(res)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
height = list(map(int, input().split()))
anslist = [1] * n
for x in range(m):
    a, b = map(int, input().split())
    if height[a - 1] == height[b - 1]:
        anslist[a - 1] = 0
        anslist[b - 1] = 0
    elif height[a - 1] < height[b - 1]: anslist[a - 1] = 0
    else: anslist[b - 1] = 0
print(sum(anslist))

Submission status: Accepted

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

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

good = [1 for j in range(n)] 


for i in range(m):
    a,b  = map(int, input().split())
    
    if height[a-1] >= height[b-1]:
        good[b-1] = 0
    if height[a-1] <= height[b-1]:
        good[a-1] = 0

ans = good.count(1)
print(ans)

Submission status: Accepted

Solution code:
def main():
    N,M = map(int,input().split())
    H = list(map(int, input().split()))
    AB = [list(map(int, input().split())) for _ in range(M)]
    ans = [0 for i in range(N)]
 
    for data in AB:
        if H[data[0]-1] <= H[data[1]-1]:
            ans[data[0]-1] = 1
        if H[data[0]-1] >= H[data[1]-1]:
            ans[data[1]-1] = 1
 
    print(ans.count(0))
 
 
if __name__ == "__main__":
    main()

Submission status: Accepted

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

candidates = {}
for i in range(m):
    x, y = map(int, input().split(" "))

    if h[x - 1] <= h[y -1]:
        candidates[x] = False
    if h[x - 1] >= h[y -1]:
        candidates[y] = False

ans = 0
for i in range(1, n + 1):
    is_highest = candidates.get(i, True)
    if is_highest:
        ans += 1

print(ans)

Submission status: Accepted

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

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

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

lists = []

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

count = 0

for i in range(N):
    if highest[i] == i+1:
        count += 1

print(count)

Submission status: Accepted

Solution code:
N,M = map(int, input().split())
H = [int(i) for i in input().split()]
edge = [[] for _ in range(N)]
for _ in range(M):
    a,b = map(int, input().split())
    edge[a-1].append(b-1)
    edge[b-1].append(a-1)

ans = 0
for v in range(N):
    flag = False
    for w in edge[v]:
        if H[v] <= H[w]:
            flag = True
            break
    if flag: continue
    ans += 1

print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

for x in range(n):
    if k[x] == 100:
        ans += 1

print(str(ans))

Submission status: Accepted

Solution code:
# C - Peaks

N, M = map(int, input().split())
H = [int(h) for h in input().split()]

mapping = [[] for _ in range(N)]
for _ in range(M):
    i, j = map(int, input().split())
    mapping[i - 1].append(j - 1)
    mapping[j - 1].append(i - 1)

cnt = 0
for i in range(N):
    ls = mapping[i]
    for j in ls:
        if H[i] <= H[j]:
            break
    else:
        cnt += 1

print(cnt)

Submission status: Accepted

Solution code:
s = input()

N = int(s.split()[0])
M = int(s.split()[1])

H = input().split()

tenbo = list(range(1,N+1))
bad_tenbo = []

for i in range(M):
  road = input().split()
  A = int(road[0])
  B = int(road[1])
  HA = int(H[A-1])
  HB = int(H[B-1])
  if HA > HB:
    bad_tenbo.append(B)
  elif HA == HB:
    bad_tenbo.append(A)
    bad_tenbo.append(B)
  elif HA < HB:
    bad_tenbo.append(A)
    
result = list(set(tenbo) - set(bad_tenbo))
    
print(len(result))

Submission status: Accepted

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

list_num = [[] for i in range(n)]

for i in range(m):
  x,y = map(int, input().split())
  list_num[x - 1].append(y)
  list_num[y - 1].append(x)

count = 0

for i in range(n):
  check = 1
  for j in list_num[i]:
    if(h[i] <= h[j - 1]):
      check = 0
      break

  if(check == 1):
    count += 1

print(count)

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_ = map(int, input().split())
    a_ -= 1
    b_ -= 1
    if h[a_] == h[b_]:
        if a_ in good:
            good.remove(a_)
        if b_ in good:
            good.remove(b_)
    elif h[a_] < h[b_]:
        if a_ in good:
            good.remove(a_)
    else:
        if b_ in good:
            good.remove(b_)
print(len(good))

Submission status: Accepted

Solution code:
#!/usr/bin/env python
import sys
from collections import Counter
from itertools import permutations, combinations
#from fractions import gcd
from math import gcd
from math import ceil, floor
import bisect
sys.setrecursionlimit(10 ** 6)
inf = float("inf")

def input():
    return sys.stdin.readline()[:-1]

def main():
    n, m = map(int, input().split())
    H = tuple(map(int, input().split()))
    AB = [tuple(map(int, input().split())) for _ in range(m)]

    ans = [True] * n
    for i in range(m):
        if H[AB[i][0]-1] > H[AB[i][1]-1]:
            ans[AB[i][1]-1] = False
        elif H[AB[i][0]-1] < H[AB[i][1]-1]:
            ans[AB[i][0]-1] = False
        elif H[AB[i][0]-1] == H[AB[i][1]-1]:
            ans[AB[i][0]-1] = False
            ans[AB[i][1]-1] = False

    print(sum(ans))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
H = list(map(int, input().split()))
r = [True for _ in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    if H[a - 1] > H[b - 1]:
        r[b - 1] = False
    elif H[a - 1] < H[b - 1]:
        r[a - 1] = False
    else:
        r[a - 1], r[b - 1] = False, False

print(sum(r))

Submission status: Accepted

Solution code:
N,M = map(int,input().split(" "))
H = input().split(" ")
for i in range(N):
  H[i]=[int(H[i]),1]
for j in range(M):
  A,B = map(int,input().split(" "))
  if H[A-1][0]>H[B-1][0]:
    H[B-1][1]=0
  elif H[A-1][0]<H[B-1][0]:
    H[A-1][1]=0
  elif H[A-1][0]==H[B-1][0]:
    H[A-1][1]=0
    H[B-1][1]=0
compte=0
for k in range(N):
  if H[k][1]==1:
    compte+=1
print(compte)

Submission status: Accepted

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=[]
for i in path_list :
    if H_list[i[0]-1]>H_list[i[1]-1] :
        c.append(i[1])
    elif H_list[i[0]-1]<H_list[i[1]-1]  :
        c.append(i[0])
    else :
        c.append(i[0])
        c.append(i[1])
k=list(set(c))
print(N-len(k))

Submission status: Accepted

Solution code:
import numpy as np
n, m = (int(x) for x in input().split())
h = [int(x) for x in input().split()]
b = np.zeros(n)
for i in range(m):
    s, k = (int(x) for x in input().split())
    if h[s-1] < h[k-1]:
        b[s-1] = 1
    elif h[k-1] < h[s-1]:
        b[k-1] = 1
    else:
        b[s-1] = 1
        b[k-1] = 1

print(np.count_nonzero(b==0))

Submission status: Accepted

Solution code:
N,M = map(int,(input().split()))
high = list(map(int, input().split()))
high.insert(0,0)
good_flg = [0]
for i in range(N):
  good_flg.append(1)
for i in range(M):
  A,B = map(int,(input().split()))
  if(high[A]>high[B]):
    good_flg[B]=0
  elif(high[A]<high[B]):
    good_flg[A]=0
  else:
    good_flg[A]=0
    good_flg[B]=0

print(good_flg.count(1))

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

l = [1] * N
for i in range(M):
    if H[A[i]-1] >= H[B[i]-1]:
        l[B[i]-1] = 0
    if H[A[i]-1] <= H[B[i]-1]:
        l[A[i]-1] = 0
print(sum(l))

Submission status: Accepted

Solution code:
R = lambda: map(int, input().split())
n, m = R()
h = [None, *R()]
g = [0] + [1] * n
for _ in range(m):
  a, b = R()
  if h[a] <= h[b]:
    g[a] = 0
  if h[b] <= h[a]:
    g[b] = 0
print(sum(g))

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)

All = [True]*N

for i in range(M):
    a = A[i]-1
    b = B[i]-1
    if H[a] > H[b]:
        All[b] = False
    elif H[a] < H[b]:
        All[a] = False
    else:
        All[a] = False
        All[b] = False

print(sum(All))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

def main():
    N, M = map(int, readline().split())
    H_ex = list(map(int, readline().split()))
    m = map(int, read().split())
    AB = zip(m, m)
    l = [[]for _ in range(N+1)]
    ans = 0
    H = [0]
    H.extend(H_ex)
    for A, B in AB:
        l[A].append(B)
        l[B].append(A)
    for i in range(1,N+1):
        for j in l[i]:
            if H[i] <= H[j]:
                break
        else:
            ans += 1
    print(ans)
    return

if __name__ == '__main__':
    main()

Submission status: Accepted

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

#A=list()
#B=list()
ans=[0]*N


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

for i in range(M):
    At,Bt=map(int,input().split())
#    A.append(At-1)
#    B.append(Bt-1)

    if(H[Bt-1]<=H[At-1]):
        ans[Bt-1]=1
    if(H[At-1]<=H[Bt-1]):
        ans[At-1]=1
    
print(ans.count(0))

Submission status: Accepted

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

l = set()
for i in range(n):
    l.add(i+1)

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

s = set()

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

#    print(s)

ans = list(l - s)
#print(ans)
print(len(ans))

Submission status: Accepted

Solution code:
import collections

N,M = map(int,input().split())
H = [int(h) for h in input().split()]
l = []
for m in range(M):
    a,b = map(int,input().split())
    if H[a-1] > H[b-1]:
        l.append(b)
    elif H[a-1] < H[b-1]:
        l.append(a)
    else:
        l.append(a)
        l.append(b)

print(N-len(collections.Counter(l)))

Submission status: Accepted

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

Submission status: Accepted

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

e = [True]*n
ten = []
for i,a in enumerate(h):
    ten.append((a,i))

for a,i in sorted(ten,reverse=True):
    if e[i] == True:
        for r in road[i]:
            if a > h[r]:
                e[r] = False
            else:
                e[i] = False
            
print(e.count(True))

Submission status: Accepted

Solution code:
#C問題
N,M = map(int, input().split())
H = input().split()
result = [True] * N
H_i = [int(s) for s in H]
bothCount = 0
for i in range(M):
    A,B = map(int, input().split())
    if(H_i[A-1] > H_i[B-1]):
        #AがBよりも高かったらAがいい展望台
        if(result[B-1] == True):
            result[B-1] = False
    elif(H_i[A-1] < H_i[B-1]):
        if(result[A-1] == True):
            result[A-1] = False
    else:
        result[A-1] = False
        result[B-1] = False
print(result.count(True))

Submission status: Accepted

Solution code:
import sys

if __name__ == '__main__':
    n, m = list(map(lambda x: int(x), sys.stdin.readline().split(' ')))
    h = list(map(lambda x: int(x), sys.stdin.readline().split(' ')))
    # matrix = {}
    # matrix = [[0 for i in range(n)] for j in range(n)]
    matrix = [[] for j in range(n)]

    for i in range(m):
        a, b = list(map(lambda x: int(x), sys.stdin.readline().split(' ')))
        a, b = a-1, b-1
        # matrix[a] = matrix.get(a, []) + [b]
        # matrix[b] = matrix.get(b, []) + [a]
        # matrix[a][b] = 1
        # matrix[b][a] = 1
        matrix[a].append(b)
        matrix[b].append(a)

    bads = {}
    good = 0
    # 展望台iが良い展望台か
    for i in range(n):
        if bads.get(i, 0) == 1:
            continue
        # for t in matrix.get(i, []):
        for t in matrix[i]:
            if h[i] <= h[t]:
                break
            else:
                # 展望台tはもはや良い展望台でない
                if t > i:
                    bads[t] = 1
        else:
            good += 1
    print(good)

# matrixを疎行列にする
# 判定順をソートする

Submission status: Accepted

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

n = a[0]
m = a[1]

all_kind = {i for i in range(1, n+1)}

for i in range(m):
    comb = list(map(int,input().split()))

    if(h[comb[0]-1] > h[comb[1]-1]):
        all_kind.discard(comb[1])
    elif(h[comb[0]-1] == h[comb[1]-1]):
        all_kind.discard(comb[0])
        all_kind.discard(comb[1])
    else:
        all_kind.discard(comb[0])

print(len(all_kind))

Submission status: Accepted

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

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

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

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


c=0
for i,it in enumerate(dist[1:]):
    hi = list(map(lambda x:H[x-1],it))

    if (list(filter(lambda x:H[i]<=x,hi)).__len__()==0):
        c+=1
    
print(c)

Submission status: Accepted

Solution code:
n,m=map(int, input().split())
h=list(map(int, input().split()))
dic = {}
ng = set()
chk = set()

for i in range(m):
  a,b=map(int, input().split())
  chk.add(a)
  chk.add(b)
  if h[a-1] == h[b-1]:
    ng.add(a)
    ng.add(b)
    if str(b) in dic:
      dic.pop(str(b))
    if str(a) in dic:
      dic.pop(str(a))
  elif h[a-1] > h[b-1]:
    if not a in ng:
      dic[str(a)] = h[a-1]
    ng.add(b)
    if str(b) in dic:
      dic.pop(str(b))
  else:
    if not b in ng:
      dic[str(b)] = h[b-1]
    ng.add(a)
    if str(a) in dic:
      dic.pop(str(a))
    
print(len(dic) + (n-len(chk)))

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
h=[0]*n
r=[1]*n
h[:]=map(int,input().split())
for ii in range(m):
  a,b=map(lambda x: int(x)-1,input().split())
  if h[a]>=h[b]:
    r[b]=0
  if h[b]>=h[a]:
    r[a]=0
print(sum(r))

Submission status: Accepted

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

print(sum(nn))

Submission status: Accepted

Solution code:
n,m = map(int, input().split())
h_li = list(map(int, input().split()))
ans = [0]*n
goods = list()
bads = list()

for i in range(m):
  a, b = map(int, input().split())
  good = max(h_li[a-1], h_li[b-1])
  bad = min(h_li[a-1], h_li[b-1])
  if h_li[a-1] == h_li[b-1]:
    bads.append(a-1)
    bads.append(b-1)
    continue
  if good == h_li[a-1]:
    good_i = a-1
    bad_i = b-1
  else:
    good_i = b-1
    bad_i = a-1
  goods.append(good_i)
  bads.append(bad_i)

  
all_s = set(goods + bads)
goods = set(goods)
bads = set(bads)

no_paths = n - len(all_s)
bests = [ten for ten in goods if ten not in bads]

print(len(bests) + no_paths)

Submission status: Accepted

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

sm = []
for i in range(M):
    A, B = map(int, input().split())
    if H[A-1] <= H[B-1] :
      sm.append(A)
    if H[B-1] <= H[A-1] :
      sm.append(B)
print(N - len(set(sm)))

Submission status: Accepted

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

roads = [[int(i) for i in input().split()] for j in range(M)]
roads2 = [[] for i in range(N)]

for spots in roads:
    roads2[spots[0]-1].append(spots[1])
    roads2[spots[1]-1].append(spots[0])

ans = 0
for spot in range(1, N+1):
    good = True
    for i in roads2[spot-1]:
        if H[spot-1] <= H[i-1]:
            good = False
            break
    if good:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
graph = dict(zip(
    list (range(1, N+1)),
    [set() for i in range(N)]
))
height=list(map(int, input().split()))

for i in range(M):
    src, dest = map(int, input().split())
    graph[src].add(dest)
    graph[dest].add(src)


count = 0
for currNode in graph:
    flag = True
    for node in graph[currNode]:
        if height[currNode-1] <= height[node-1]:
            flag = False
    
    if flag:
        count += 1


print(count)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# n,m = map(int,sys.stdin.readline().split())
# a = list(map(int,sys.stdin.readline().split()))
# a = [sys.stdin.readline() for _ in range(n)]
# s = sys.stdin.readline().rstrip()
# n = int(sys.stdin.readline())
import sys,bisect,math,collections
sys.setrecursionlimit(15000)

N,M = map(int,sys.stdin.readline().split())
h = list(map(int,sys.stdin.readline().split()))
good = [1]*N

for _ in range(M):
    a,b = list(map(int,sys.stdin.readline().split()))
    if h[a-1] > h[b-1]:
        good[b-1] = 0
    elif h[a-1] < h[b-1]:
        good[a-1] = 0
    else:# h[a-1] == h[b-1]:
        good[a-1] = 0
        good[b-1] = 0
#print(good)
print(sum(good))

Submission status: Accepted

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

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

ans =[1]*N

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

    if Peaks[a]>Peaks[b]:
        ans[b]=0
    elif Peaks[a]<Peaks[b]:
        ans[a]=0
    else:
        ans[a]=0
        ans[b]=0

print(sum(ans))

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
# [[展望台の高さ, 道の数, 自分より高い展望台がない],[], ...] を
# ループの中で更新してくこととする
info_list = list()
for h in map(int, input().split()):
    info_list.append([h, 0, True])

for i in range(M):
    ai, bi = map(int, input().split())
    # 道の数更新
    info_list[ai - 1][1] += 1
    info_list[bi - 1][1] += 1
    # 高い展望台あるかどうか更新
    # print(info_list[ai - 1][0])
    # print(info_list[bi - 1][0])
    if info_list[ai - 1][0] < info_list[bi - 1][0]:
        # print("a")
        info_list[ai - 1][2] = False
    elif info_list[ai - 1][0] > info_list[bi - 1][0]:
        # print("b")
        info_list[bi - 1][2] = False
    else:
        # print("a=b")
        # 問題分より同じ高さの場合はどちらも良い展望台はではない解釈した
        info_list[ai - 1][2] = False
        info_list[bi - 1][2] = False
    # print(info_list)


result = len([i for i in info_list if i[2]])
print(result)