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()))
ans = []
for j in H:
    ans.append(j)
for i in range(m):
    a, b = map(int, input().split())
    if H[a-1] == H[b-1]:
        ans[a-1] = "low"
        ans[b-1] = "low"
    elif H[a-1] > H[b-1]:
        ans[b-1] = "low"
    elif H[a-1] < H[b-1]:
        ans[a-1] = "low"
print(len(H) - ans.count("low"))

Submission status: Accepted

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

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

print(ans.count(1))

Submission status: Accepted

Solution code:
import collections

N, M = map(int,input().split())
H = list(map(int,input().split()))
a = []
b = []
loser = []

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

    if H[a[i]-1] > H[b[i]-1]:
        loser.append(b[i])

    elif H[a[i]-1] == H[b[i]-1]:
        loser.append(b[i])
        loser.append(a[i])

    elif H[a[i]-1] < H[b[i]-1]:
        loser.append(a[i])

X = len(collections.Counter(loser))
print(N-X)

Submission status: Accepted

Solution code:
g = set()
al  = set()
e = set()
lists = list(map(int, input().split()))
h = list(map(int, input().split()))
for j in range(lists[0]):
  e.add(j+1)
for i in range(lists[1]):
    a,b= map(int, input().split())
    al.add(a)
    al.add(b)
    if h[a-1] > h[b-1]:
        g.add(b)

       
    elif h[a-1] < h[b-1]:
        g.add(a)


    else:

      
        g.add(a)
        g.add(b)
        

    
denai = e - al 
s1 = e - g
ans =  s1 | denai

print(len(ans))

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline
N, M = map(int, readline().split())
H = list(map(int, readline().split()))
Edge = [[] for _ in range(N)]
table = [1]*N
for _ in range(M):
    a, b = map(int, readline().split())
    a -= 1
    b -= 1
    if H[a] == H[b]:
        table[a] = 0
        table[b] = 0
    elif H[a] > H[b]:
        table[b] = 0
    else:
        table[a] = 0
print(sum(table))

Submission status: Accepted

Solution code:
import itertools
from collections import deque,defaultdict,Counter
from itertools import accumulate
import bisect
from heapq import heappop,heappush,heapify
import math
from copy import deepcopy
import queue
#import sympy as syp(素因数分解とか)
Mod = 1000000007
  
def sieve_of_eratosthenes(n):
    if not isinstance(n,int):
        raise TypeError("n is not int")
    if n<2:
        raise ValueError("n is not effective")
    prime = [1]*(n+1)
    for i in range(2,int(math.sqrt(n))+1):
        if prime[i] == 1:
            for j in range(2*i,n+1):
                if j%i == 0:
                    prime[j] = 0
    res = []
    for i in range(2,n+1):
        if prime[i] == 1:
            res.append(i)
    return res

 
class UnionFind:
    def __init__(self,n):
        self.parent = [i for i in range(n+1)]
        self.rank = [0 for i in range(n+1)]
    
    def findroot(self,x):
        if x == self.parent[x]:
            return x
        else:
            y = self.parent[x]
            y = self.findroot(self.parent[x])
            return y
    
    def union(self,x,y):
        px = self.findroot(x)
        py = self.findroot(y)
        if px < py:
            self.parent[py] = px
        else:
            self.parent[px] = py
 
    def same_group_or_no(self,x,y):
        return self.findroot(x) == self.findroot(y)

def main():  #startline-------------------------------------------
    n, m = map(int, input().split())
    h = list(map(int, input().split()))
    ab = [list(map(int, input().split())) for i in range(m)]
    path = [[] for i in range(n)]
    ans = 0
    for i in range(m):
        path[ab[i][0]-1].append(ab[i][1]-1)
        path[ab[i][1]-1].append(ab[i][0]-1)
    for i in path:
        if not (i):
            i.append(-1)
    for i, ele in enumerate(path):
        if ele[0] == -1:
            ans += 1  #一本の道を使ってたどり着ける展望台がない
            continue
        high = []
        for j in ele:
            high.append(h[j])
        if h[i] > max(high):
            ans += 1
    print(ans)



if __name__ == "__main__":
    main() #endline===============================================

