Submission #1358038

---

Source Code Expand

import sys
sys.setrecursionlimit(10**8)


class Segtree():
    INT_MIN=-10**9

    def __init__(self,size):
        self.size=1
        while self.size<size:
            self.size=self.size*2
        self.node=[self.INT_MIN]*(2*self.size-1)


    def update(self,k,a):
        k+=self.size-1
        self.node[k]=a
        while k>0:
            k=(k-1)/2
            self.node[k]=max(self.node[k*2+1],self.node[k*2+2])

    def get_max(self,queryL,queryR,k=0,nodeL=0,nodeR=-1):
        if nodeR==-1:nodeR=self.size
        if (nodeR<=queryL or queryR<=nodeL):return self.INT_MIN
        if (queryL<=nodeL and nodeR<=queryR):return self.node[k]
        else:
            nodeM=(nodeL+nodeR)/2
            vl=self.get_max(queryL,queryR,k*2+1,nodeL,nodeM)
            vr=self.get_max(queryL,queryR,k*2+2,nodeM,nodeR)
            return max(vl,vr)

n,t=map(int,raw_input().split())
a=map(int,raw_input().split())
seg=Segtree(n)
for i in xrange(n):
    seg.update(i,a[i])
ans=0
mx=0
for i in xrange(n):
    tmp=seg.get_max(i,n)-a[i]
    if mx<tmp:
        ans=1
        mx=tmp
    elif mx==tmp:
        ans+=1
print ans

Submission Info

Judge Result