Problem:


Score : 400 points

Problem Statement

There are N towns located in a line, conveniently numbered 1 through N. Takahashi the merchant is going on a travel from town 1 to town N, buying and selling apples.

Takahashi will begin the travel at town 1, with no apple in his possession. The actions that can be performed during the travel are as follows:

Move: When at town i (i < N), move to town i + 1.

Merchandise: Buy or sell an arbitrary number of apples at the current town. Here, it is assumed that one apple can always be bought and sold for A_i yen (the currency of Japan) at town i (1 ≦ i ≦ N), where A_i are distinct integers. Also, you can assume that he has an infinite supply of money.

For some reason, there is a constraint on merchandising apple during the travel: the sum of the number of apples bought and the number of apples sold during the whole travel, must be at most T. (Note that a single apple can be counted in both.)

During the travel, Takahashi will perform actions so that the profit of the travel is maximized. Here, the profit of the travel is the amount of money that is gained by selling apples, minus the amount of money that is spent on buying apples. Note that we are not interested in apples in his possession at the end of the travel.

Aoki, a business rival of Takahashi, wants to trouble Takahashi by manipulating the market price of apples. Prior to the beginning of Takahashi's travel, Aoki can change A_i into another arbitrary non-negative integer A_i' for any town i, any number of times. The cost of performing this operation is |A_i - A_i'|. After performing this operation, different towns may have equal values of A_i.

Aoki's objective is to decrease Takahashi's expected profit by at least 1 yen. Find the minimum total cost to achieve it. You may assume that Takahashi's expected profit is initially at least 1 yen.

Constraints

1 ≦ N ≦ 10^5

1 ≦ A_i ≦ 10^9 (1 ≦ i ≦ N)

A_i are distinct.

2 ≦ T ≦ 10^9

In the initial state, Takahashi's expected profit is at least 1 yen.

Input

The input is given from Standard Input in the following format:

N T
A_1 A_2 ... A_N

Output

Print the minimum total cost to decrease Takahashi's expected profit by at least 1 yen.

Sample Input 1

3 2
100 50 200

Sample Output 1

1

In the initial state, Takahashi can achieve the maximum profit of 150 yen as follows:

Move from town 1 to town 2.

Buy one apple for 50 yen at town 2.

Move from town 2 to town 3.

Sell one apple for 200 yen at town 3.

If, for example, Aoki changes the price of an apple at town 2 from 50 yen to 51 yen, Takahashi will not be able to achieve the profit of 150 yen. The cost of performing this operation is 1, thus the answer is 1.

There are other ways to decrease Takahashi's expected profit, such as changing the price of an apple at town 3 from 200 yen to 199 yen.

Sample Input 2

5 8
50 30 40 10 20

Sample Output 2

2

Sample Input 3

10 100
7 10 4 5 9 3 6 8 2 1

Sample Output 3

2



Sample input:
3 2
100 50 200


Sample output:
1

Submission status: Accepted

Solution code:
n, t = map(int, input().split())
a = list(map(int, input().split()))
m = float('inf')
l = []
max_s = 0
ans = 0
for i in range(n):
    m = min(m, a[i])
    max_s =max(a[i]-m, max_s)
    l.append(max(a[i] - m, 0))
for i in l:
    if i == max_s:
        ans += 1
# print(l)
print(ans)

Submission status: Accepted

Solution code:
import bisect
import collections
import copy
import functools
import heapq
import math
import sys
from collections import deque
from collections import defaultdict
input = sys.stdin.readline
MOD = 10**9+7

N,T = map(int,(input().split()))
a = list(map(int,(input().split())))
a.append(0)
m = a[0]
p = []
for i in range(1,N):
    if m < a[i] > a[i+1]:
        M = a[i]
        p.append(M-m)
    elif a[i] < m:
        m = a[i]

ans = p.count(max(p))
print(ans)

Submission status: Accepted

Solution code:
n, t = map(int, input().split())
l = [int(i)for i in input().split()]

