Submission #7401109


Source Code Expand

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

iPs = [0] * (N+1)
for iP, A in enumerate(Ps):
    iPs[A] = iP

ans = 0
iLs = list(range(N+1))
iRs = list(range(N+1))
for P in range(1, N+1):
    i = iPs[P]
    iL, iR = iLs[i], iRs[i]
    if iL <= 1:
        iL2 = 0
    else:
        iL2 = iLs[iL-1]
    if iR >= N-2:
        iR2 = N-1
    else:
        iR2 = iRs[iR+1]
    num = 0
    if iL != 0:
        num += (iL-iL2)*(iR-i+1)
    if iR != N-1:
        num += (i-iL+1)*(iR2-iR)
    ans += P * num
    iLs[iR+1] = iL
    iRs[iL-1] = iR

print(ans)

Submission Info

Submission Time
Task E - Second Sum
User ZollingerPython3
Language PyPy3 (2.4.0)
Score 500
Code Size 587 Byte
Status AC
Exec Time 222 ms
Memory 53772 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 164 ms 38256 KB
00-sample-02.txt AC 166 ms 38256 KB
00-sample-03.txt AC 164 ms 38256 KB
01-small-01.txt AC 162 ms 38256 KB
01-small-02.txt AC 165 ms 38256 KB
01-small-03.txt AC 165 ms 38256 KB
01-small-04.txt AC 162 ms 38256 KB
01-small-05.txt AC 161 ms 38256 KB
02-large-01.txt AC 218 ms 52500 KB
02-large-02.txt AC 200 ms 46448 KB
02-large-03.txt AC 220 ms 53360 KB
02-large-04.txt AC 217 ms 53448 KB
02-large-05.txt AC 203 ms 47216 KB
03-max-01.txt AC 222 ms 52716 KB
03-max-02.txt AC 218 ms 52716 KB
04-min-01.txt AC 163 ms 38256 KB
05-sorted-01.txt AC 219 ms 53640 KB
05-sorted-02.txt AC 211 ms 52384 KB
06-almost-sorted-01.txt AC 212 ms 53348 KB
06-almost-sorted-02.txt AC 211 ms 52876 KB
06-almost-sorted-03.txt AC 213 ms 53772 KB
06-almost-sorted-04.txt AC 211 ms 52760 KB