Submission status: Accepted

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

for p in P:
    if H[int(p[0])-1] < H[int(p[1])-1]:
        try:
            candi[int(p[0])-1] = 0
        except ValueError:
            pass
    elif H[int(p[0])-1] == H[int(p[1])-1]:
        try:
            candi[int(p[0])-1] = 0
            candi[int(p[1])-1] = 0
        except ValueError:
            pass
    else:
        try:
            candi[int(p[1])-1] = 0
        except ValueError:
            pass
print(str(int(N) - candi.count(0)))

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
H = list(map(int, input().split()))
A=[0]*M
B=[0]*M
Nset=set(range(N))

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

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
H=list(map(int,input().split()))
T=[0]*N
ans=0
li=[list(map(int,input().split())) for _ in range(M)]
for l in li:
  if H[l[0]-1]>H[l[1]-1]:
    T[l[0]-1]+=1
    T[l[1]-1]-=10**5
  if H[l[0]-1]<H[l[1]-1]:
    T[l[0]-1]-=10**5
    T[l[1]-1]+=1
  if H[l[0]-1]==H[l[1]-1]:
    T[l[0]-1]=T[l[1]-1]=-(10**5)
for t in T:
  if t>=0:
    ans+=1
print(ans)

Submission status: Accepted

Solution code:
def getN():
    return int(input())

def getIntList():
    return list(map(int, input().split()))


def main():

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

    H = getIntList()

    # input AB
    ABlist = []
    for i in range(M):
        AB = list(map(int,input().split()))
        ABlist.append(AB)
    
    
    wlist = [1] * N
    for i in ABlist:
        if H[i[0]-1] < H[i[1]-1]:
            wlist[i[0]-1] = 0
        elif H[i[0]-1] == H[i[1]-1]:
            wlist[i[0]-1] = 0
            wlist[i[1]-1] = 0
        else:
            wlist[i[1]-1] = 0

    #print(wlist)
    print(wlist.count(1))

    return

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:

def start():
    n, m = input().split()
    n = int(n)
    m = int(m)
    hs = list(map(int, input().split()))
    bs = [0 for i in range(n)]
    for i in range(m):
        a, b = input().split()
        a = int(a) - 1
        b = int(b) - 1
        if hs[a] > hs[b]:
            bs[b] = -1
        elif hs[a] < hs[b]:
            bs[a] = -1
        else:
            bs[a] = -1
            bs[b] = -1
    n = bs.count(0)
    print(n)


if __name__ == '__main__':
    start()

Submission status: Accepted

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

for n in range(N):
    L = len(roots[n])
    for l in range(L):
        if H[n] <= H[roots[n][l]]:
            good -=1
            break
    else:
        continue
print(good)

Submission status: Accepted

Solution code:
import sys
n, m = map(int, sys.stdin.readline().split())
li = list(map(int, sys.stdin.readline().split()))
li2 = ['a']*n
for _ in range(m):
  i, k = map(int, sys.stdin.readline().split())
  k -= 1
  i -= 1
  if li[k] - li[i] > 0:
    li2[i] = 'F'
    if li2[k] == 'a':
      li2[k] = 'T'
  elif li[k] == li[i]:
    li2[i] = 'F'
    li2[k] = 'F'
  else:
    li2[k] = 'F'
    if li2[i] == 'a':
      li2[i] = 'T'
print(n-li2.count('F'))

Submission status: Accepted

Solution code:
import numpy as np

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

ok=np.ones(N)
for i in range(M):
    if H[A[i][0]-1]>H[A[i][1]-1]:
        ok[A[i][1]-1]=0
    elif H[A[i][0]-1]==H[A[i][1]-1]:
        ok[A[i][0]-1]=0
        ok[A[i][1]-1]=0
    else:
        ok[A[i][0]-1]=0
print(int(np.sum(ok)))

Submission status: Accepted

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

bads = set([])
for _ in range(m):
    (s, d) = list(map(int, input().split()))
    if hights[s-1] < hights[d-1]:
        bads.add(s)
    elif hights[s-1] > hights[d-1]:
        bads.add(d)
    elif hights[s-1] == hights[d-1]:
        bads.add(s)
        bads.add(d)