if t <= 1 or all(a >= b for a, b in zip(l, l[1:])):
    print(0)
else:
    mini = float("inf")
    maxp = 0
    maxc = 0
    for n in l:
        if n - mini > maxp:
            maxp = n - mini
            maxc = 1
        elif n - mini == maxp:
            maxp = n - mini
            maxc += 1
        mini = min(mini, n)
    print(maxc)

Submission status: Accepted

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


profit_memo = []
min_price = next(prices)

for price in prices:
    if price < min_price:
        min_price = price
    else:
        profit_memo.append(price - min_price)

max_profit = max(profit_memo)
print(profit_memo.count(max_profit))

Submission status: Accepted

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

def VI(N, init=0):
  return [init for _ in range(N)]
def VVI(N, M, init=0):
  return [[init for _ in range(M)] for _ in range(N)]

def VD(N, init=0.0):
  return [init for _ in range(N)]
def VVD(N, M, init=0.0):
  return [[init for _ in range(M)] for _ in range(N)]

def Decimal(x):
  print("{0:.10f}".format(x))

class Pair:
  def __init__(self, x=0, y=0):
    self.first = x
    self.second = y

  def __repr__(self):
    return '{0} {1}'.format(self.first, self.second)

  def __lt__(self, pi):
    return self.first < pi.second

def POW(x, n):
  ret = 1
  while n:
    if n&1:
      ret *= x
    x *= x
    n >>= 1
  return ret

N, T = map(int, input().rstrip().split())
A = list(map(int, input().rstrip().split()))

mi = VI(N)
ma = VI(N)

mi[0] = A[0]
ma[N-1] = A[N-1]

for i in range(1, N):
  mi[i] = min(A[i], mi[i-1])

for i in range(N-2, -1, -1):
  ma[i] = max(A[i], ma[i+1])

t = T // 2

max_benefit = 0
for i in range(N-1):
  max_benefit = max(max_benefit, ma[i+1]-mi[i])

s = set([])
s.add(A[N-1])
cnt = 0
for i in range(N-2, -1, -1):
  a = A[i]
  if (a+max_benefit) in s:
    cnt += 1
  s.add(a)

print(cnt)

Submission status: Accepted

Solution code:
N, T = map(int,input().split())
A = list(map(int,input().split()))
MIN = A[0]
ans = 0
diff = 0
for i in range(1, N):
    if MIN > A[i]:
        MIN = A[i]
    elif A[i] - MIN > diff:
        ans = 1
        diff = A[i] - MIN
    elif A[i] - MIN == diff:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
N,T = map(int,input().split())
A = list(map(int,input().split()))
v = []

m = A[0]
for i in A:
    m = min(i,m)
    v.append(i-m)

print(v.count(max(v)))

Submission status: Accepted

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

def main():
    N, T = [int(x) for x in input().split()]
    A = [int(x) for x in input().split()]

    maxlist = [0] * N
    ma = 0
    for i in range(N - 1, -1, -1):
        ma = max(ma, A[i])
        maxlist[i] = ma

    c = collections.Counter()

    for i in range(N - 1):
        c[maxlist[i + 1] - A[i]] += 1

    m = sorted(c.keys(), reverse=True)


    print(c[m[0]])



    
    
    

if __name__ == '__main__':
    main()

Submission status: Accepted

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

#リンゴを買う個数
apple = n//2

#街iで売った時の利益
b = []
mi = a[0]
for i in range(n):
    if a[i] < mi:
        mi = a[i]
    b.append((a[i]-mi)*apple)

ma = max(b)

print(b.count(ma))

Submission status: Accepted

Solution code:
N, T = map(int, input().split())
a = list(map(int, input().split()))
if N == 1:
    print(1)
    exit()

ans = []
ans.append(a[1] - a[0])
mina = min(a[1], a[0])
maxri = ans[0]
for i in range(2, N):
    ans.append(a[i] - mina)
    maxri = max(ans[i - 1], maxri)
    mina = min(a[i], mina)

