#827545 (Python3) No.2170 Left Addition Machine

提出ソース

結果

問題	No.2170 Left Addition Machine
ユーザー	titia
提出日時	2022-12-22 04:02:07
言語	Python3 (3.12.2 + numpy 1.26.4 + scipy 1.12.0)
結果	AC
実行時間	1,286 ms / 2,000 ms
コード長	562 bytes
コンパイル時間	326 ms
コンパイル使用メモリ	12,800 KB
実行使用メモリ	49,428 KB
最終ジャッジ日時	2024-04-29 05:25:38
合計ジャッジ時間	73,861 ms
ジャッジサーバーID （参考情報）	judge2 / judge4

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	127 ms 22,400 KB
testcase_01	AC	131 ms 22,528 KB
testcase_02	AC	127 ms 22,272 KB
testcase_03	AC	1,087 ms 45,096 KB
testcase_04	AC	471 ms 23,552 KB
testcase_05	AC	730 ms 32,528 KB
testcase_06	AC	734 ms 37,404 KB
testcase_07	AC	1,015 ms 38,132 KB
testcase_08	AC	275 ms 32,432 KB
testcase_09	AC	824 ms 27,212 KB
testcase_10	AC	225 ms 23,040 KB
testcase_11	AC	579 ms 34,800 KB
testcase_12	AC	1,248 ms 46,152 KB
testcase_13	AC	1,197 ms 46,352 KB
testcase_14	AC	1,239 ms 46,284 KB
testcase_15	AC	1,219 ms 46,172 KB
testcase_16	AC	1,236 ms 46,296 KB
testcase_17	AC	1,214 ms 46,284 KB
testcase_18	AC	1,258 ms 46,176 KB
testcase_19	AC	1,205 ms 46,168 KB
testcase_20	AC	1,211 ms 46,308 KB
testcase_21	AC	700 ms 22,656 KB
testcase_22	AC	684 ms 22,656 KB
testcase_23	AC	705 ms 22,656 KB
testcase_24	AC	698 ms 22,656 KB
testcase_25	AC	697 ms 22,656 KB
testcase_26	AC	691 ms 22,656 KB
testcase_27	AC	682 ms 22,528 KB
testcase_28	AC	697 ms 22,656 KB
testcase_29	AC	704 ms 22,656 KB
testcase_30	AC	1,208 ms 44,568 KB
testcase_31	AC	1,205 ms 44,692 KB
testcase_32	AC	1,197 ms 44,528 KB
testcase_33	AC	1,199 ms 44,572 KB
testcase_34	AC	1,239 ms 44,692 KB
testcase_35	AC	1,218 ms 44,568 KB
testcase_36	AC	1,211 ms 44,568 KB
testcase_37	AC	1,224 ms 44,568 KB
testcase_38	AC	1,200 ms 44,564 KB
testcase_39	AC	720 ms 22,528 KB
testcase_40	AC	698 ms 22,528 KB
testcase_41	AC	695 ms 22,528 KB
testcase_42	AC	708 ms 22,528 KB
testcase_43	AC	703 ms 22,656 KB
testcase_44	AC	704 ms 22,528 KB
testcase_45	AC	702 ms 22,400 KB
testcase_46	AC	693 ms 22,656 KB
testcase_47	AC	704 ms 22,528 KB
testcase_48	AC	1,160 ms 44,672 KB
testcase_49	AC	1,147 ms 44,784 KB
testcase_50	AC	1,109 ms 44,684 KB
testcase_51	AC	1,133 ms 44,564 KB
testcase_52	AC	1,122 ms 44,564 KB
testcase_53	AC	1,100 ms 44,524 KB
testcase_54	AC	1,148 ms 44,820 KB
testcase_55	AC	1,179 ms 44,556 KB
testcase_56	AC	1,286 ms 44,552 KB
testcase_57	AC	1,225 ms 49,276 KB
testcase_58	AC	1,178 ms 49,428 KB
testcase_59	AC	1,140 ms 49,296 KB
testcase_60	AC	1,163 ms 49,296 KB
testcase_61	AC	1,163 ms 49,280 KB
testcase_62	AC	1,217 ms 49,420 KB
testcase_63	AC	1,181 ms 49,284 KB
testcase_64	AC	1,164 ms 49,280 KB
testcase_65	AC	1,150 ms 49,284 KB
testcase_66	AC	339 ms 22,400 KB
testcase_67	AC	1,028 ms 33,700 KB
testcase_68	AC	1,192 ms 49,276 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

import sys
input = sys.stdin.readline

mod=998244353
INV=pow(2,mod-2,mod)
POW2INV=[1]
for i in range(3*10**5):
    POW2INV.append(POW2INV[-1]*INV%mod)

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

INC=[0]*N
now=0

for i in range(1,N):
    if A[i-1]<A[i]:
        pass
    else:
        now=i

    INC[i]=now
    
SUM=[0]
now=1
for i in range(N):
    SUM.append(SUM[-1]+A[i]*now%mod)
    now=now*2%mod
    
for tests in range(Q):
    l,r=map(int,input().split())
    k=max(INC[r-1],l-1)+1
    
    print(((SUM[r]-SUM[k])*POW2INV[k]+A[k-1])%mod)

yukicoder

結果

テストケース

ソースコード