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 = list(map(int,input().split()))
h = list(map(int,input().split()))
p = [[] for i in range(n)]
for i in range(m):
    a,b = list(map(int,input().split()))
    p[a-1].append(b-1)
    p[b-1].append(a-1)

ans=0
for i in range(n):
    flag = True
    for j in p[i]:
        if h[j]>=h[i]:
            flag = False
            break
    if flag:
        ans+=1
print(ans)

Submission status: Accepted

Solution code:
n_ten, n_r = map(int, input().split())
H = list(map(int, input().split()))
R = [list(map(int, input().split())) for i in range(n_r)]

bad=set()

for r in R:
    if H[r[0]-1]<=H[r[1]-1]:
        bad.add(r[0])
    if H[r[1]-1]<=H[r[0]-1]:
        bad.add(r[1])

print(n_ten-len(bad))

Submission status: Accepted

Solution code:
# coding: utf-8
import sys
#from operator import itemgetter
sysread = sys.stdin.readline
#from heapq import heappop, heappush
#from collections import defaultdict
sys.setrecursionlimit(10**7)
#import math
#from itertools import combinations
def run():
    N,M = map(int, sysread().split())
    H = [0] + list(map(int, sysread().split()))
    to = [[] for _ in range(N+1)]
    for _ in range(M):
        a,b = map(int, sysread().split())
        to[a].append(b)
        to[b].append(a)

    ret = 0
    for i in range(1, N+1):
        val = H[i]
        no = False
        for k in to[i]:
            if val <= H[k]:
                no = True
                break
        if not no:

            ret += 1
    print(ret)

if __name__ == "__main__":
    run()

Submission status: Accepted

Solution code:
#C
n,m = map(int,input().split())
h = list(map(int,input().split()))
r = []
for _ in range(m):
    a,b = map(int,input().split())
    r.append([a,b])
    
flg = [True for _ in range(n)]

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

print(flg.count(True))

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
H_list = list(map(int, input().split()))
ab_list = [[i] for i in range(N)]
for i in range(M):
    ab = list(map(int, input().split()))
    ab_list[ab[0]-1].append(ab[1]-1)
    ab_list[ab[1]-1].append(ab[0]-1)
ans = N
for i in ab_list:
    for j in range(1, len(i)):
        if H_list[i[0]] <= H_list[i[j]]:
            ans -= 1
            break
print(ans)

Submission status: Accepted

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

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

ANS = [True] * N

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

print(ANS.count(True))

Submission status: Accepted

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

Submission status: Accepted

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

def solve(N: int, M: int, H: "List[int]", A: "List[int]", B: "List[int]"):
    G = nx.Graph()

    nodes = [i for i in range(1, N+1)]
    G.add_nodes_from(nodes)

    edges = [(a,b) for a, b in zip(A, B)]
    G.add_edges_from(edges)

    visited = {}
    for i in range(1, N+1):
        if i in visited:
            continue

        neighbors = G.neighbors(i)

        # get best neighbors weight
        best_neighbor = 0
        for n in neighbors:
            best_neighbor = max(best_neighbor, H[n-1])

        if H[i-1] > best_neighbor:
            visited[i] = True
            for n in neighbors:
                visited[n-1] = False
        else:
            visited[i] = False
            
    cnt = 0
    for key, value in visited.items():
        if value: 
            cnt += 1

    print(cnt)
    return


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

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:

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

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

s = []
ss = []

res = 0

a = [[0 for i in range(1)] for i in range(n)]

for _ in range(m):
    nnn = list(map(int, input().split()))
    a[nnn[0] - 1].append(hyokou[nnn[1] - 1])
    a[nnn[1] - 1].append(hyokou[nnn[0] - 1])

for i in range(n):
    b = max(a[i])
    if hyokou[i] > b:
        res += 1
print(res)

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

tenbou=[1]*N

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

print(sum(tenbou))

Submission status: Accepted

Solution code:
import sys