print(ans.count(maxri))

Submission status: Accepted

Solution code:
import sys
import heapq
import re
from itertools import permutations
from bisect import bisect_left, bisect_right
from collections import Counter, deque
from fractions import gcd
from math import factorial, sqrt, ceil
from functools import lru_cache, reduce
INF = 1 << 60
MOD = 1000000007
sys.setrecursionlimit(10 ** 7)

# UnionFind
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

def is_prime(n):
    if n == 1:
        return False
    for i in range(2,int(n**0.5)+1):
        if n % i == 0:
            return False
    return True


# ワーシャルフロイド (任意の2頂点の対に対して最短経路を求める)
# 計算量n^3 (nは頂点の数)
def warshall_floyd(d, n):
    #d[i][j]: iからjへの最短距離
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    return d


# ダイクストラ
def dijkstra_heap(s, edge, n):
    #始点sから各頂点への最短距離
    d = [10**20] * n
    used = [True] * n #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for a,b in edge[s]:
        heapq.heappush(edgelist,a*(10**6)+b)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge%(10**6)]:
            continue
        v = minedge%(10**6)
        d[v] = minedge//(10**6)
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,(e[0]+d[v])*(10**6)+e[1])
    return d

# 素因数分解
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

# 2数の最小公倍数
def lcm(x, y):
    return (x * y) // gcd(x, y)

# リストの要素の最小公倍数
def lcm_list(numbers):
    return reduce(lcm, numbers, 1)

# リストの要素の最大公約数
def gcd_list(numbers):
    return reduce(gcd, numbers)

# 素数判定



# limit以下の素数を列挙
def eratosthenes(limit):
    A = [i for i in range(2, limit+1)]
    P = []

    while True:
        prime = min(A)
        
        if prime > sqrt(limit):
            break
            
        P.append(prime)
            
        i = 0
        while i < len(A):
            if A[i] % prime == 0:
                A.pop(i)
                continue
            i += 1
            
    for a in A:
        P.append(a)
            
    return P

# 同じものを含む順列
def permutation_with_duplicates(L):

    if L == []:
        return [[]]

    else:
        ret = []

        # set（集合）型で重複を削除、ソート
        S = sorted(set(L))

        for i in S:

            data = L[:]
            data.remove(i)

            for j in permutation_with_duplicates(data):
                ret.append([i] + j)

        return ret


# ここから書き始める
n, t = map(int, input().split())        
a = list(map(int, input().split()))
b = [0 for i in range(n)]
for i in reversed(range(n)):
    if i == n - 1:
        b[i] = a[i]
    else:
        b[i] = max(a[i], b[i + 1])
c = [0 for i in range(n - 1)]
for i in range(n - 1):
    c[i] = b[i + 1] - a[i]
# print("b =", b)
# print("c =", c)
ans = 1
maximum = 0
for i in c:
    if i > maximum:
        maximum = i
        ans = 1
    elif i == maximum:
        ans += 1
# print("ans =", ans)
print(ans)

Submission status: Accepted

Solution code:
N,T=map(int,input().split())
alist=list(map(int,input().split()))
#print(alist)

arlist=alist[:]
for i in reversed(range(N-1)):
  arlist[i]=max(arlist[i],arlist[i+1])  
#print(arlist)

max_diff=0
for i in range(N-1):
  diff=arlist[i+1]-alist[i]
  max_diff=max(max_diff,diff)

max_diff_cnt=0
for i in range(N-1):
  diff=arlist[i+1]-alist[i]
  if diff==max_diff:
    max_diff_cnt+=1
#print(max_diff,max_diff_cnt)

print(max_diff_cnt)

Submission status: Accepted

Solution code:
from collections import Counter
N, T = map(int, input().split())
A = [int(i) for i in input().split()]
m = A[0]
B = []
for a in A[1:]:
    B.append(a - m)
    m = min(m, a)
