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:
from itertools import accumulate
N, T = map(int, input().split())
A = list(map(int, input().split()))

MIN_Acc = list(accumulate(A, func=min))
Profits = [A[i] - MIN_Acc[i] for i in range(N)]
MAX_Profit = max(Profits)

ans = Profits.count(MAX_Profit)
print(ans)

Submission status: Accepted

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

min_num = 0
margin_list = []
for i in range(N):
    if i == 0:
        min_num = a_list[0]
    else:
        if min_num > a_list[i]:
            min_num = a_list[i]
        else:
            margin_list.append(a_list[i]-min_num)
max_num = max(margin_list)
print(margin_list.count(max_num))

Submission status: Accepted

Solution code:
N, T = [int(_) for _ in input().split()]
A = [int(_) for _ in input().split()]
buy_price = float('inf')
count = {}
for i in range(N):
    buy_price = min(buy_price, A[i])
    profit = A[i] - buy_price
    count[profit] = count.get(profit, 0) + 1
print(count[sorted(count.keys())[-1]])

Submission status: Accepted

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

minA = A[0]
profit = 0
cnt = 0
for i in range(1,N):
    # A[i] で min(A[0..i-1])を売る場合の利益
    p = A[i]-minA
    if p==profit:
        cnt += 1 
    elif p>profit:
        profit = p
        cnt = 1
    # min(A[0..i]) の更新
    minA = min(minA,A[i])
    
print(cnt)

Submission status: Accepted

Solution code:
N,T = map(int,input().split())
A = list(map(int,input().split()))
B = []
mini = 0
for i in range(N):
    if A[i] < A[mini]:
        mini = i
    B.append(A[i]-A[mini])
m = max(B)
ans = 0
for i in B:
    if i == m:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
n, t = map(int, input().split())
a = input().split()
a = [int(m) for m in a]
b = sorted(a, reverse=True)
c = set()
k = 1
v = 0
high = 0
ansli = []
for i in range(n - 1):
    c.add(a[i])
    if i == 0 or high == a[i]:
        if i == 0 and b[0] == a[i]:
            v += 1
        while True:
            if b[v] in c:
                v += 1
            else:
                break
        for j in range(k, n):
            if a[j] == b[v] and a[j] not in c:
                high = a[j]
                k = j + 1
                v += 1
                break
            elif a[j] == b[v]:
                v += 1
                while True:
                    if b[v] in c:
                        v += 1
                    else:
                        break
    ansli.append(high - a[i])

ansli.sort(reverse=True)
ans = 1
for i in range(1, n - 1):
    if ansli[i - 1] != ansli[i]:
        break
    else:
        ans += 1
print(ans)

Submission status: Accepted

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

MAX=[A[-1]]

for i in range(N-2,-1,-1):
    MAX.append(max(MAX[-1],A[i]))

MAX=MAX[::-1]
SABUN=[MAX[i]-A[i] for i in range(N)]

#print(MAX)
#print(SABUN)
MAXSA=max(SABUN)

ANS=0
for i in range(N):
    if SABUN[i]==MAXSA:
        ANS+=1

print(ANS)

Submission status: Accepted

Solution code:
from bisect import bisect_left

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

aa = A[:]
aa.sort()

ans = 0
num = 0

for i in range(N-1):
    ind = bisect_left(aa, A[i])
    del aa[ind]
    now = aa[-1] - A[i]
    
    if 0 < now and num < now:
        ans = 1
        num = now
    elif num == now:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
from bisect import bisect_left

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

aa = A[:]
aa.sort()

ans = 0
num = []

for i in range(N-1):
    ind = bisect_left(aa, A[i])
    del aa[ind]
    
    num.append(aa[-1]-A[i])

print(num.count(max(num)))

Submission status: Accepted

Solution code:
N, T = map(int, input().split())
a_arr = list(map(int, input().split()))
mini = 10**9
diff = []
for a in a_arr:
    if a < mini:
        mini = a
    diff.append(a - mini)
max_diff = max(diff)
ans = 0
for d in diff:
    if d == max_diff:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
N,T=map(int,input().split())
A=[int(i) for i in input().split()]
b=0
count=0
for i in range(N):
  if i==0:
    min_A=A[i]
  else:
    if b<A[i]-min_A:
      b=A[i]-min_A
      count=1
    elif b==A[i]-min_A:
      count+=1
    if min_A>A[i]:
      min_A=A[i]
