Submission #1358039


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

Submission Time
Task D - An Invisible Hand
User roto_37
Language PyPy2 (5.6.0)
Score 400
Code Size 1162 Byte
Status AC
Exec Time 658 ms
Memory 49568 KB

Judge Result

Set Name sample All
Score / Max Score 0 / 0 400 / 400
Status
AC × 3
AC × 15
Set Name Test Cases
sample sample_01.txt, sample_02.txt, sample_03.txt
All large_01.txt, large_02.txt, random_01.txt, random_02.txt, sample_01.txt, sample_02.txt, sample_03.txt, small_01.txt, small_02.txt, spec_01.txt, spec_02.txt, spec_03.txt, spec_04.txt, spec_05.txt, spec_06.txt
Case Name Status Exec Time Memory
large_01.txt AC 549 ms 46484 KB
large_02.txt AC 534 ms 45292 KB
random_01.txt AC 654 ms 49568 KB
random_02.txt AC 648 ms 49568 KB
sample_01.txt AC 35 ms 27628 KB
sample_02.txt AC 34 ms 28524 KB
sample_03.txt AC 34 ms 27244 KB
small_01.txt AC 35 ms 27628 KB
small_02.txt AC 34 ms 28652 KB
spec_01.txt AC 658 ms 48152 KB
spec_02.txt AC 654 ms 48796 KB
spec_03.txt AC 658 ms 47008 KB
spec_04.txt AC 622 ms 48800 KB
spec_05.txt AC 579 ms 47264 KB
spec_06.txt AC 566 ms 47772 KB