Contest Duration: - (local time) (100 minutes) Back to Home

Submission #13229453

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

print(ans)

solve()
```

#### Submission Info

Submission Time 2020-05-15 20:00:03+0900 E - Second Sum ZollingerPython3 Python (3.4.3) 0 1308 Byte TLE 2104 ms 14052 KB

#### Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 500
Status
 AC × 3
 AC × 17 TLE × 5
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 17 ms 3064 KB
00-sample-02.txt AC 17 ms 3064 KB
00-sample-03.txt AC 17 ms 3064 KB
01-small-01.txt AC 17 ms 3064 KB
01-small-02.txt AC 18 ms 3064 KB
01-small-03.txt AC 18 ms 3064 KB
01-small-04.txt AC 18 ms 3192 KB
01-small-05.txt AC 17 ms 3064 KB
02-large-01.txt TLE 2104 ms 12776 KB
02-large-02.txt AC 1645 ms 9152 KB
02-large-03.txt TLE 2104 ms 13056 KB
02-large-04.txt TLE 2104 ms 13208 KB
02-large-05.txt AC 1722 ms 9352 KB
03-max-01.txt TLE 2104 ms 14052 KB
03-max-02.txt TLE 2104 ms 14004 KB
04-min-01.txt AC 17 ms 3064 KB
05-sorted-01.txt AC 1620 ms 13544 KB
05-sorted-02.txt AC 1871 ms 13784 KB
06-almost-sorted-01.txt AC 1561 ms 12976 KB
06-almost-sorted-02.txt AC 1716 ms 12744 KB
06-almost-sorted-03.txt AC 1626 ms 13900 KB
06-almost-sorted-04.txt AC 1706 ms 12772 KB