c = Counter(B)
print(c[max(c.keys())])

Submission status: Accepted

Solution code:
from collections import Counter
n, t = map(int, input().split())
a = list(map(int, input().split()))
cnt = Counter(a)
cnt_tmp = Counter()
#i番目以下の最小値
min_a = [a[0] for _ in range(n)]
for i in range(n-1):
    min_a[i+1] = min(a[i+1], min_a[i])

res = 0
for i in range(1, n):
    res = max(a[i] - min_a[i-1], res)

ans = 0
for i in range(n):
    cnt_tmp[a[i]] += 1
    x = a[i] + res
    cnt_a = cnt_tmp[a[i]]
    cnt_x = cnt[x] - cnt_tmp[x]
    ans += min(cnt_a, cnt_x)

print(ans)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

def main():
    n,t=MI()
    aa=LI()
    mn=10**10
    pp=[]
    for a in aa:
        pp.append(a-mn)
        mn=min(mn,a)
    #print(pp)
    ans=pp.count(max(pp))
    print(ans)

main()

Submission status: Accepted

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

ml = [(A[-1], 1)]
for a in A[-2:0:-1]:
    n = ml[-1]
    if n[0] == a:
        ml.append((a, n[1] + 1))
    elif n[0] < a:
        ml.append((a, 1))
    else:
        ml.append(n)
ml.reverse()

c = [(ml[i][0] - A[i], ml[i][0], ml[i][1]) for i in range(N - 1)]
c.sort(reverse=True)
max_num = c[0][0]
d = {}
cnt = 0

for m in c:
    if m[0] != max_num:
        break
    cnt += 1
    if m[1] not in d:
        d[m[1]] = m[2]
    else:
        d[m[1]] = max(d[m[1]], m[2])

print(min(cnt, sum(d.values())))

Submission status: Accepted

Solution code:
from collections import defaultdict as dd
N,T = map(int,input().split())
a = list(map(int,input().split()))
dic=dd(int)
mi = a[0]
for i in range(1,N):
    if a[i] < mi:
        mi = a[i]
    else:
        profit = a[i]-mi
        dic[profit] += 1
res = dic[max(dic.keys())]
print(res)

Submission status: Accepted

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


diff_v=0
max_a_v=0
max_a_pos=[]
aa=set([])
bb=set([])

for i in range(1,len(a)):
    index=len(a)-i-1
    if max_a_v<a[index+1]:
        max_a_v=a[index+1]
        max_a_pos=[index+1]
    elif max_a_v==a[index+1]:
        max_a_pos.append(index+1)

    if max_a_v-a[index]>diff_v:
        diff_v=max_a_v-a[index]
        aa=set([index])
        bb=set(max_a_pos)
    elif max_a_v-a[index]==diff_v:
        aa.add(index)
        bb|=set(max_a_pos)
    #print(a[index],max_a_v,diff_v,aa,bb)

print(min(len(list(aa)),len(list(bb))))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
from collections import defaultdict
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

def main():
    N,T=map(int,input().split())
    A=list(map(int,input().split()))
    m=INF
    diff=0
    for i in range(N):
        m=min(m,A[i])
        diff=max(diff,A[i]-m)
    d=defaultdict(int)
    dd=defaultdict(lambda:[0,0])
    for i in range(N):
        res=d[A[i]-diff]
        if res>0:
            dd[A[i]][0]+=1
            dd[A[i]][1]+=res
        d[A[i]]+=1
    ans=0
    for l in dd.values():
        ans+=min(l)
    print(ans)
    

if __name__ == '__main__':
    main()

Submission status: Accepted

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

