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().rstrip().split(" "))
A = list(map(int,input().rstrip().split(" ")))
max_ra = [0 for i in range(len(A)+1)]
ans = 0
k = 0
for i in range(len(A)-1,-1,-1):
    if max_ra[i+1] < A[i]:
        max_ra[i] = A[i]
    else:
        max_ra[i] = max_ra[i+1]
for i in range(len(A)):
    if max_ra[i] - A[i] > k:
        ans = 1
        k = max_ra[i] - A[i]
    elif max_ra[i] - A[i] == k:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
# input()
# int(input())
# map(int, input().split())
# list(map(int, input().split()))
# list(map(int, list(input()))) # スペースがない数字リストを読み込み
import math
import fractions
import sys
import bisect
import heapq  # 優先度付きキュー(最小値取り出し)
import collections
from collections import Counter
from collections import deque
import pprint
import itertools

sr = lambda: input()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

"""nを素因数分解"""
"""2以上の整数n => [[素因数, 指数], ...]の2次元リスト"""


def factorization(n):
    arr = []
    temp = n
    if n == 1:
        return arr

    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


# a^n
def power(a, n, mod):
    x = 1
    while n:
        if n & 1:
            x *= a % mod
        n >>= 1
        a *= a % mod
    return x % mod


# n*(n-1)*...*(l+1)*l
def kaijo(n, l, mod):
    if n == 0:
        return 1
    a = n
    tmp = n - 1
    while (tmp >= l):
        a = a * tmp % mod
        tmp -= 1
    return a


inf = 10 ** 18
mod = 10 ** 9 + 7

n,t = lr()
a = lr()
min_num = inf
ans = 0
max_num = 0
for num in a:
    if max_num == num-min_num:
        ans+=1
    elif max_num < num-min_num:
        ans = 1
        max_num = num-min_num
    min_num = min(num,min_num)
print(ans)

Submission status: Accepted

Solution code:
N, T = map(int, input().split())
A = list(map(int, input().split()))
C = 0
L = 10 ** 9 + 5
S = 0
for a in A:
    if a < L:
        L = a
    elif a > L:
        St = a - L
        if St == S:
            C += 1
        elif St > S:
            C = 1
            S = St
print(C)

Submission status: Accepted

Solution code:
n, t = map(int, input().split())
A = list(map(int, input().split()))
d = {}
min_ = 10**18
for a in A:
    p = a-min_
    if p not in d:
        d[p] = 1
    else:
        d[p] += 1
    if a <= min_:
        min_ = a
M = max(d.keys())
print(d[M])

Submission status: Accepted

Solution code:
from operator import add
from collections import defaultdict

class SegTree():
    def __init__(self, N, e, operator_func=add):
        self.e = e # 単位元
        self.size = N
        self.node = [self.e] * (2*N)
        self.operator_func = operator_func # 処理(add or xor max minなど)

    def set_list(self, l):
        for i in range(self.size):
            self.node[i+self.size-1] = l[i]
        for i in range(self.size-1)[::-1]:
            self.node[i] = self.operator_func(self.node[2*i+1], self.node[2*i+2])
    
    def update(self, k, x):
        k += self.size-1
        self.node[k] = x
        while k >= 0:
            k = (k - 1) // 2
            self.node[k] = self.operator_func(self.node[2*k+1], self.node[2*k+2])

    def get(self, l, r):
        # [l, r) についてqueryを求める
        x = self.e
        l += self.size
        r += self.size

        while l<r:
            if l&1:
                x = self.operator_func(x, self.node[l-1])
                l += 1
            if r&1:
                r -= 1
                x = self.operator_func(x, self.node[r-1])
            l >>= 1
            r >>= 1
        return x

N, T = map(int, input().split())
*A, = map(int, input().split())
tree = SegTree(N, 0, max)
tree.set_list(A)
d = defaultdict(int)
for i in range(N-1):
    d[(tree.get(i+1, N)-A[i])] += 1