print(count)

Submission status: Accepted

Solution code:
N,T=list(map(int,input().split()))
min_=10**9+1
max_=0
num=0
for x in map(int,input().split()):
    tmp=x-min_
    if x<min_:
        min_=x
    elif tmp>max_:
        max_=tmp
        num=1
    elif  tmp==max_:
        num+=1
print(num)

Submission status: Accepted

Solution code:
# coding:utf-8

import sys


input = sys.stdin.readline
INF = float('inf')
MOD = 10 ** 9 + 7


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


N, T = inpl()
A = inpl()
min_cost = INF
max_diff = 0
cnt = 0
for i in range(N):
    diff = A[i] - min_cost
    if max_diff <= diff:
        if max_diff == diff:
            cnt += 1
        else:
            cnt = 0
            max_diff = diff
    min_cost = min(min_cost, A[i])

print(1 + cnt)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N, T = map(int, input().split())
A = list(map(int, input().split()))
mi = A[0]
ma = 0
for i in range(1, N):
    mi = min(mi, A[i - 1])
    ma = max(ma, A[i] - mi)

num = 0
mi = A[0]
for i in range(1, N):
    mi = min(mi, A[i - 1])
    if A[i] - mi == ma:
        num += 1

print(num)

Submission status: Accepted

Solution code:
n,t=map(int,input().split())
a=list(map(int,input().split()))
a.append(0)
res=[]
t=1
j=False
tmin=a[0]
tmax=a[0]
for i in range(1,n+1):
    if tmin>a[i]:
        res.append(tmax-tmin)
        tmin=a[i]
        tmax=a[i]
    if tmax<a[i]:
        tmax=a[i]
print(res.count(max(res)))

Submission status: Accepted

Solution code:
# ABC 047 D
N, T = map(int,input().split())
A = list(map(int,input().split()))

m = A[0]
M = 0
for k in range(1,N):
    m = min(m,A[k-1])
    M = max(M,A[k]-m)

m = A[0]
ans = 0
for k in range(1,N):
    m = min(m,A[k-1])
    if A[k]-m == M:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
def 解():
    iN,iT = [int(_) for _ in input().split()]
    aA = [int(_) for _ in input().split()]

    aMaxD = [0]
    iMin = aA[0]
    iV = 0

    def checkMax(aMaxD,iMaxD):
        if aMaxD[0] < iMaxD:
            aMaxD = [iMaxD]
        elif aMaxD[0] == iMaxD:
            aMaxD.append(iMaxD)
        return aMaxD

    iB = aA[0]
    for iN in aA[1:]:
        if iB - iN > 0: #山
            if iV >= 0:
                aMaxD = checkMax(aMaxD,iB-iMin)
            iV = -1
        elif iB - iN < 0: #谷
            if iV <= 0:
                if iB < iMin : iMin = iB
            iV = 1
        iB = iN
    aMaxD = checkMax(aMaxD,aA[-1] - iMin)
    print( len(aMaxD) )
解()

Submission status: Accepted

Solution code:
def 解():
    iN,iT = [int(_) for _ in input().split()]
    aA = [int(_) for _ in input().split()]
    iL = len(aA)

    aMaxD = [0]
    iMin = aA[0]
    iV = 0

    def checkMax(aMaxD,iMaxD):
        if aMaxD[0] < iMaxD:
            aMaxD = [iMaxD]
        elif aMaxD[0] == iMaxD:
            aMaxD.append(iMaxD)
        return aMaxD

    iB = aA[0]
    for iN in aA[1:]:
        if iB - iN > 0:
            if iV >= 0:
                aMaxD = checkMax(aMaxD,iB-iMin)
            iV = -1
        elif iB - iN < 0:
            if iV <= 0:
                iMin = min(iB,iMin)
            iV = 1
        iB = iN
    aMaxD = checkMax(aMaxD,aA[-1] - iMin)
    print( len(aMaxD) )
解()

Submission status: Accepted

Solution code:

iN,iT = [int(_) for _ in input().split()]
aA = [int(_) for _ in input().split()]
iL = len(aA)

aMaxD = [0]
iMin = aA[0]
iV = 0