print(len(hights) - len(bads))

Submission status: Accepted

Solution code:
from copy import copy, deepcopy
from collections import Counter
from math import sqrt, floor, factorial
from itertools import permutations, combinations, combinations_with_replacement
from operator import mul
from functools import reduce

MOD = 10**9 + 7
INF = float('inf')

ans = 0

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

T = [[] for i in range(N)]

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

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

for i in range(N):
    if len(T[i]) == 0:
        ans += 1
    else:
        if H[i] > max(list(map(lambda x: H[x], T[i]))):
            ans += 1

print(ans)

Submission status: Accepted

Solution code:
n, m = map(int, input().split(" "))
number = [[] for _ in range(n)]
height = list(map(int, input().split(" ")))
result = 0
for i in range(0, m):
    a, b = map(int, input().split(" "))
    number[b - 1].append(a - 1)
    number[a - 1].append(b - 1)
for i in range(0, n):
    if (len(number[i]) == 0):
        result += 1
    else:
        sig = 1
        for k in number[i]:
            if (height[i] <= height[k]):
                sig = 0
                break
        if sig == 1:
            result+=1
print(result)

Submission status: Accepted

Solution code:
import numpy as np
N,M=list(map(int,input().split()))
H=list(map(int,input().split()))
F=[0]*len(H)
for i in range(M):
  A,B=list(map(int,input().split()))
  if(H[A-1]<H[B-1]):
    F[A-1]=1
  elif(H[A-1]>H[B-1]):
    F[B-1]=1
  else:
    F[B-1]=1
    F[A-1]=1
print(F.count(0))

Submission status: Accepted

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

Submission status: Accepted

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




if __name__=="__main__":
    main()

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
h=list(map(int,input().split()))
street=[]
for i in range(m):
    street.append(list(map(int,input().split())))
not_taller=[]
for i in range(m):
    if h[street[i][0]-1]==h[street[i][1]-1]:
        not_taller.append(street[i][0])
        not_taller.append(street[i][1])
    elif h[street[i][0]-1]>h[street[i][1]-1]:
        not_taller.append(street[i][1])
    else:
        not_taller.append(street[i][0])
print(n-len(set(not_taller)))

Submission status: Accepted

Solution code:
ma = lambda :map(int,input().split())
ni = lambda:int(input())

n,m = ma()
H = list(ma())
Hm = [True]*n
ab = []
tr = [[] for i in range(n)]
for i in range(m):
    a,b = ma()
    tr[a-1].append(b-1)
    tr[b-1].append(a-1)
    if H[a-1] > H[b-1]:
        Hm[b-1] = False
    elif H[a-1] < H[b-1]:
        Hm[a-1] =False
    else:
        Hm[b-1] = False
        Hm[a-1] = False
ans = 0
for f in Hm:
    if f:ans+=1
print(ans)

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
H = list(map(int,input().split()))
br = {num+1:[] for num in range(N)}
for i in range(M):
    a,b = map(int,input().split())
    br[a].append(b)
    br[b].append(a)
cnt = 0
for i in range(N):
    height = []
    if len(br[i+1])==0:
        cnt+=1
        continue
    for j in br[i+1]:
        height.append(H[j-1])
    if H[i]>max(height):
        cnt+=1
print(cnt)

Submission status: Accepted

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

competitor_H = {}

for m in range(M):
    A, B = map(int, input().split())
    
    if A-1 not in competitor_H.keys():
        competitor_H[A-1] = []
    competitor_H[A-1].append(H[B-1])
    
    if B-1 not in competitor_H.keys():
        competitor_H[B-1] = []
    competitor_H[B-1].append(H[A-1])

countGood = 0
for i in range(N):
    if i not in competitor_H.keys():
        countGood += 1
    elif H[i] > max(competitor_H[i]):
        countGood += 1
print(countGood)

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
ans = [1]*n
h = input().split()
h_int = [int(s) for s in h]
cou = 0
 
for i in range(m):
  x,y = map(int,input().split())
  if h_int[x-1] >= h_int[y-1]:
    ans[y-1] = 0
  if h_int[y-1] >= h_int[x-1]:
    ans[x-1] = 0
 