print(d[max(d.keys())])

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 8)
ini = lambda: int(sys.stdin.readline())
inm = lambda: map(int, sys.stdin.readline().split())
inl = lambda: list(inm())
ins = lambda: sys.stdin.readline().rstrip()
debug = lambda *a, **kw: print(*a, **dict(file=sys.stderr, **kw))

N, T = inm()
A = inl()
assert N > 1
assert len(A) == N


def solve():
    lmin = [None] * N
    lmin[0] = A[0]
    for i in range(1, N):
        lmin[i] = min(lmin[i - 1], A[i])

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

    gap = -1
    gmin = set()
    for i in range(N - 1):
        g = rmax[i + 1] - lmin[i]
        if g <= 0:
            continue
        if g > gap:
            gap = g
            gmin = {lmin[i]}
            # debug(f"{gap=}: {rmax[i+1]} - {lmin[i]}")
        elif g == gap and lmin[i] not in gmin:
            gmin.add(lmin[i])
    buy = len(gmin)
    assert buy > 0
    return buy


print(solve())

Submission status: Accepted

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

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache

#############
# Constants #
#############

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

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]

######OUTPUT######
def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()

#####Shorten#####
def DD(arg): return defaultdict(arg)

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
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

#####MakeDivisors######
def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors

#####MakePrimes######
def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum

#####GCD#####
def gcd(a, b):
    while b: a, b = b, a % b
    return a

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

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n-1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

#############
# Main Code #
#############
N,T = IL()
A = IL()
ans = []
MIN = A[0]
for i in range(N):
  MIN = min(MIN,A[i])
  ans.append(max(A[i]-MIN,0))
M = max(ans)
count = 0
for a in ans:
  if a == M:
    count += 1
print(count)

Submission status: Accepted

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

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache

#############
# Constants #
#############

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

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]

######OUTPUT######
def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()

#####Shorten#####
def DD(arg): return defaultdict(arg)

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
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

#####MakeDivisors######
def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors

#####MakePrimes######
def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum

#####GCD#####
def gcd(a, b):
    while b: a, b = b, a % b
    return a

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

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n-1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

#############
# Main Code #
#############
N,T = IL()
A = IL()
ans = []
MAX = A[-1]
for i in range(N)[::-1]:
  MAX = max(MAX,A[i])
  ans.append(max(MAX-A[i],0))
M = max(ans)
count = 0
for a in ans:
  if a == M:
    count += 1
print(count)

Submission status: Accepted

Solution code:
def main():
    n, t, *a = map(int, open(0).read().split())
    b = 0
    c = float("Inf")
    ans = 1
    for i in range(n):
        x = a[i]
        ans = 1 if x - c > b else ans + int(x - c == b)
        b = max(b, x - c)
        c = min(c, x)

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    n, t, *a = map(int, open(0).read().split())
    b = 0
    c = float("Inf")
    d = 0
    for i in range(n):
        x = a[i]
        if x - c > b:
            b = x - c
            d = 1
        elif x - c == b:
            d += 1
        c = min(c, x)

    print(d)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import math


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


def read_ints():
    return list(map(int, input().strip().split(' ')))


def solve():
    N, T = read_ints()
    A = read_ints()
    MAX_OF_REST = []
    MAX = -math.inf
    for i in range(N-1, -1, -1):
        MAX = max(MAX, A[i])
        MAX_OF_REST.append(MAX)
    MAX_OF_REST.reverse()
    max_profit = 0
    max_count = 0
    for i in range(N-1):
        profit = MAX_OF_REST[i+1]-A[i]
        if profit > max_profit:
            max_profit = profit
            max_count = 1
        elif profit == max_profit:
            max_count += 1
    return max_count


if __name__ == '__main__':
    print(solve())

Submission status: Accepted

Solution code:
def resolve():
    N, T = list(map(int, input().split()))
    A = list(map(int, input().split()))
    counts = {}
    a_max = -float("inf")
    a_min = A[0]
    for i in range(1, len(A)):
        if a_min < A[i] and a_max < A[i]:
            a_max = A[i]
            counts.setdefault(a_max-a_min, 0)
            counts[a_max-a_min] += 1
        if a_min > A[i]:
            a_min = A[i]
            a_max = -float("inf")
    #print(counts)
    maxdiff = max(counts.keys())
    print(counts[maxdiff])