import sys
# import time
# import math
# import numpy as np
# import scipy.sparse.csgraph as cs            # csgraph_from_dense(ndarray, null_value=inf), bellman_ford(G, return_predecessors=True), dijkstra, floyd_warshall
# import random                                # random, uniform, randint, randrange, shuffle, sample
# import string                                # ascii_lowercase, ascii_uppercase, ascii_letters, digits, hexdigits
# import re                                    # re.compile(pattern) => ptn obj; p.search(s), p.match(s), p.finditer(s) => match obj; p.sub(after, s)
# from bisect import bisect_left, bisect_right # bisect_left(a, x, lo=0, hi=len(a)) returns i such that all(val<x for val in a[lo:i]) and all(val>-=x for val in a[i:hi]).
# from collections import deque                # deque class. deque(L): dq.append(x), dq.appendleft(x), dq.pop(), dq.popleft(), dq.rotate()
# from collections import defaultdict          # subclass of dict. defaultdict(facroty)
# from collections import Counter              # subclass of dict. Counter(iter): c.elements(), c.most_common(n), c.subtract(iter)
# from datetime import date, datetime          # date.today(), date(year,month,day) => date obj; datetime.now(), datetime(year,month,day,hour,second,microsecond) => datetime obj; subtraction => timedelta obj
# from datetime.datetime import strptime       # strptime('2019/01/01 10:05:20', '%Y/%m/%d/ %H:%M:%S') returns datetime obj
# from datetime import timedelta               # td.days, td.seconds, td.microseconds, td.total_seconds(). abs function is also available.
# from copy import copy, deepcopy              # use deepcopy to copy multi-dimentional matrix without reference
# from functools import reduce                 # reduce(f, iter[, init])
# from functools import lru_cache              # @lrucache ...arguments of functions should be able to be keys of dict (e.g. list is not allowed)
# from heapq import heapify, heappush, heappop # built-in list. heapify(L) changes list in-place to min-heap in O(n), heappush(heapL, x) and heappop(heapL) in O(lgn).
# from heapq import nlargest, nsmallest        # nlargest(n, iter[, key]) returns k-largest-list in O(n+klgn).
# from itertools import count, cycle, repeat   # count(start[,step]), cycle(iter), repeat(elm[,n])
# from itertools import groupby                # [(k, list(g)) for k, g in groupby('000112')] returns [('0',['0','0','0']), ('1',['1','1']), ('2',['2'])]
# from itertools import starmap                # starmap(pow, [[2,5], [3,2]]) returns [32, 9]
# from itertools import product, permutations  # product(iter, repeat=n), permutations(iter[,r])
# from itertools import combinations, combinations_with_replacement
# from itertools import accumulate             # accumulate(iter[, f])
# from operator import itemgetter              # itemgetter(1), itemgetter('key')
# from fractions import gcd                    # for Python 3.4 (previous contest @AtCoder)