for i in range(n):
  if ans[i] == 1:
    cou += 1
print(cou)

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())
C=[]
for j in range(M):
  if H[A[j]-1]>H[B[j]-1]:
               C.append(B[j])
  elif H[A[j]-1]==H[B[j]-1]:
               C.append(A[j])
               C.append(B[j])
  else:
               C.append(A[j])
c=set(C)
d=list(c)               
print(N-len(d))

Submission status: Accepted

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はダメ
        not_good.append(b)
    elif h[a - 1] == h[b - 1]:
        not_good.append(a)
        not_good.append(b)
    else:
        not_good.append(a)
ans = 0
not_good = list(set(not_good))
not_good.sort()
# print(not_good)
idx = 0
for i in range(1, n + 1):
    if i < not_good[idx]:
        ans += 1
        # print(i, end=" ")
    elif i == not_good[idx]:
        idx += 1
        if idx == len(not_good):
            ans += n - i
            break
    else:
        pass
print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

result = sum(i == 1 for i in ans)
print(result)

Submission status: Accepted

Solution code:
def main():
    n,m = (int(x) for x in input().split())
    h = [int(x) for x in input().split()]
    r = [[h[i]] for i in range(n)]
    for i in range(m):
        a,b = (int(x)-1 for x in input().split())
        r[a].append(h[b])
        r[b].append(h[a])

    cnt = 0
    for i in range(n):
        if max(r[i]) == h[i] and r[i].count(h[i]) == 1:
            cnt += 1
    print(cnt)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

t = [0]*m
for j in range(m):
    t[j] = tuple(map(int, input().split()))

count = 0

for i in range(m):
    if h[t[i][0]-1] > h[t[i][1]-1]:
        hc[t[i][1]-1] = 0
    elif h[t[i][0]-1] < h[t[i][1]-1]:
        hc[t[i][0]-1] = 0
    else:
        hc[t[i][0]-1] = 0
        hc[t[i][1]-1] = 0

for i in range(n):
    if hc[i] == 0:
        continue
    else:
        count += 1

print(count)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
h = list(map(int, input().split()))
a = [list(map(int, input().split())) for _ in range(m)]
b = set()
for i, j in a:
    if h[i-1] < h[j-1]:
        b.add(i-1)
    elif h[i-1] > h[j-1]:
        b.add(j-1)
    else:
        b.add(j-1)
        b.add(i-1)


print(n-len(b))

Submission status: Accepted

Solution code:
nm = list(map(int, input().split()))
n = nm[0]
m = nm[1]
h = list(map(int, input().split()))
observatories = [[] for i in range(n)]
ans = 0
for i in range(m):
  ab = list(map(int, input().split()))
  a = ab[0] - 1
  b = ab[1] - 1
  observatories[a].append(b)
  observatories[b].append(a)
for j in range(len(observatories)):
  ans = ans + 1
  h_j = h[j]
  for k in observatories[j]:
    if h[k] >= h_j:
      ans = ans - 1
      break
print(ans)

Submission status: Accepted

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

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


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

print(count)

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
 if H[B-1]<=H[A-1]:
  L[B-1]+=1
b=0
for i in L:
 if i==0:
  b+=1
print(b)

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)

x = 0
bad = []

while x < M:
    if H[A[x]-1] > H[B[x]-1]:
        bad.append(B[x])
    elif H[A[x]-1] < H[B[x]-1]:
        bad.append(A[x])
    else:
        bad.append(A[x])
        bad.append(B[x])

    x += 1


print(N-len(set(bad)))

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)]
tf = [3 for _ in range(n)]
for i in ab:
    if h[i[0] - 1] > h[i[-1] - 1]:
        if tf[i[0] - 1] == 3:
            tf[i[0] - 1] = True
            tf[i[-1] - 1] = False
        else:
            tf[i[-1] - 1] = False
    elif h[i[0] - 1] < h[i[-1] - 1]:
        if tf[i[-1] - 1] == 3:
            tf[i[-1] - 1] = True
            tf[i[0] - 1] = False
        else:
            tf[i[0] - 1] = False
    elif h[i[0] - 1] == h[i[-1] - 1]:
        tf[i[0] - 1] = False
        tf[i[-1] - 1] = False