if __name__ == '__main__':
    resolve()

Submission status: Accepted

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

    mi = 10**10
    diff = 0
    r = 0
    for a in A:
        if a < mi:
            mi = a
        elif a - mi == diff:
            r += 1
        elif a - mi > diff:
            r = 1
            diff = a - mi
    return r

print(main())

Submission status: Accepted

Solution code:
class SegTree:
    def __init__(self, a, func):
        self.n = 2**(len(a) - 1).bit_length()
        self.f = func
        self.d = [0] * (2 * self.n - 1)
        self.d[self.n - 1:self.n - 1 + len(a)] = a
        for i in reversed(range(self.n - 1)):
            self.d[i] = self.f(self.d[2 * i + 1], self.d[2 * i + 2])

    def update(self, i, v):
        i += self.n - 1
        self.d[i] = v
        while i:
            i = (i - 1) // 2
            self.d[i] = self.f(self.d[2 * i + 1], self.d[2 * i + 2])
    # l <= i < r
    def query(self, l, r):
        assert l <= r
        l += self.n
        r += self.n
        s = self.d[l - 1]
        while l < r:
            if l & 1:
                s = self.f(s, self.d[l - 1])
                l += 1
            if r & 1:
                r -= 1
                s = self.f(s, self.d[r - 1])
            l //= 2
            r //= 2
        return s
def main():
    N, T = map(int, input().split())
    A = list(map(int, input().split()))
    if N == 2:
        return 1
    def func(a, b):
        if a >= b:
            return a
        return b
    s = SegTree(A, func)
    d = {}
    for i in range(N):
        t = s.query(i+1, N) - A[i]
        d[t] = d.get(t, 0) + 1
    m = 0
    for i in d:
        if i > m:
            m = i
    return d[m]
print(main())

Submission status: Accepted

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

Amin = 10**10
P = -10**10
c = 0
for i in range(N):
    if A[i] < Amin:
        Amin = A[i]

    if A[i]-Amin == P:
        c += 1
    elif A[i]-Amin > P:
        P = A[i]-Amin
        c = 1
print(c)

Submission status: Accepted

Solution code:
import bisect
import copy
import heapq
import math
import sys
from collections import *
from functools import lru_cache
from itertools import accumulate, combinations, permutations, product
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
sys.setrecursionlimit(5000000)
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

n,t=map(int,input().split())
a=list(map(int,input().split()))
lst=[0]*(n+1)

for i in range(n):
    lst[-2-i]=max(lst[-1-i],a[-1-i])
# print(lst)

sa=0
cnt=0
for i in range(n):
    if sa<lst[i]-a[i]:
        sa=lst[i]-a[i]
        cnt=1
    elif sa==lst[i]-a[i]:
        cnt+=1
    else:
        pass
print(cnt)

Submission status: Accepted

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

# そこまでの最小値を記録する
# 最小値との差が最大になった時点で、その値を記録し、1を計上
# 最小値との差がこれまでの最大値と同じ場合は+1を計上
# 最小値との差の最大値が更新された場合はまた1から計上
# Tは関係ない

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

minval = 10 ** 9 + 1 # そこまでの最小値
maxdiff = 0 # そこまでの差の最大値
ans = 0
for a in A:
  if a < minval:
    minval = a
    continue
  diff = a - minval
  if diff > maxdiff:
    maxdiff = diff
    ans = 1
  elif diff == maxdiff:
    ans += 1

print(ans)

Submission status: Accepted

Solution code:
n,t=map(int,input().split())
a=list(map(int,input().split()))
b=[]
min_a=a[0]
cnt_min=1
for ai in a[1:]:
  if min_a<ai:
    b.append([ai,ai-min_a,cnt_min])
  elif min_a==ai:
    cnt_min+=1
  elif min_a>ai:
    cnt_min=1
    min_a=ai