def main():
    mod = 1000000007                # 10^9+7
    inf = float('inf')              # sys.float_info.max = 1.79...e+308
    # inf = 2 ** 64 - 1             # (for fast JIT compile in PyPy) 1.84...e+19
    sys.setrecursionlimit(10**6)    # 1000 -> 1000000
    def input(): return sys.stdin.readline().rstrip()
    def ii():    return int(input())
    def mi():    return map(int, input().split())
    def mi_0():  return map(lambda x: int(x)-1, input().split())
    def lmi():   return list(map(int, input().split()))
    def lmi_0(): return list(map(lambda x: int(x)-1, input().split()))
    def li():    return list(input())
    
    
    n, t = mi()
    L = lmi()
    diff = [L[i] - L[i-1] for i in range(n) if i > 0]
    # print(diff)

    # sum(diff[i:j]) は L[i] で買い L[j] で売ることを示す
    max_subarray = -inf
    max_subarray_indices = []
    max_subarray_end_with_j = -inf
    max_subarray_end_with_j_indices = [[], []]    # start_indices, j
    # diff[0:1] から diff[0:n-1] までを考察する
    for j in range(1, n):
        if max_subarray_end_with_j + diff[j-1] > diff[j-1]:
            max_subarray_end_with_j = max_subarray_end_with_j + diff[j-1]
            max_subarray_end_with_j_indices[1] = [j]
        elif max_subarray_end_with_j + diff[j-1] < diff[j-1]:
            max_subarray_end_with_j = diff[j-1]
            max_subarray_end_with_j_indices[0] = [j-1]
            max_subarray_end_with_j_indices[1] = [j]
        else:
            max_subarray_end_with_j_indices[0].append(j-1)
        
        if max_subarray < max_subarray_end_with_j:
            max_subarray = max_subarray_end_with_j
            max_subarray_indices = [(start, max_subarray_end_with_j_indices[1][0]) for start in max_subarray_end_with_j_indices[0]]
        elif max_subarray > max_subarray_end_with_j:
            continue
        else:
            max_subarray_indices.append(*[(start, max_subarray_end_with_j_indices[1][0]) for start in max_subarray_end_with_j_indices[0]])
        # print(max_subarray_end_with_j)
        # print(max_subarray_end_with_j_indices)
        # print(max_subarray)
        # print(max_subarray_indices)

    # print(max_subarray)
    # print(max_subarray_indices)

    s = set(max_subarray_indices)
    L1 = sorted(max_subarray_indices, key=lambda x: x[0])
    for i, elm in enumerate(L1):
        if i != 0 and elm[0] == L1[i-1][0]:
            s.remove(elm)
    L2 = sorted(max_subarray_indices, key=lambda x: x[1])
    for i, elm in enumerate(L2):
        if i != 0 and elm[1] == L2[i-1][1] and elm in s:
            s.remove(elm)
    print(len(list(s)))




if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n, t = map(int, input().split())
ns = list(map(int, input().split()))
min_n = 10 ** 10
max_n = 0
max_l = []
for i in ns[::-1]:
    max_n = max(max_n, i)
    max_l.append(max_n)
max_l.reverse()
l = []
for i in range(n):
    l.append(ns[i]-min_n)
    min_n = min(min_n, ns[i])
print(l.count(max(l)))

Submission status: Accepted

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

ans = 0
same = 0
mn = 1100000000
dif = 0
for x in a:
  mn = min(mn, x)
  if dif == x - mn:
    ans += 1
  if dif < x - mn:
    dif = x - mn
    ans = 1
  
print(ans)

Submission status: Accepted

Solution code:
import sys

N, T = map(int, sys.stdin.readline().strip().split())
A = list(map(int, sys.stdin.readline().strip().split()))

# 利益の最大額
max_profit = 0
max_count = 0
# その時点での最小金額
tmp_min = float("inf")
# 売買金額のカウント
count = {}

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

    if tmp_min > A[i]:
        tmp_min = A[i]

    profit = A[i+1] - tmp_min
    if max_profit < profit:
        max_profit = profit
        max_count = 1
    elif max_profit == profit:
        max_count += 1

    # print("max_profit", max_profit, "tmp_min", tmp_min)

print(max_count)

Submission status: Accepted

Solution code:
# ABC047D

import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))


n,t = map(int, input().split())
a = list(map(int, input().split()))

m = a[0]
best = 0
count = 0
for num in a[1:]:
    if m>num:
        m = num
    elif best<num-m:
        best = num - m
        count = 1
    elif best==num-m:
        count += 1
print(count)

Submission status: Accepted

Solution code:
N, T = [int(_) for _ in input().split()]
A = [int(_) for _ in input().split()]

max_diff = 0
cnt = 0
min_a = A[0]
for i in range(1, N):
    a = A[i]
    if min_a > a:
        min_a = a
        continue

    if max_diff < a - min_a:
        max_diff = a - min_a
        cnt = 1
    elif max_diff == a - min_a:
        cnt += 1
print(cnt)

Submission status: Accepted

Solution code:
n,t=map(int,input().split())
a=list(map(int,input().split()))
b=c=0
m=a[0]
for i in range(n):
  if a[i]<m:
    m=a[i]
    continue
    
  d=a[i]-m
  if b<d:
    b=d
    c=1
  elif b==d:
    c+=1