cnt = 0
for j in tf:
    if j == True:
        cnt += 1
    elif j == 3:
        cnt += 1
print(cnt)

Submission status: Accepted

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

Submission status: Accepted

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

print(x)

Submission status: Accepted

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

import sys
import pprint

sys.setrecursionlimit(10 ** 6)

class Logger:
	def __init__(self, debug):
		self.debug = debug
	def print(self, *args):
		if self.debug:
			pprint.pprint(args)


def main():
	log = Logger(0)
	n, m = map(int, sys.stdin.readline().split())
	h = list(map(int, sys.stdin.readline().split()))
	graph = [[] for i in range(n)]
	for i in range(m):
		ai, bi = map(int, sys.stdin.readline().split())
		graph[ai-1].append(bi-1)
		graph[bi-1].append(ai-1)
	log.print(graph)
	cnt = 0
	for i in range(n):
		good = True
		for j in range(len(graph[i])):
			log.print(i, graph[i][j])
			if h[i] <= h[graph[i][j]]:
				good = False
		if good:
			cnt += 1
	print(cnt)

	


main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from collections import Counter
n,m = map(int,input().split())
h = list(map(int,input().split()))
judge = [0]*n
t = [0]*n
for _ in range(m):
    a,b = map(int,input().split())
    t[a-1] = max(t[a-1],max(h[a-1],h[b-1]))
    t[b-1] = max(t[b-1],max(h[a-1],h[b-1]))
    if h[a-1] == h[b-1]:
        judge[a-1] = 1
        judge[b-1] = 1

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

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
high = list(map(int, input().split()))
route = []
ans = 0
for i in range(N + 1):
  ls = set()
  route.append(ls)

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

for i, v in enumerate(route):
  if i == 0:
    continue
  kijun = high[i - 1]
  if v == set():
    ans += 1
    continue
  else:
    flag = True
    for j in v:
      tmp = high[j - 1]
      if tmp >= kijun:
        flag = False
    if flag:
      ans += 1

print(ans)

Submission status: Accepted

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

H = list(map(int,input().split()))
T = [True]*n
A=[0]*m
B=[0]*m
for i in range(m):
    A[i],B[i] = map(int,input().split())

box=[[0] for _ in range(n)]
for i in range(m):
    if H[A[i] -1] - H[B[i] -1] < 0:
        box[A[i] -1].append(1)
        box[B[i] -1].append(0)
        
    elif H[A[i] -1] - H[B[i] -1]==0:
        box[A[i] -1].append(1)
        box[B[i] -1].append(1)
        
    elif H[A[i] -1] - H[B[i] -1] > 0:
        box[A[i] -1].append(0)
        box[B[i] -1].append(1)
        
for i in range(n):
    if sum(box[i])==0:
        T[i] =True
    else:
        T[i] = False

print(T.count(True))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
def main():
    N,M = map(int, input().split())
    H = list(map(int, input().split()))
    #print(H)
    ans = []
    ansn = 0
    for _ in range(N):
        ans.append(0)
    for i in range(M):
        A,B = map(int, input().split())
        if H[A-1] < H[B-1]:
            ans[A-1] = -1
        elif H[A-1] > H[B-1]:
            ans[B-1] = -1
        else:
            ans[B-1] = -1
            ans[A-1] = -1
    for j in ans:
        if j == 0:
            ansn += 1
    #print(ansn, ans)
    print(ansn)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
[n, m] = [int(i) for i in input().split()]
h = [int(i) for i in input().split()]
st = [set([]) for _ in range(n)]
for i in range(m):
    [a, b] = [int(i) for i in input().split()]
    st[a-1].add(b-1)
    st[b-1].add(a-1)
cnt = 0
for i, height in enumerate(h):
    line = []
    for huga in st[i]:
        line.append(h[huga])
    if len(line) == 0 or height > max(line):
        cnt += 1
print(cnt)

Submission status: Accepted

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

R=[1]*n

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

print(sum(R))

Submission status: Accepted

Solution code:
from sys import stdin
import sys
import math


N, M = list(map(int, stdin.readline().rstrip().split()))
H = list(map(int, stdin.readline().rstrip().split()))