def main():
    N, M = map(int, input().split())
    H_list = list(map(int, input().split()))
    AB_list = [[int(_) for _ in input().split()] for i in range(M)]

    tree = [[] for _ in range(N)]

    for a, b in AB_list:
        tree[a-1].append(b-1)
        tree[b-1].append(a-1)

    good_observatory = 0

    for i_obs in range(N):
        if len(tree[i_obs]) == 0:
            good_observatory += 1
            continue

        now_height = H_list[i_obs]
        good_flag = True
        for i_tree in tree[i_obs]:
            if now_height <= H_list[i_tree]:
                good_flag = False
        if good_flag:
            good_observatory += 1

    print(good_observatory)
    return


    if a:
        print('Yes')
    else:
        print('No')

    return

if __name__ == '__main__':
    main()
    sys.exit(0)

Submission status: Accepted

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

    temp = [True for _ in range(N)]
    for _ in range(M):
        A, B = map(int, input().split())

        if HN[A - 1] < HN[B - 1]:
            temp[A - 1] = False
        elif HN[B - 1] < HN[A - 1]:
            temp[B - 1] = False
        else:
            temp[A - 1] = False
            temp[B - 1] = False

    print(sum([1 for a in temp if a]))


main()

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
H = list(map(int,input().split()))
Route = []
Check = [""] * N


for i in range(M):
    Route.append(list(map(int,input().split())))
    
Route.sort()


for i in range(M):
    
    if H[Route[i][0] - 1] < H[Route[i][1] - 1]:
        Check[Route[i][0] - 1] = "Bad"
    
    elif H[Route[i][0] - 1] > H[Route[i][1] - 1]:
        Check[Route[i][1] - 1] = "Bad"
        
    else:
        Check[Route[i][0] - 1] = "Bad"
        Check[Route[i][1] - 1] = "Bad"

count = 0

for i in range(N):
    if Check[i] == '':
        count += 1
        
print(count)

Submission status: Accepted

Solution code:

N, M = map(int, input().split())
*H, = map(int, input().split())
set_list = [[] for _ in range(N)]
import sys
input = sys.stdin.readline
for _ in range(M):
    A, B = map(int, input().rstrip().split())
    A -= 1
    B -= 1
    set_list[A].append(B)
    set_list[B].append(A)
ans = 0
for i in range(N):
    chk = True
    for j in set_list[i]:
        if H[i] > H[j]:
            continue
        else:
            chk = False
    if chk:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
L=list(map(int,input().split()))
B=[1]*N
for i in range(M):
  a,b=map(int,input().split())
  if L[a-1]<L[b-1]:
    B[a-1]=0
  elif L[a-1]==L[b-1]:
    B[a-1]=0
    B[b-1]=0
  else:
    B[b-1]=0
print(sum(B))

Submission status: Accepted

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

ex =[]

for i in range(0,m):
    if hlist[ab[i][0]-1] > hlist[ab[i][1]-1]:
        ex.append(ab[i][1]-1)
    elif hlist[ab[i][1]-1] > hlist[ab[i][0]-1]:
        ex.append(ab[i][0]-1)
    else:
        ex.append(ab[i][0]-1)
        ex.append(ab[i][1]-1)

exlen = len(set(ex))

res = n-exlen
print(res)

Submission status: Accepted

Solution code:
def main():
    n,m=map(int,input().split())
    h=list(map(int,input().split()))
    dic={}
    for i in range(m):
        a,b=map(int,input().split())
        dic.setdefault(a,[]).append(b)
        dic.setdefault(b,[]).append(a)
    ans=0
    for i in range(n):
        tmp=h[i]
        f=True
        if i+1 in dic:
            for j in dic[i+1]:
                if tmp<=h[j-1]:
                   f=False
        if f: ans+=1
    print(ans)

if __name__ =='__main__':
    main()

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
lh = list(map(int,input().split()))
la = [0]*N
for i in range(M):
    a,b = map(int,input().split())
    a-=1
    b-=1
    if lh[a] >= lh[b]:
        la[b] +=1
    if lh[b]>=lh[a]:
        la[a] += 1