b.sort(key=lambda x:x[1])
max_v=b[-1][1]
ans={}
while b and max_v==b[-1][1]:
  d,v,e=b.pop()
  if d in ans:
    if e==ans[d][0]:
      ans[d]=[e,ans[d][1]+1]
    elif e>ans[d][0]:
      ans[d]=[e,1]
    else:
      pass
  else:
    ans[d]=[e,1]
tmp=0
for v in ans.values():
  tmp+=min(v)
print(tmp)

Submission status: Accepted

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

dp={}
mina=a[0]
maxdiff=0

for i in range(1,n):
    if a[i]>mina:
        diff=a[i]-mina
        maxdiff=max(maxdiff,diff)

        if diff in dp:
            dp[diff]+=1
        else:
            dp[diff]=1
        
    mina=min(mina,a[i])

print(dp[maxdiff])

Submission status: Accepted

Solution code:
import numpy as np
import sys
def sinput(): return sys.stdin.readline()
def iinput(): return int(sinput())
def imap(): return map(int, sinput().split())
def fmap(): return map(float, sinput().split())
def iarr(): return list(imap())
def farr(): return list(fmap())
def sarr(): return sinput().split()

n, t = imap()
a = iarr()
b = []
minv = a[0]
for i in a:
    minv = min(i, minv)
    b.append(i - minv)
b.sort(reverse=True)
ans = 0
while b[ans]==b[0]: ans+=1
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
n,t = map(int,input().split())
a = [int(i) for i in input().split()]
dct = defaultdict(int)
mv = mk = 0
for i in range(n)[::-1]:
    k = mv-a[i]
    if k > 0: dct[k] += 1
    mk = max(mk,k)
    mv = max(mv,a[i])
print(dct[mk])

Submission status: Accepted

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

Submission status: Accepted

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

m = A[0]
l = []
for i in range(1, N):
    if A[i] < m:
        m = A[i]
    else:
        d = A[i] - m
        l.append(d)
print(l.count(max(l)))

Submission status: Accepted

Solution code:
def main():
    N, T = list(map(int, input().split(' ')))
    A = list(map(int, input().split(' ')))
    score_list = [0 for _ in range(N)]
    min_price = A[0]
    for i in range(N):
        a = A[i]
        score_list[i] = a - min_price
        min_price = min(a, min_price)
    max_score = max(score_list)
    ans = 0
    for i in range(N):
        if score_list[i] == max_score:
            ans += 1
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    N, T = list(map(int, input().split(' ')))
    A = list(map(int, input().split(' ')))
    target_list = list()
    price_buy, town_num_buy = A[N - 1], 1
    price_sell, town_num_sell = A[N - 1], 1
    for t in range(N - 2, -1, -1):
        price = A[t]
        if price < price_buy:
            price_buy = price
            town_num_buy = 1
        elif price == price_buy:
            town_num_buy += 1
        elif price == price_sell:
            town_num_sell += 1
        elif price > price_sell:
            target_list.append({
                'score': price_sell - price_buy,
                'town_num_buy': town_num_buy,
                'town_num_sell': town_num_sell
            })
            price_buy, town_num_buy = price, 1
            price_sell, town_num_sell = price, 1
    target_list.append({
        'score': price_sell - price_buy,
        'town_num_buy': town_num_buy,
        'town_num_sell': town_num_sell
    })
    max_score = max([target['score'] for target in target_list])
    ans = 0
    for target in target_list:
        if target['score'] < max_score:
            continue
        ans += min(target['town_num_buy'], target['town_num_sell'])
    print(ans)


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_list = []
tmp = A[0]
max_tmp = -1011100011
for num in A[1:]:
	diff = num - tmp
	max_tmp = max(diff, max_tmp)
	tmp = min(num, tmp)
	max_list.append(diff)

max_val = max(max_list)
c = max_list.count(max_val)
print(c)

Submission status: Accepted

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
import math
from fractions import gcd
import random
import string
import copy
from itertools import permutations
from operator import mul
from functools import reduce
from bisect import bisect_left, bisect_right

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


#############
# Main Code #
#############

# print(rand_List(1, 10, 10))
N, T = getNM()
price = getList()
max_list = [0] * N