A = []
for i in range(M):
    #A.append(stdin.readline().rstrip().split())
    A.append(list(map(int, stdin.readline().rstrip().split())))

#print(H)
#print(A)

m = {}

for tmp in A:
    #print(tmp)
    a, b = tmp
    #print(a)
    if H[a - 1] > H[b - 1]:
        m[b] = 0
    elif H[a - 1] < H[b - 1]:
        m[a] = 0
    else:
        m[a] = 0
        m[b] = 0

count = 0
for j in range(1, N+1):
    if m.get(j, 1) == 1:
        count += 1

print(count)

Submission status: Accepted

Solution code:
# Onum : Obs. Num
# Rnum : Road Num
# H : Hight of Obs.
# R : Road
Onum, Rnum = map(int, input().split())
H = list(map(int, input().split()))
R = []
good = Onum      # count of good obs.
bad = [0] * Onum    # check list of not good obs.


def mark(idx):
    global good
    if bad[idx] == 0:
        good -= 1
    bad[idx] += 1


for i in range(Rnum):
    R = list(map(int, input().split()))
    if H[R[0] - 1] == H[R[1] - 1]:
        mark(R[0] - 1)
        mark(R[1] - 1)
    elif H[R[0] - 1] > H[R[1] - 1]:
        mark(R[1] - 1)
    elif H[R[0] - 1] < H[R[1] - 1]:
        mark(R[0] - 1)

print(good)

Submission status: Accepted

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

s = set()

for i in range(m):
    arr = arrs[i]
    if l[arr[0]-1] < l[arr[1]-1]:
        s.add(arr[0])
    elif l[arr[0]-1] == l[arr[1]-1]:
        s.add(arr[0])
        s.add(arr[1])
    else:
        s.add(arr[1])

ans = n - len(s)
print(ans)

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
H = list(map(int,input().split()))
AB = [list(map(int,input().split())) for _ in range(M)]
A = [list() for _ in range(N)] 
ans = 0  
for a ,b in AB:
    A[b-1].append(a-1)
    A[a-1].append(b-1)
for i in range(N):
    for j in A[i]:
        #満たさないものを数える
        if H[i] <= H[j]:
            ans += 1
            break
print(N-ans)

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict

input = sys.stdin.readline


def I():
    return int(input())


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


def LI():
    return list(MI())


def LIN(n: int):
    return [I() for _ in range(n)]


inf = float("inf")
mod = 10 ** 9 + 7


def main():
    n, m = MI()
    h = LI()

    dict = defaultdict(set)
    for _ in range(m):
        a, b = MI()
        dict[a].add(b)
        dict[b].add(a)

    c = n
    for k, v in dict.items():
        for t in v:
            if h[t - 1] >= h[k - 1]:
                c -= 1
                break

    print(c)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

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

print(N-sum(ans))

Submission status: Accepted

Solution code:
from collections import defaultdict, deque

def main():
    N, M = tuple(int(c) for c in input().split(' '))
    H = [0] + [int(c) for c in input().split(' ')]
    path = defaultdict(set)
    for _ in range(M):
        a, b = tuple(int(c) for c in input().split(' '))
        path[a].add(b)
        path[b].add(a)

    def tansaku(dai):
        #print(f'---traversing {dai}')
        #print(f'stack: {stack}, traversed: {traversed}')
        reachable = path[dai]
        #print(f'reachable[{i}]: {reachable}')
        if len(reachable) == 0:
            return 1
        else:
            for j in reachable:
                if H[dai] <= H[j]:
                    return 0
            else:
                return 1 

    cnt = 0
    for dai in range(1, N+1):
        cnt += tansaku(dai)

    print(cnt)

if __name__ == "__main__":
    main()

Submission status: Accepted

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

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

res =  [True] * n

for _ in range(m):
    x1, x2 = map(int,input().split())

    if h[x1 - 1] <= h[x2 - 1]:
        res[x1 - 1] = False
    if h[x2 - 1] <= h[x1 - 1]:
        res[x2 - 1] = False

print(sum(res))

Submission status: Accepted

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

L = [1] * N

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

print(sum(L))