a = 0
for i in range(N):
    if la[i] == 0:
        a += 1
print(a)

Submission status: Accepted

Solution code:
from statistics import median
#import collections
#aa = collections.Counter(a) # list to list || .most_common(2)で最大の2個とりだせるお a[0][0]
from fractions import gcd
from itertools import combinations # (string,3) 3回
from collections import deque
from collections import defaultdict
import bisect
#
#    d = m - k[i] - k[j]
#    if kk[bisect.bisect_right(kk,d) - 1] == d:
#
#
#
# pythonで無理なときは、pypyでやると正解するかも！！
#
#

import sys
sys.setrecursionlimit(10000000)
mod = 10**9 + 7

def readInts():
  return list(map(int,input().split()))
def main():
    n,m = readInts()
    H = readInts()
    G = [[] for _ in range(n)]
    for i in range(m):
        a,b = map(lambda x:int(x)-1, input().split())
        G[a].append(b)
        G[b].append(a)
    #print(G)
    # 各数字について調べる
    cnt = 0
    for i in range(n):
        if len(G[i]) == 0:
            cnt += 1
            continue
        ok = True
        for k in G[i]:
            if H[i] <= H[k]:
                ok = False
                break
        if ok:
            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()))
k=list(range(1,N+1))
d=dict(zip(k,H))
arr=[1]*N
for _ in range(M):
    a,b=map(int,input().split())
    if d[a]>d[b]:
        arr[b-1]=0
    elif d[a]<d[b]:
        arr[a-1]=0
    else:
        arr[a-1]=0
        arr[b-1]=0
print(sum(arr))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

N,M = list(map(int, input().rstrip().split()))
H_list = list(map(int, input().rstrip().split()))
AB_list = [list(map(int, input().rstrip().split())) for i in range(M)]
#-----

road_dic = {}

for A,B in AB_list:
    road_dic.setdefault(A, [])
    road_dic[A].append(B)
    
    road_dic.setdefault(B, [])
    road_dic[B].append(A)


cnt = 0
for i in range(1, len(H_list)+1):
    if i not in road_dic:
        cnt += 1
    
    else:
        for j in road_dic[i]:
            if H_list[i-1] <= H_list[j-1]:
                break
        else:
            cnt += 1


print(cnt)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
def input(): return sys.stdin.readline().rstrip()

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

  height = [i for i in list(map(int, input().split()))]

  results = [0 for i in range(N)]

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

if __name__ == '__main__':
  main()

Submission status: Accepted

Solution code:
# /usr/bin/python3
# -*- coding: utf-8 -*-
from queue import Queue
from queue import LifoQueue as Stack
from math import sqrt, floor, ceil, log2, log10, pi
from fractions import gcd
from itertools import permutations, combinations
from operator import itemgetter
from functools import cmp_to_key


INF=1001001001
__MOD__=(10**9)+7
yn = 'YNeos'
judge = False
cnt = 0
ans = None


def lcm(a, b):
    return (a*b) // gcd(a,b)

def intinput():
    return int(input())

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

def lineinputs(func=intinput):
    datas = []
    while True:
        try:
            datas.append(func())
        except EOFError:
            break
    return datas

