Submission #69330857

Source Code Expand

from itertools import accumulate
from atcoder.segtree import SegTree

N, Q = map(int, input().split())
A = list(map(int, input().split()))


e = (0, 0, 0, 0, 0)  # 長さ、単純合計, 上り山合計,下り山, 合計値


def op(l, r):
    dl, sl, ml, nl, tl = l
    dr, sr, mr, nr, tr = r
    d = dl + dr
    s = sl + sr
    m = ml + mr + dr * sl
    n = nl + nr + dl * sr
    t = tl + tr + dl * mr + dr * nl
    return d, s, m, n, t


st = SegTree(op, e, [(1, v, v, v, v) for v in A])
for _ in range(Q):
    l, r = map(int, input().split())
    print(st.prod(l - 1, r)[-1])

"""
2
2 1
2 1 3
2 1 3 3

  1
  1 3
  1 3 3
    3
    3 3
      3
---
2 1 3
2 1 3 3
  1 3
  1 3 3



"""

Submission Info

Submission Time
Task E - Sum of Subarrays
User mo12412
Language Python (PyPy 3.10-v7.3.12)
Score 475
Code Size 732 Byte
Status AC
Exec Time 1429 ms
Memory 220576 KiB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 475 / 475
Status
AC × 1
AC × 16
Set Name Test Cases
Sample sample00.txt
All sample00.txt, testcase00.txt, testcase01.txt, testcase02.txt, testcase03.txt, testcase04.txt, testcase05.txt, testcase06.txt, testcase07.txt, testcase08.txt, testcase09.txt, testcase10.txt, testcase11.txt, testcase12.txt, testcase13.txt, testcase14.txt
Case Name Status Exec Time Memory
sample00.txt AC 124 ms 84440 KiB
testcase00.txt AC 119 ms 84756 KiB
testcase01.txt AC 580 ms 87500 KiB
testcase02.txt AC 891 ms 103384 KiB
testcase03.txt AC 670 ms 105024 KiB
testcase04.txt AC 665 ms 151664 KiB
testcase05.txt AC 645 ms 160204 KiB
testcase06.txt AC 380 ms 103928 KiB
testcase07.txt AC 904 ms 104452 KiB
testcase08.txt AC 1372 ms 208980 KiB
testcase09.txt AC 1393 ms 208476 KiB
testcase10.txt AC 1356 ms 209048 KiB
testcase11.txt AC 1429 ms 208576 KiB
testcase12.txt AC 1422 ms 208740 KiB
testcase13.txt AC 1371 ms 208372 KiB
testcase14.txt AC 837 ms 220576 KiB