Submission #13228794


Source Code Expand

Copy
def solve():
    N = int(input())
    Ps = list(map(int, input().split()))

    def makeBIT(numEle):
        numPow2 = 2 ** (numEle-1).bit_length()
        data = [0] * (numPow2+1)
        return data, numPow2
    def addValue(iA, A):
        iB = iA + 1
        while iB <= numPow2:
            data[iB] += A
            iB += iB & -iB
    def getSum(iA):
        iB = iA + 1
        ans = 0
        while iB > 0:
            ans += data[iB]
            iB -= iB & -iB
        return ans

    data, numPow2 = makeBIT(N)

    iPs = list(range(N))
    iPs.sort(key=lambda iP: Ps[iP])

    ans = 0
    for iP in reversed(iPs):
        v = getSum(iP)
        Bs = []
        for x in range(v-1, v+3):
            if x <= 0:
                L = -1
            elif getSum(numPow2-1) < x:
                L = N
            else:
                maxD = numPow2.bit_length()-1
                L = 0
                S = 0
                for d in reversed(range(maxD)):
                    if S+data[L+(1<<d)] < x:
                        S += data[L+(1<<d)]
                        L += 1<<d
            Bs.append(L)

        num = (Bs[1]-Bs[0])*(Bs[2]-iP) + (iP-Bs[1])*(Bs[3]-Bs[2])
        ans += Ps[iP] * num
        addValue(iP, 1)

    print(ans)


solve()

Submission Info

Submission Time
Task E - Second Sum
User ZollingerPython3
Language PyPy3 (2.4.0)
Score 500
Code Size 1308 Byte
Status AC
Exec Time 552 ms
Memory 60908 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 500 / 500
Status
AC × 3
AC × 22
Set Name Test Cases
Sample 00-sample-01.txt, 00-sample-02.txt, 00-sample-03.txt
All 00-sample-01.txt, 00-sample-02.txt, 00-sample-03.txt, 01-small-01.txt, 01-small-02.txt, 01-small-03.txt, 01-small-04.txt, 01-small-05.txt, 02-large-01.txt, 02-large-02.txt, 02-large-03.txt, 02-large-04.txt, 02-large-05.txt, 03-max-01.txt, 03-max-02.txt, 04-min-01.txt, 05-sorted-01.txt, 05-sorted-02.txt, 06-almost-sorted-01.txt, 06-almost-sorted-02.txt, 06-almost-sorted-03.txt, 06-almost-sorted-04.txt
Case Name Status Exec Time Memory
00-sample-01.txt AC 163 ms 38512 KB
00-sample-02.txt AC 160 ms 38256 KB
00-sample-03.txt AC 162 ms 38256 KB
01-small-01.txt AC 163 ms 38256 KB
01-small-02.txt AC 168 ms 38512 KB
01-small-03.txt AC 164 ms 38256 KB
01-small-04.txt AC 172 ms 38896 KB
01-small-05.txt AC 163 ms 38256 KB
02-large-01.txt AC 511 ms 59724 KB
02-large-02.txt AC 408 ms 51980 KB
02-large-03.txt AC 519 ms 60136 KB
02-large-04.txt AC 527 ms 60360 KB
02-large-05.txt AC 427 ms 52292 KB
03-max-01.txt AC 552 ms 60908 KB
03-max-02.txt AC 552 ms 60908 KB
04-min-01.txt AC 161 ms 38256 KB
05-sorted-01.txt AC 363 ms 60488 KB
05-sorted-02.txt AC 379 ms 60576 KB
06-almost-sorted-01.txt AC 357 ms 60508 KB
06-almost-sorted-02.txt AC 365 ms 59652 KB
06-almost-sorted-03.txt AC 372 ms 60876 KB
06-almost-sorted-04.txt AC 367 ms 59792 KB