class ModInt():
    def __init__(self, x):
        self.__x = (x % __MOD__)
    def __add__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((self.__x + other.__x)%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((self.__x + other.__x)%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")
    def __radd__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((other.__x + self.__x)%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((other.__x + self.__x)%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")

    def __sub__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((self.__x - other.__x)%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((self.__x - other.__x)%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")
    def __rsub__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((other.__x - self.__x)%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((other.__x - self.__x)%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")

    def __mul__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((self.__x * other.__x)%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((self.__x * other.__x)%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")
    def __rmul__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((other.__x * self.__x)%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((other.__x * self.__x)%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")

    def __truediv__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((self.__x * other.__modinv())%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((self.__x * other.__modinv())%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")
    def __rtruediv__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((other.__x * self.__modinv())%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((other.__x * self.__modinv())%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")

    def __pow__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__(pow(self.__x, other.__x, __MOD__)))
        elif type(other) == ModInt:
            return self.__class__(pow(self.__x, other.__x, __MOD__))
        else:
            raise Exception("Not Int or Not ModInt")
    def __rpow__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__(pow(other.__x, self.__x, __MOD__)))
        elif type(other) == ModInt:
            return self.__class__(pow(other.__x, self.__x, __MOD__))
        else:
            raise Exception("Not Int or Not ModInt")

    def __modinv(self, m=__MOD__):
        a = self.__x
        if a == 0:
            raise ZeroDivisionError()
        if gcd(a, m) != 1:
            raise Exception("%sの逆数は求まりません。" % a)
        b, u, v = m, 1, 0
        while b != 0:
            t = a//b;
            a -= t*b
            a, b = b, a
            u -= t * v
            u, v = v, u
        u %= m
        if u < 0:
            u += m
        return u
    def __int__(self):
        return self.__x
    def __str__(self):
        return str(self.__x)


cnt = 0
def dfs(path, paths, heights):
    global cnt
    if not paths[path]:
        cnt += 1
        return
    for p in paths[path]:
        if heights[path] <= heights[p]:
            continue
        cnt += 1
        dfs(p, paths, heights)

if __name__ == '__main__':
    N, M = mulinputs()
    Hs = list(mulinputs())
    paths = []
    for _ in range(N):
        paths.append(set())
    for _ in range(M):
        A, B = mulinputs()
        paths[A-1].add(B-1)
        paths[B-1].add(A-1)

    # dfs(0, paths, Hs)
    for i, path in enumerate(paths):
        is_highest = True
        for j in path:
            if Hs[i] > Hs[j]:
                continue
            is_highest = False
            break
        if is_highest:
            cnt += 1

    # 出力
    print(cnt)

Submission status: Accepted

Solution code:
'''
.append(要素) リストに要素を追加
.extend(リスト) リストを連結する
.insert(場所,要素) 指定した場所に要素追加
del 配列名[場所]
-1で末尾で末尾から一つ前

sort()
sorted(reverse=true)

配列の初期化
配列名=[a]*n+[b]*m

Decimal()
'''

from sys import stdin
from itertools import accumulate, dropwhile, takewhile, groupby
import bisect
import copy
import math
from functools import reduce
from operator import mul
from collections import Counter
import itertools
import fractions

t = stdin.readline().rstrip().split()
n = int(t[0])
m = int(t[1])
tour = [int(s) for s in stdin.readline().rstrip().split()]
data = []
for el in range(m):
    data.append([int(s) for s in stdin.readline().rstrip().split()])
para = []
for el in range(n):
    tmp = {'index': el, 'height': tour[el], 'rel': []}
    para.append(tmp)
for el in data:
    para[el[0] - 1]['rel'].append(el[1] - 1)
    para[el[1]-1]['rel'].append(el[0]-1)

count = 0
for el in para:
    check = True
    for el2 in el['rel']:
        if el['height'] <= para[el2]['height']:
            check = False
    if check:
        count += 1
print(count)

Submission status: Accepted

Solution code:
n, m = map(int ,input().split())
h = list(map(int, input().split()))
lis = [[] for i in range(n)]
for i in range(m):
    a,b = map(int ,input().split())
    a -= 1
    b -= 1
    lis[a].append(b)
    lis[b].append(a)
#print(lis)
ans = 0
for i in range(n):
    flg = True
    val = h[i]
    for j in range(len(lis[i])):
        if val <= h[lis[i][j]]:
            flg = False
    if flg == True:
        ans += 1
        #print(i)
print(ans)

Submission status: Accepted

Solution code:
import itertools
 
def resolve():
    N, M = map(int, input().split())
    a_list = []
    b_list = []
    h_list = list(map(int, input().split()))

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

    not_good_oka_list = []

    for i in range(M):
        if h_list[a_list[i]-1] == h_list[b_list[i]-1]:
            not_good_oka_list.append(a_list[i]-1)
            not_good_oka_list.append(b_list[i]-1)
        elif h_list[a_list[i]-1] < h_list[b_list[i]-1]:
            not_good_oka_list.append(a_list[i]-1)
        else:
            not_good_oka_list.append(b_list[i]-1)

    print(N - len(set(not_good_oka_list)))

if __name__ == "__main__":
    resolve()

Submission status: Accepted

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

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

d=dict(zip(k,H))

arr=[1]*N

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

print(sum(arr))

Submission status: Accepted

Solution code:
import numpy as np
N, M = map(int, input().split())
H = list(map(int, input().split()))
AB = [list(map(int, input().split())) for _ in range(M)]
h = {}
ans = 0
for row in AB:
    if row[0] in h:
        h[row[0]].append(row[1])
    else:
        h[row[0]] = [row[1]]
    if row[1] in h:
        h[row[1]].append(row[0])
    else:
        h[row[1]] = [row[0]]
ans += sum([1 for i in range(1, N+1) if i not in h.keys()])
for hidx, otherh in h.items():
    if H[hidx-1] > max([H[idx-1] for idx in otherh]):
        ans += 1
print(ans)

Submission status: Accepted

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

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

print(ans.count(1))

Submission status: Accepted

Solution code:

import collections

[n,m] = list(map(int, input().strip().split()))

graph = collections.defaultdict(set)
arr = list(map(int, input().strip().split()))

for i in range(m):
	[u, v] = list(map(int, input().strip().split()))
	
	graph[u].add(v)
	graph[v].add(u)
	
ans = 0
	
for i in range(1, n+1):
	ithDex = i-1
	isPossible = True
	
	for j in graph[i]:
		jthDex = j-1
		
		if arr[ithDex] <= arr[jthDex]:
			isPossible = False
			break
			
	ans += int(isPossible)
	
print(ans)

Submission status: Accepted

Solution code:
#n=int(input())
#n,m=list(map(int,input().split()))
#a=list(map(int,input().split()))
import math
import itertools
from collections import defaultdict
from collections import Counter
import numpy as np

import heapq

def bfs(c,nu,di,node,val):
    c[nu]=True
    di[val[nu]]+=1
    for each in node[nu]:
        if c[each]:
            continue
        di=bfs(c,each,di,node,val)
    return di





n,k=list(map(int,input().split()))
h=list(map(int,input().split()))
#node=[i for i in h]
node=[defaultdict(int) for _ in range(n) ]
for _ in range(k):
    i,v=list(map(int,input().split()))
    i-=1
    v-=1
    """
    if node[i]>node[v]:
        node[v]=node[i]
    elif node[i]<node[v]:
        node[i]=node[v]
    """
    #node[i]=max(node[i],h[v])
    #node[v]=max(node[v],h[i])
    #node[i].append(v)
    #node[v].append(i)
    node[i][h[v]]+=1
    node[v][h[i]]+=1

#print(node)
check=[False for _ in range(n)]
ans=0
for i in range(n):
    t=node[i]
    if len(t)==0:
        ans+=1
        continue
    if max(t.keys())<h[i]:
        #print(i)
        ans+=1
print(ans)

Submission status: Accepted

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

ab_list = []
is_good_observatory = [True for _ in range(n)]
for i in range(m):
    a, b = list(map(int, input().split()))

    if h_list[a-1] >= h_list[b-1]:
        is_good_observatory[b-1] = False
    if h_list[a-1] <= h_list[b-1]:
        is_good_observatory[a-1] = False

print(is_good_observatory.count(True))

Submission status: Accepted

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

Submission status: Accepted

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

ab = [tuple(map(int,input().split())) for i in range(m)]
es = [[] for i in range(n)]
for i, (a,b) in enumerate(ab):
    a,b = a-1,b-1
    es[a].append(b)
    es[b].append(a) #無向グラフ

ans = 0
for i in range(n):
    ma = h[i]
    if es[i] == []:
        ans+=1
    else:
        for aa in set(es[i]):
            if ma <= h[aa]:
                break
        else:
            ans+=1

print(ans)

Submission status: Accepted

Solution code:
import numpy as np

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

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

good_peak = np.zeros(n, dtype = np.int)

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

# print(good_peak)
print(np.count_nonzero(good_peak == 0))

Submission status: Accepted

Solution code:
# Problem C - Peaks

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

# initialization
score_list = [0]*N
for i in range(M):
    a, b = map(int, input().split())
    if h_list[a-1]<h_list[b-1]:
        if h_list[b-1]>=0:
            score_list[b-1] += 1
        else:
            score_list[b-1] = -1 * float("INF")
        score_list[a-1] = -1 * float("INF")
    elif h_list[a-1]>h_list[b-1]:
        if h_list[a-1]>=0:
            score_list[a-1] += 1
        else:
            score_list[a-1] = -1 * float("INF")
        score_list[b-1] =  -1 * float("INF")
    else:
        score_list[a-1] = -1 * float("INF")
        score_list[b-1] = -1 * float("INF")

# output
ans = 0
for s in score_list:
    if s>=0:
        ans += 1
print(ans)

Submission status: Accepted

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

l = [True] * n
# print(l)

count = n
for _ in range(m):
    a, b = map(int, input().split())
    
    a = a - 1
    b = b - 1
    
    ah = hl[a]
    bh = hl[b]
    
    if ah >= bh:
        if l[b] == True:
            count -= 1
            l[b] = False
    if ah <= bh:
        if l[a] == True:
            count -= 1
            l[a] = False
    
    
# print(l)    
print(count)

Submission status: Accepted

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

d = {}
for i in range(m):
    a,b = map(int, input().split())
    if (a-1,b-1) in d :
        continue
    d[(a-1,b-1)] = 1
    d[(b-1,a-1)] = 1
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)

ans = 0
for i in range(n) :
    check = 0
    for j in graph[i] :
        if h[i] <= h[j] :
            check = 1
            break
    if check == 0 :
        ans += 1

print(ans)

Submission status: Accepted

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

graph = [[] for i in range(n)];

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

ans = 0;
for i in range(n) :
    check = 1;
    for j in graph[i] :
        if h[i] <= h[j] :
            check = 0;
    if check :
        ans += 1;

print(ans);

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
h =  list(map(int,input().split()))
adj = [[] for _ in range(n)]
for i in range(m):
    s1,s2 = map(int,input().split())
    adj[s1-1].append(s2-1)
    adj[s2-1].append(s1-1)
total = 0
for i in range(n):
    if (len(adj[i]) == 0):
        total += 1
    else:
        total += int(all(h[i]>h[j] for j in adj[i]))
print(total)

Submission status: Accepted

Solution code:
from collections import defaultdict


def main():
    N, M = list(map(int, input().split(' ')))
    H = list(map(int, input().split(' ')))
    obs = defaultdict(list)
    for _ in range(M):
        A, B = list(map(int, input().split(' ')))
        A -= 1
        B -= 1
        obs[A].append(B)
        obs[B].append(A)
    cnt = 0
    for i in range(N):
        obs_list = obs[i]
        if len(obs_list) == 0:
            cnt += 1
            continue
        h_i = H[i]
        to_be_counted = True
        for j in obs_list:
            if h_i <= H[j]:
                to_be_counted = False
                break
        if to_be_counted:
            cnt += 1
    print(cnt)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict

INF = 10 ** 10

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

hs = [0] + map(int, raw_input().split())
assert len(hs) == n + 1

g = defaultdict(list)

for i in xrange(m):
    (a, b) = map(int, raw_input().split())
    g[a].append(b)
    g[b].append(a)


tot = 0
for i in xrange(1, n + 1):
    maxi = -INF
    for nxt in g[i]:
        maxi = max(maxi, hs[nxt])
    if hs[i] > maxi:
        tot += 1
print tot

Submission status: Accepted

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

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

print(n - len(set(to_remove)))

Submission status: Accepted

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