def checkMax(aMaxD,iMaxD):
    if aMaxD[0] < iMaxD:
        aMaxD = [iMaxD]
    elif aMaxD[0] == iMaxD:
        aMaxD.append(iMaxD)
    return aMaxD

for i in range(1,iL):
    iB = aA[i-1]
    iN = aA[i]
    if iB - iN > 0:
        if iV >= 0:
            aMaxD = checkMax(aMaxD,iB-iMin)
        iV = -1
    elif iB - iN < 0:
        if iV <= 0:
            iMin = min(iB,iMin)
        iV = 1
aMaxD = checkMax(aMaxD,aA[-1] - iMin)
print( len(aMaxD) )

Submission status: Accepted

Solution code:
from collections import defaultdict, Counter
from itertools import product, groupby, count, permutations, combinations
from math import pi, sqrt
from collections import deque
from bisect import bisect, bisect_left, bisect_right
from string import ascii_lowercase
from functools import lru_cache
import sys
sys.setrecursionlimit(10000)
INF = float("inf")
YES, Yes, yes, NO, No, no = "YES", "Yes", "yes", "NO", "No", "no"
dy4, dx4 = [0, 1, 0, -1], [1, 0, -1, 0]
dy8, dx8 = [0, -1, 0, 1, 1, -1, -1, 1], [1, 0, -1, 0, 1, 1, -1, -1]


def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W


def ceil(a, b):
    return (a + b - 1) // b


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

    maxi, mini = [-1] * N, [INF] * N
    mini[0] = A[0]
    for i in range(1, N):
        mini[i] = min(mini[i - 1], A[i])
    maxi[-1] = A[-1]
    for i in range(N - 2, -1, -1):
        maxi[i] = max(maxi[i + 1], A[i])

    a, b = defaultdict(int), defaultdict(int)
    diff = -1
    for i in range(N):
        d1 = maxi[i] - A[i]
        d2 = A[i] - mini[i]
        diff = max(diff, d1, d2)
        a[d1] += 1
        b[d2] += 1

    print(min(a[diff], b[diff]))


if __name__ == '__main__':
    main()

Submission status: Accepted

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

Profit = []
tempMin = A[0]
tempMax = A[0]
for i in range(1, N+1):
    if tempMin > A[i]:
        Profit.append(tempMax - tempMin)
        tempMin = A[i]
        tempMax = A[i]
    if tempMax < A[i]:
        tempMax = A[i]

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

Submission status: Accepted

Solution code:
N,T=map(int,input().split())
listA=list(map(int,input().split()))
max=-1
count=0
min=listA[0]
for i in range(N-1):
    if listA[1+i]<min:
        min=listA[1+i]
    if listA[1+i]-min>max:
        max=listA[1+i]-min
        count=1
    elif listA[1+i]-min==max:
        count+=1
print(count)

Submission status: Accepted

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

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

best_buy = 1e9
best_diff = 0
best_diff_cnt= 0

for i in range(N):
  if best_buy > A[i]:
    best_buy = A[i]
  
  if best_diff < A[i] - best_buy:
    best_diff = A[i] - best_buy
    best_diff_cnt = 1
  elif best_diff == A[i] - best_buy:
    best_diff_cnt += 1
    
  #print(i, best_buy, best_diff, best_diff_cnt)
    
print(best_diff_cnt)

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin

def li(): return [int(x) for x in stdin.readline().split()]
def li_(): return [int(x)-1 for x in stdin.readline().split()]
def lf(): return [float(x) for x in stdin.readline().split()]
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(ns())
def nf(): return float(ns())

from collections import Counter

n,t = li()
a = li()

a_rev = a[::-1]
itv_max_rev = [0]
for i in range(n-1):
    itv_max_rev.append(max(itv_max_rev[-1], a_rev[i]))
    
itv_max = itv_max_rev[::-1]

cnt = Counter([])
for ai,ivmi in zip(a, itv_max):
    cnt[ivmi - ai] += 1
    
max_key = max(cnt.keys())
print(cnt[max_key])

Submission status: Accepted

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

vm = a[n - 1]#数列を右から見た時の最大値
dfm = 0
cnt = 0
for i in range(n - 2, -1, -1):
    if a[i] > vm:
        vm = a[i]
    else:
        df = vm - a[i]
        if dfm < df:
            dfm = df
            cnt = 1
        elif dfm == df:
            cnt += 1

print(cnt)

