Submission #68148452

Source Code Expand

from atcoder.lazysegtree import LazySegTree
MOD=998244353

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

def op(l:tuple[int,int],r:tuple[int,int]) -> tuple[int, int]:
    lv,ld=l
    rv,rd=r
    return (lv+rv)%MOD,ld+rd
def mapping(f:tuple[int,int],x:tuple[int,int]) -> tuple[int, int]:
    a,b=f
    v,d=x
    return (a*v+b*d)%MOD,d
def composition(f:tuple[int,int],g:tuple[int,int]) -> tuple[int, int]:
    fa,fb=f
    ga,gb=g
    return fa*ga%MOD,(fa*gb+fb)%MOD

lst=LazySegTree(op,(0,0),mapping,composition,(1,0),[(a,1) for a in A])
for _ in range(M):
    l,r=map(int,input().split())
    l-=1
    d=r-l
    t=lst.prod(l,r)[0]
    lst.apply(l,r,(0,t*pow(d,-1,MOD)%MOD))

ans=[lst.get(i)[0] for i in range(N)]
print(*ans)

Submission Info

Submission Time
Task F - Random Gathering
User mo12412
Language Python (PyPy 3.10-v7.3.12)
Score 500
Code Size 769 Byte
Status AC
Exec Time 1760 ms
Memory 271692 KiB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 500 / 500
Status
AC × 3
AC × 49
Set Name Test Cases
Sample 00_sample_00.txt, 00_sample_01.txt, 00_sample_02.txt
All 00_sample_00.txt, 00_sample_01.txt, 00_sample_02.txt, 01_random_03.txt, 01_random_04.txt, 01_random_05.txt, 01_random_06.txt, 01_random_07.txt, 01_random_08.txt, 01_random_09.txt, 01_random_10.txt, 01_random_11.txt, 01_random_12.txt, 01_random_13.txt, 01_random_14.txt, 01_random_15.txt, 01_random_16.txt, 01_random_17.txt, 01_random_18.txt, 01_random_19.txt, 01_random_20.txt, 01_random_21.txt, 01_random_22.txt, 01_random_23.txt, 01_random_24.txt, 01_random_25.txt, 01_random_26.txt, 01_random_27.txt, 01_random_28.txt, 01_random_29.txt, 01_random_30.txt, 01_random_31.txt, 01_random_32.txt, 01_random_33.txt, 01_random_34.txt, 01_random_35.txt, 01_random_36.txt, 01_random_37.txt, 01_random_38.txt, 01_random_39.txt, 01_random_40.txt, 01_random_41.txt, 01_random_42.txt, 01_random_43.txt, 01_random_44.txt, 01_random_45.txt, 01_random_46.txt, 01_random_47.txt, 01_random_48.txt
Case Name Status Exec Time Memory
00_sample_00.txt AC 118 ms 84204 KiB
00_sample_01.txt AC 119 ms 84560 KiB
00_sample_02.txt AC 122 ms 84252 KiB
01_random_03.txt AC 1737 ms 271692 KiB
01_random_04.txt AC 1760 ms 270844 KiB
01_random_05.txt AC 1717 ms 271520 KiB
01_random_06.txt AC 1715 ms 270820 KiB
01_random_07.txt AC 1739 ms 270580 KiB
01_random_08.txt AC 1673 ms 271376 KiB
01_random_09.txt AC 1672 ms 271084 KiB
01_random_10.txt AC 1669 ms 271460 KiB
01_random_11.txt AC 1157 ms 188544 KiB
01_random_12.txt AC 1327 ms 203348 KiB
01_random_13.txt AC 548 ms 122380 KiB
01_random_14.txt AC 837 ms 168200 KiB
01_random_15.txt AC 1020 ms 189988 KiB
01_random_16.txt AC 1651 ms 270696 KiB
01_random_17.txt AC 1518 ms 263120 KiB
01_random_18.txt AC 1457 ms 238308 KiB
01_random_19.txt AC 1650 ms 270456 KiB
01_random_20.txt AC 1538 ms 262560 KiB
01_random_21.txt AC 1433 ms 238552 KiB
01_random_22.txt AC 1671 ms 270016 KiB
01_random_23.txt AC 1555 ms 262856 KiB
01_random_24.txt AC 1450 ms 236600 KiB
01_random_25.txt AC 1674 ms 271192 KiB
01_random_26.txt AC 1558 ms 262508 KiB
01_random_27.txt AC 1427 ms 237604 KiB
01_random_28.txt AC 1036 ms 153360 KiB
01_random_29.txt AC 1076 ms 137164 KiB
01_random_30.txt AC 1663 ms 263016 KiB
01_random_31.txt AC 1686 ms 264748 KiB
01_random_32.txt AC 1667 ms 263136 KiB
01_random_33.txt AC 1650 ms 263996 KiB
01_random_34.txt AC 1632 ms 264668 KiB
01_random_35.txt AC 1530 ms 248292 KiB
01_random_36.txt AC 1042 ms 136740 KiB
01_random_37.txt AC 684 ms 139032 KiB
01_random_38.txt AC 118 ms 84492 KiB
01_random_39.txt AC 119 ms 84420 KiB
01_random_40.txt AC 456 ms 90368 KiB
01_random_41.txt AC 586 ms 90932 KiB
01_random_42.txt AC 640 ms 92144 KiB
01_random_43.txt AC 609 ms 92128 KiB
01_random_44.txt AC 747 ms 101704 KiB
01_random_45.txt AC 625 ms 91712 KiB
01_random_46.txt AC 711 ms 96724 KiB
01_random_47.txt AC 742 ms 103020 KiB
01_random_48.txt AC 510 ms 90488 KiB