# この先訪れる店の中で最も値段が高い店の値段
def maximizer(num_list):
    num_N = len(num_list)
    res = 0
    for i in range(1, num_N + 1):
        res = max(res, price[-i])
        num_list[-i] = res
maximizer(max_list)

# 最大マージンを調べる
def margin_checker():
    margin = 0
    for i in range(N - 1):
        margin = max(max_list[i] - price[i], margin)
    return margin

max_margin = margin_checker()

cnt = 0
# ループはしないはず
while True:
    for i in range(N - 1):
        if max_list[i] - price[i] == max_margin:
            price[i] += 1
            cnt += 1
    if margin_checker() < max_margin:
        break
    # ループはしないはずだが念の為
    maximizer(max_list)
    max_margin = margin_checker()
print(cnt)

Submission status: Accepted

Solution code:
import math
#import sys
#input = sys.stdin.readline

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return divisors

def ValueToBits(x,digit):
    res = [0 for i in range(digit)]
    now = x
    for i in range(digit):
        res[i]=now%2
        now = now >> 1
    return res

def BitsToValue(arr):
    n = len(arr)
    ans = 0
    for i in range(n):
        ans+= arr[i] * 2**i
    return ans

def ZipArray(a):
    aa = [[a[i],i]for i in range(n)]

    aa.sort(key = lambda x : x[0])
    for i in range(n):
        aa[i][0]=i+1
    aa.sort(key = lambda x : x[1])
    b=[aa[i][0] for i in range(len(a))]
    return b

def ValueToArray10(x, digit):
    ans = [0 for i in range(digit)]
    now = x
    for i in range(digit):
        ans[digit-i-1] = now%10
        now = now //10
    return ans

def Zeros(a,b):
    if(b<=-1):
        return [0 for i in range(a)]
    else:
        return [[0 for i in range(b)] for i in range(a)]

def AddV2(v,w):
    return [v[0]+w[0],v[1]+w[1]]

dir4 = [[1,0],[0,1],[-1,0],[0,-1]]


def clamp(x,y,z):
    return max(y,min(z,x))

class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
 
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
 
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i
            
#
def Zaatsu(a):
    a.sort()
    now = a[0][0]
    od = 0
    for i in range(n):
        if(now==a[i][0]):
            a[i][0]=od
        else:
            now = a[i][0]
            od+=1
            a[i][0] = od
    
    a.sort(key = lambda x : x[1])
    return a

class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (n+1)

    # 検索
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    # 併合
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    # 同じ集合に属するか判定
    def same_check(self, x, y):
        return self.find(x) == self.find(y)


'''
def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p

p = 2
N = 10 ** 6 + 2
fact = [1, 1]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用

for i in range(2, N + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)

'''

def rl(x):
    return range(len(x))

#a = list(map(int, input().split()))
# list(map(int, input().split()))

#################################################
#################################################
#################################################
#################################################



#34-

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

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


difference = 0
mn = 10**9
for i in range(n):
    mn = min(mn,a[i])
    difference = max(difference,a[i]-mn)

#print(difference)

nms = {}

upper = {}
lower = {}

d = difference

for i in range(n):
    if not a[i] in nms:
        nms[a[i]]=1
    else:
        num[a[i]]+=1

    if( a[i]-d in nms):
        lower[a[i]-d] = nms[a[i]-d]
        if(a[i] in upper):
            upper[a[i]] += 1
        else:
            upper[a[i]] = 1


#print(lower,upper)
ans = 0

for i in upper:
    ans += min(upper[i],lower[i-d])
    
print(ans)

Submission status: Accepted

Solution code:
import sys
import heapq
def v():
    N,T=tuple(map(int,sys.stdin.readline().split()))
    A=list(map(int,sys.stdin.readline().split()))
    ma=0
    d=[]
    heapq.heapify(d)
    for a in reversed(A):
        if a<ma:heapq.heappush(d,a-ma)
        else:ma=a
    res,x=1,heapq.heappop(d)
    while len(d)>0:
        y=heapq.heappop(d)
        if x==y:res+=1
    print(res)
if __name__=='__main__':v()