Submission status: Accepted

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

vm = a[n - 1]#数列を右から見た時の最大値
d = dict()
for i in range(n - 2, -1, -1):
    if a[i] > vm:
        vm = a[i]
    else:
        df = vm - a[i]
        d[df] = d.get(df, 0) + 1

df_cnt = sorted(d.items(), key = lambda x:x[0], reverse = True)#差が大きい方から並べる

print(df_cnt[0][1])

Submission status: Accepted

Solution code:
n,t=map(int,input().split())
*a,=map(int,input().split())
l=[None]*n
m=a[0]
for i in range(n):
  m=min(m,a[i])
  l[i]=a[i]-m
print(l.count(max(l)))

Submission status: Accepted

Solution code:
n,t = map(int,input().split())
a =list(map(int,input().split()))
MIN = float("inf")
b = [0] * n
for i in range(n):
  MIN = min(MIN,a[i])
  b[i] = a[i]-MIN
print(b.count(max(b)))

Submission status: Accepted

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

small = 10**9
adv = []
for i in range(1, n):
    small = min(small, a[i-1])
    adv.append(a[i] - small)

count = 0
highest = max(adv)
for i in range(n-1):
    if adv[i] == highest:
        count += 1

print(count)

Submission status: Accepted

Solution code:
from collections import Counter
import sys
sdin = sys.stdin.readline

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

# iまででの最高と最低
diff_list = [] # iを含むiまでの最低
max_list = [] # iを含まないiからの最高

mini = max(a)
maxi = a[-1]
max_list = [a[-1]]
for i in range(n-1,0,-1):
    if a[i] > maxi:
        max_list.append(a[i])
        maxi = a[i]
    else:
        max_list.append(maxi)
        
max_list = max_list[::-1]

# iまでの最低と最高を更新
for i in range(n-1):
#    if a[i] < mini:
#        mini = a[i]
#    
#    if a[i] == maxi:
#        maxi = max(a[i+1:])
        
    diff_list.append(max_list[i]-a[i])
    
cnt = Counter(diff_list)

# 最大値の個数
print(cnt[max(cnt.keys())])

Submission status: Accepted

Solution code:
INF=999999999

n,t=[int(i) for i in input().split()]
a=[int(i) for i in input().split()]


res=0
mini=a[0]
best = -INF

for i in range(1,n):
	if a[i]-mini == best:
		res+=1
	elif a[i]-mini > best:
		best=a[i]-mini
		res=1
	mini=min(mini,a[i])
print(res)

Submission status: Accepted

Solution code:
N, T = map(int, input().split())
A = [int(x) for x in input().split()] + [0]
buy = A[0]
sale = A[0]
benefit = 0
cost = 0
for a in A[1:]:
  if a > sale:
    sale = a
  elif a < buy:
    b = sale - buy
    if b > benefit:
      benefit = b
      cost = 1
    elif b == benefit:
      cost += 1
    buy = a
    sale = a
print(cost)

Submission status: Accepted

Solution code:
#ab = [tuple(map(int, input().split())) for _ in range(n)]
from collections import Counter
from collections import defaultdict
_,_ = map(int, input().split())
a = list(map(int, input().split()))

benefit, min = defaultdict(int), 0
for i in range(len(a)):
    if i == 0 or a[i] <= min:
        min = a[i]
    else:
        benefit[a[i]-min] += 1
print(benefit[max(benefit)])
exit(0)

Submission status: Accepted

Solution code:
from itertools import accumulate
from collections import defaultdict

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

B = [x for x in accumulate(A[::-1], max)][::-1]
c = defaultdict(int)
for i in range(N - 1):
    c[B[i] - A[i]] += 1
print(c[max(c)])

Submission status: Accepted

Solution code:
import sys
import math
import collections
import itertools
import array
import inspect

# Set max recursion limit
sys.setrecursionlimit(1000000)


# Debug output
def chkprint(*args):
    names = {
        id(v): k
        for k, v in inspect.currentframe().f_back.f_locals.items()
    }
    print(', '.join(
        names.get(id(arg), '???') + ' = ' + repr(arg) for arg in args))


# Binary converter
def to_bin(x):
    return bin(x)[2:]


def li_input():
    return [int(_) for _ in input().split()]


def gcd(n, m):
    if n % m == 0:
        return m
    else:
        return gcd(m, n % m)