print(c)

Submission status: Accepted

Solution code:
n, t = map(int, input().split())
a = [int(x) for x in input().split()]

minimum = a[0]
count = 0
profit = 0
for i in range(1, n):
  if a[i] < minimum:
    minimum = a[i]
    continue
  
  k = a[i]-minimum
  if profit < k:
    profit = k
    count = 1
  elif profit == k:
    count += 1

print(count)

Submission status: Accepted

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    sys.setrecursionlimit(10**7)
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]

    N,_ = LI()
    N0 = 2 ** N.bit_length()
    st = [0] * (N0*2)

    def add(p,x):
        p += N0-1
        st[p] = x
        while p > 0:
            p = (p-1) // 2
            st[p] = max(st[p*2+1],st[p*2+2])

    def get(a,b,x,l,r):
        if a <= l and r <= b: return st[x]
        if a >= r or b <= l: return 0
        vl = get(a,b,x*2+1,l,(l+r)//2)
        vr = get(a,b,x*2+2,(l+r)//2,r)
        return max(vl,vr)

    A = []
    for e,a in enumerate(sys.stdin.readline().split()):
        a = int(a)
        A.append(a)
        add(e+1,a)
    max_a = -1
    max_cnt = 0
    for i in range(1,N):
        a = get(i+1,N+1,0,0,N0) - A[i-1]
        if a > max_a:
            max_a = a; max_cnt = 1
        elif a == max_a:
            max_cnt += 1

    print(max_cnt)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    sys.setrecursionlimit(10**7)
    INF = 10**18
    MOD = 10**9 + 7
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())

    N,_ = LI()
    N0 = 2 ** N.bit_length()
    st = [0] * (N0*2)

    def add(p,x):
        p += N0-1
        st[p] = x
        while p > 0:
            p = (p-1) // 2
            st[p] = max(st[p*2+1],st[p*2+2])

    def get(a,b,x,l,r):
        if a <= l and r <= b: return st[x]
        if a >= r or b <= l: return 0
        vl = get(a,b,x*2+1,l,(l+r)//2)
        vr = get(a,b,x*2+2,(l+r)//2,r)
        return max(vl,vr)
    A = LI()
    for e,a in enumerate(A):
        add(e+1,a)
    max_a = -1
    max_cnt = 0
    for i in range(1,N):
        a = get(i+1,N+1,0,0,N0) - A[i-1]
        if a > max_a:
            max_a = a; max_cnt = 1
        elif a == max_a:
            max_cnt += 1

    print(max_cnt)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import Counter

n,t = map(int,input().split())
a = list(map(int,input().split()))
a_min = [0] * n
a_min[0] = a[0]
for i in range(1,n):
    a_min[i] = min(a_min[i-1],a[i])

profit = [a[i] - a_min[i] for i in range(n)]

comb = Counter(profit)
print(sorted(comb.items(),reverse = True)[0][1])

Submission status: Accepted

Solution code:
n,t=map(int,input().split())
a=[int(i) for i in input().split()]
mn,mx=10**10,-1
d={}
for i in range(n-1):
    mn=min(a[i],mn)
    mx=max(a[i+1]-mn,mx)
    d[a[i]]=i
d[a[n-1]]=n-1
ans=0
for i in range(1,n):
    if a[i]-mx in d and d[a[i]-mx]<i:
        ans+=1
print(ans)

Submission status: Accepted

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

from collections import defaultdict

def main():
  n, t = map(int, input().split())
  la = list(map(int, input().split()))
  min_a = 10**9 + 7
  max_a = -1
  
  cnts = defaultdict(int)
  for a in la:
    min_a = min(min_a, a)
    cnts[a - min_a] += 1
  print(cnts[max(cnts.keys())])

if __name__=='__main__':
  main()

Submission status: Accepted

Solution code:
N,T=map(int, input().split())
A=list(map(int, input().split()))
if N==1:
  print(1)
  exit()
mn=10**9+1
V=-1*10**9
cnt=0
for i in range(N):
  if V==A[i]-mn:
    cnt+=1
  elif V<A[i]-mn:
    V=A[i]-mn
    cnt=1
  mn=min(A[i],mn)
print(cnt)

Submission status: Accepted

Solution code:
N,T=map(int, input().split())
A=list(map(int, input().split()))
if N==1:
  print(1)
  exit()
mn=10**9+1
sell=-10**9
cnt=0
for i in range(N):
  if sell<A[i]-mn:
    cnt=1
    sell=A[i]-mn
  elif sell==A[i]-mn:
    cnt+=1
  mn=min(A[i],mn)
print(cnt)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


def input():
    return sys.stdin.readline().strip()


def main():
    N, T = map(int, input().split())
    A = list(map(int, input().split()))
    A_ = sorted(A)

    j = -1
    diff = 0
    cnt = 0
    MAX = [0] * N
    MAX[-1] = A[-1]
    for i in range(N - 1)[::-1]:
        if A[i] > MAX[i + 1]:
            MAX[i] = A[i]
        else:
            MAX[i] = MAX[i + 1]

    diff = 0
    cnt = 0
    for i in range(N):
        if MAX[i] - A[i] > diff:
            diff = MAX[i] - A[i]
            cnt = 1
        elif MAX[i] - A[i] == diff:
            cnt += 1

    print(cnt)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict


def input():
    return sys.stdin.readline().strip()


sys.setrecursionlimit(20000000)


def main():
    N, T = map(int, input().split())
    A = list(map(int, input().split()))
    m = float("inf")
    count = defaultdict(int)
    for i in range(N):
        if A[i] < m:
            m = A[i]
        else:
            count[A[i] - m] += 1
    K = list(count.keys())
    print(count[max(K)])


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1

n,t = map(int,input().split())
A = list(map(int,input().split()))
B = [0] * n
acumin = A[0]
for i in range(n):
  acumin = min(acumin,A[i])
  B[i] = A[i] - acumin
C = collections.Counter(B)
print(C[max(B)])

Submission status: Accepted

Solution code:
n,t = list(map(int,input().split()))
a = list(map(int,input().split()))
max_array = [0]*(n+1)
for i in range(n-1,-1,-1):
    max_array[i] = max(max_array[i+1],a[i])
max_diff = 0
for i in range(n):
    max_diff = max(max_diff,max_array[i] - a[i])
count = 0
for i in range(n):
    count += (max_array[i] - a[i]) == max_diff
print(count)

Submission status: Accepted

Solution code:
from collections import defaultdict

N, T, *A = map(int, open(0).read().split())

ctr = defaultdict(int)
m = 10 ** 9 + 7
for i in range(N):
    m = min(m, A[i])
    ctr[A[i] - m] += 1

print(ctr[max(ctr)])

Submission status: Accepted

Solution code:
from bisect import bisect_left
from collections import defaultdict

N, T, *A = map(int, open(0).read().split())

inf = 10 ** 9 + 7
dp = [inf] * (N + 1)
ctr = defaultdict(int)
for i in range(N):
    idx = bisect_left(dp, A[i])
    dp[idx] = A[i]
    if idx != 0:
        ctr[A[i] - dp[0]] += 1

print(ctr[max(ctr)])

Submission status: Accepted

Solution code:
n, t = map(int, input().split())
a = list(map(int, input().split()))
mins = set()
maxs = set()
ma = 0
mi = 10**9
for ind, i in enumerate(a):
    if i<mi:
        mi = i
        min_ind = [ind]
    elif i==mi:
        min_ind.append(ind)
    if i-mi>ma:
        ma = i-mi
        maxs = {ind}
        mins = set(min_ind)
    elif i-mi==ma:
        maxs.add(ind)
        for j in min_ind:
            mins.add(j)
print(min(len(maxs), len(mins)))