def gcd_list(L):
    v = L[0]

    for i in range(1, len(L)):
        v = gcd(v, L[i])

    return v


def lcm(n, m):
    return (n * m) // gcd(n, m)


def lcm_list(L):
    v = L[0]

    for i in range(1, len(L)):
        v = lcm(v, L[i])

    return v


# Width First Search (+ Distance)
def wfs_d(D, N, K):
    """
    D: 隣接行列(距離付き)
    N: ノード数
    K: 始点ノード
    """

    dfk = [-1] * (N + 1)
    dfk[K] = 0

    cps = [(K, 0)]
    r = [False] * (N + 1)
    r[K] = True
    while len(cps) != 0:
        n_cps = []
        for cp, cd in cps:
            for i, dfcp in enumerate(D[cp]):
                if dfcp != -1 and not r[i]:
                    dfk[i] = cd + dfcp
                    n_cps.append((i, cd + dfcp))
                    r[i] = True

        cps = n_cps[:]

    return dfk


# Depth First Search (+Distance)
def dfs_d(v, pre, dist):
    """
    v:  現在のノード
    pre: １つ前のノード
    dist: 現在の距離

    以下は別途用意する
    D: 隣接リスト(行列ではない)
    D_dfs_d: dfs_d関数で用いる，始点ノードから見た距離リスト
    """

    global D
    global D_dfs_d

    D_dfs_d[v] = dist

    for next_v, d in D[v]:
        if next_v != pre:
            dfs_d(next_v, v, dist + d)

    return


def sigma(N):
    ans = 0
    for i in range(1, N + 1):
        ans += i
    return ans


class Combination:
    def __init__(self, n, mod):

        g1 = [1, 1]
        g2 = [1, 1]
        inverse = [0, 1]
        for i in range(2, n + 1):
            g1.append((g1[-1] * i) % mod)
            inverse.append((-inverse[mod % i] * (mod // i)) % mod)
            g2.append((g2[-1] * inverse[-1]) % mod)
        self.MOD = mod
        self.N = n
        self.g1 = g1
        self.g2 = g2
        self.inverse = inverse

    def __call__(self, n, r):
        if (r < 0 or r > n):
            return 0
        r = min(r, n - r)
        return self.g1[n] * self.g2[r] * self.g2[n - r] % self.MOD


# --------------------------------------------

dp = None


def main():
    N, T = li_input()
    A = li_input()

    cmin = A[0]
    ans = 0
    maxp = -1

    for i in range(1, len(A)):
        if A[i] < cmin:
            cmin = A[i]
            continue

        if A[i] - cmin > maxp:
            ans = 1
            maxp = A[i] - cmin
        elif A[i] - cmin == maxp:
            ans += 1

    print(ans)


main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sun Aug 12 14:43:03 2018
ABC947D
@author: maezawa
"""

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

cnt_buy = 0
cnt_sell = 0
buy = 10**9
sell = 2
profit = 0

for i in range(n):
    if a[i] - buy > profit:
        profit = a[i] - buy
        sell = a[i]
    elif a[i] < buy:
        buy = a[i]

buy = 10**9
sell = 2
buys = []
sells = []
i_buy = []

for i in range(n):
    if a[i] - buy == profit:
        buys.extend(i_buy)
        sells.append(i)
    elif a[i] < buy:
        buy = a[i]
        i_buy = [i]
    elif a[i] == buy:
        i_buy.append(i)
    
n_sell = len(set(sells)) 
n_buy = len(set(buys))   
        

print(min(n_sell, n_buy))

Submission status: Accepted

Solution code:

# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from pprint import pprint
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(10000)


def read_int():
    return int(input())


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


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, T, A):
    ma = [-1] * N
    ma[-1] = A[-1]
    for i in range(N-2, -1, -1):
        ma[i] = max(ma[i+1], A[i])

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

    return c[max(c.keys())]


def main():
    N, T = read_int_n()
    A = read_int_n()

    print(slv(N, T, A))


if __name__ == '__main__':
    main()

Submission status: Accepted

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

maxA = [min(A)]

for a in A[::-1]:
    maxA.append(max(maxA[-1], a))

del maxA[0]
maxA.reverse()

ans = 0
maxd = 0

for maxa, a in zip(maxA, A):
    d = maxa - a
    if maxd == d:
        ans += 1
    elif maxd < d:
        maxd = d
        ans = 1

print(ans)

Submission status: Accepted

Solution code:
NT=input()
NT=NT.rstrip().split(" ")
N=int(NT[0])
T=int(NT[1])

cnt=0
sa=0
min=0
max=0

L=input()
L=L.rstrip().split(" ")
min=int(L[0])
for i in range(1,len(L)):
    if int(L[i])<min:
        min=int(L[i])
    s=int(L[i])-min
    if s>sa:
        sa=s
        cnt=1
    elif s==sa:
        cnt+=1
    
    #print(cnt,sa,max,min)
print(cnt)

Submission status: Accepted

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

re = 0
max_dif = 0
A_min = A[0]
for i in range(1, N):
    A_min = min(A_min, A[i-1])
    dif = A[i] - A_min
    if max_dif < dif:
        max_dif = dif
        re = 1
    elif dif == max_dif:
        re += 1

print(re)

Submission status: Accepted

Solution code:
class Bit:
    def __init__(self, n):
        self.n = n
        self.data = [0] * (n + 1)

    def ope(self, x, y):
        return max(x, y)

    def update(self, i, v):
        j = i
        while j <= self.n:
            self.data[j] = self.ope(self.data[j], v)
            j += j & -j

    def query(self, i):
        ret = 0
        j = i
        while 0 < j:
            ret = self.ope(self.data[j], ret)
            j &= (j - 1)
        return ret

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

bit = Bit(N)
for i, a in enumerate(reversed(A)):
    bit.update(i + 1, a)

mv, mc = 0, 0
for i in range(N):
    v = bit.query(N - i) - A[i]
    if v > mv:
        mv = v
        mc = 1
    elif v == mv:
        mc += 1
print(mc)

Submission status: Accepted

Solution code:
N, T = map(int, input().split())
A = [int(Ai) for Ai in input().split()]
Amin = A[0]
Bmax = 0
count = 0
for i in range(1, len(A)):
    Amin = min(A[i-1], Amin)
    Bi = A[i] - Amin
    if Bmax == Bi:
        count += 1
    elif Bmax < Bi:
        Bmax = Bi
        count = 1
print(count)

Submission status: Accepted

Solution code:
from collections import defaultdict

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

B = [0] * N
for i in range(N - 1):
    a = A[N - i - 1]
    B[i + 1] = max(B[i], a)
B = B[::-1]

c = defaultdict(int)
for i in range(N - 1):
    c[B[i] - A[i]] += 1
print(c[max(c)])

Submission status: Accepted

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

sa=0
ans=1

n=k[a-1]

for i in range(a-2,-1,-1):
    if k[i]>n:
        n=k[i]
    tmp=n-k[i]
    if tmp>sa:
        sa=tmp
        ans=1
    elif tmp==sa:
        ans+=1

    

print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict

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

min_price = p_list[0]
max_rev = 0
max_dict = defaultdict(int)

for price in p_list[1:]:
  rev = price - min_price
  if rev >= max_rev:
    max_rev = rev
    max_dict[rev] += 1
  if price < min_price:
    min_price = price

max_rev_key = max(max_dict, key=max_dict.get)
min_cost = max_dict[max_rev_key]

print(min_cost)

Submission status: Accepted

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


a_min = float("inf")
a_max = 0
a_diff = 0

ans = 0
a_diff = -1

for a in A:

    hasModefied = False
    if a_min > a:
        a_min = a
        a_max = a
    if a_max < a:
        a_max = a
        hasModefied = True
        
    if hasModefied:
        if a_diff == a_max-a_min:
            ans += 1
        elif a_diff < a_max-a_min:
            a_diff = a_max - a_min
            ans = 1
            
print(ans)

Submission status: Accepted

Solution code:
n,t=map(int,input().split())
a=list(map(int,input().split()))
b=[]
s=a[0]
for i in range(n):
    if a[i]<s:
        s=a[i]
    b.append(a[i]-s)
print(b.count(max(b)))

Submission status: Accepted

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

remain_max = [a[-1]]*n
for i in range(1, n):
    remain_max[-(i+1)] = max(a[-i], remain_max[-i])

diffs = [0]*n
for i in range(n):
    diffs[i] = remain_max[i] - a[i]

max_diff = 0
ans = 0
for i in range(n):
    if diffs[i] > max_diff:
        max_diff = diffs[i]
        ans = 1
    elif diffs[i] == max_diff:
        ans += 1

print(ans)

Submission status: Accepted

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

remain_max = [a[-1]]*n
for i in range(1, n):
    remain_max[-(i+1)] = max(a[-i], remain_max[-i])

diffs1 = [0]*n
for i in range(n):
    diffs1[i] = remain_max[i] - a[i]

max_diff1 = 0
ans1 = 0
for i in range(n):
    if diffs1[i] > max_diff1:
        max_diff1 = diffs1[i]
        ans1 = 1
    elif diffs1[i] == max_diff1:
        ans1 += 1
# print(diffs1, ans1)

remain_min = [a[0]]*n
for i in range(1, n):
    remain_min[i] = min(a[i-1], remain_min[i-1])

diffs2 = [0]*n
for i in range(n):
    diffs2[i] = a[i] - remain_min[i]

max_diff2 = 0
ans2 = 0
for i in range(n):
    if diffs2[i] > max_diff2:
        max_diff2 = diffs2[i]
        ans2 = 1
    elif diffs2[i] == max_diff2:
        ans2 += 1
# print(diffs2, ans2)

print(min(ans1, ans2))

Submission status: Accepted

Solution code:
N, T = map(int, input().split())
A = list(map(int, input().split()))
mi, ma = float("inf"), 0
d = 0
cnt = 0
for a in A:
    mi = min(mi, a)
    if mi+d < a:
        d = a-mi
        cnt = 1
    elif mi+d == a:
        cnt += 1
print(cnt)

Submission status: Accepted

Solution code:
n, t = map(int, raw_input().split())
a = map(int, raw_input().split())
min_a = a[0]
max_a = a[0]
max_diff = []
for i in range(1, len(a)):
  if a[i] >= max_a:
    max_a = a[i]
    max_diff.append(max_a-min_a)
  elif a[i] <= min_a:
    min_a = a[i]
    max_a = a[i]

max_d = max(max_diff)
print(len([d for d in max_diff if d == max_d]))

Submission status: Accepted

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

m = [0]*n
m[-1] = a[-1]
for i in range(n-2, -1, -1):
    m[i] = max(m[i+1], a[i])

p = m[0]-a[0]
ans = 1
for i in range(1, n):
    if m[i]-a[i] == p:
        ans += 1
    elif m[i]-a[i] > p:
        ans = 1
        p = m[i]-a[i]
print(ans)

Submission status: Accepted

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

    if n == 1:
        print(0)
    else:
        min_a, max_prof = a[0], a[1] - a[0]
        cnt, c_lst = 0, []
        for i in range(1, n):
            if a[i] - min_a > max_prof:
                max_prof = a[i] - min_a
                c_lst.append(cnt)
                cnt = 1
            elif a[i] - min_a == max_prof:
                cnt += 1

            if a[i] < min_a:
                min_a = a[i]

        c_lst.append(cnt)

        print(max(c_lst))


if __name__ == '__main__':
    main()

Submission status: Accepted

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

max = [0]

for a in A[::-1][:-1]:
  if a > max[-1]:
    max.append(a)
  else:
    max.append(max[-1])

max.reverse()
  
ans = 0
maxp = 0

for i in range(n):
  p = max[i] - A[i]
  if p > maxp:
    ans = 1
    maxp = p
  elif p == maxp:
    ans += 1

print(ans)

Submission status: Accepted

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

mincost = src[0]
maxgain = 0
sell = 0
buy = 1
for a in src[1:]:
    if a < mincost:
        mincost = a
        buy = 1
    elif a == mincost:
        buy += 1
    elif a > mincost + maxgain:
        maxgain = a - mincost
        sell = 1
    elif a == mincost + maxgain:
        sell += 1

print(max(sell,buy))

Submission status: Accepted

Solution code:
n,t = (int(i) for i in input().split())
a = [int(i) for i in input().split()]
amax = [a[-1]]
for i in range(n-2,0,-1): amax.append(max(amax[-1],a[i]))
num,ans,amax = 0,0,amax[::-1]
for i in range(n-1):
	if num<amax[i]-a[i]: ans,num = 1,amax[i]-a[i]
	elif num==amax[i]-a[i]: ans += 1
print(ans)