#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,002 ms / 2,000 ms
コード長	562 bytes
コンパイル時間	1,204 ms
コンパイル使用メモリ	10,904 KB
実行使用メモリ	47,076 KB
最終ジャッジ日時	2023-08-11 13:01:54
合計ジャッジ時間	62,636 ms
ジャッジサーバーID （参考情報）	judge13 / judge11

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	94 ms 19,744 KB
testcase_01	AC	93 ms 19,764 KB
testcase_02	AC	96 ms 19,800 KB
testcase_03	AC	888 ms 42,572 KB
testcase_04	AC	358 ms 20,976 KB
testcase_05	AC	570 ms 30,128 KB
testcase_06	AC	574 ms 35,160 KB
testcase_07	AC	813 ms 35,624 KB
testcase_08	AC	213 ms 29,812 KB
testcase_09	AC	643 ms 24,964 KB
testcase_10	AC	165 ms 20,728 KB
testcase_11	AC	487 ms 32,280 KB
testcase_12	AC	1,002 ms 43,896 KB
testcase_13	AC	960 ms 43,764 KB
testcase_14	AC	971 ms 43,560 KB
testcase_15	AC	978 ms 43,564 KB
testcase_16	AC	989 ms 43,800 KB
testcase_17	AC	980 ms 43,932 KB
testcase_18	AC	977 ms 43,744 KB
testcase_19	AC	979 ms 43,604 KB
testcase_20	AC	985 ms 43,564 KB
testcase_21	AC	563 ms 19,676 KB
testcase_22	AC	559 ms 19,832 KB
testcase_23	AC	569 ms 19,740 KB
testcase_24	AC	567 ms 19,804 KB
testcase_25	AC	550 ms 19,716 KB
testcase_26	AC	553 ms 19,716 KB
testcase_27	AC	561 ms 19,756 KB
testcase_28	AC	563 ms 19,828 KB
testcase_29	AC	541 ms 19,836 KB
testcase_30	AC	971 ms 42,164 KB
testcase_31	AC	994 ms 42,128 KB
testcase_32	AC	976 ms 42,044 KB
testcase_33	AC	958 ms 42,072 KB
testcase_34	AC	978 ms 42,044 KB
testcase_35	AC	971 ms 42,140 KB
testcase_36	AC	953 ms 42,144 KB
testcase_37	AC	971 ms 42,052 KB
testcase_38	AC	984 ms 42,040 KB
testcase_39	AC	568 ms 19,784 KB
testcase_40	AC	557 ms 19,680 KB
testcase_41	AC	556 ms 19,708 KB
testcase_42	AC	550 ms 19,716 KB
testcase_43	AC	562 ms 19,764 KB
testcase_44	AC	554 ms 19,800 KB
testcase_45	AC	544 ms 19,728 KB
testcase_46	AC	560 ms 19,784 KB
testcase_47	AC	562 ms 19,800 KB
testcase_48	AC	962 ms 42,156 KB
testcase_49	AC	944 ms 41,988 KB
testcase_50	AC	936 ms 42,124 KB
testcase_51	AC	919 ms 42,136 KB
testcase_52	AC	929 ms 42,140 KB
testcase_53	AC	891 ms 42,080 KB
testcase_54	AC	909 ms 42,032 KB
testcase_55	AC	959 ms 42,080 KB
testcase_56	AC	938 ms 42,112 KB
testcase_57	AC	954 ms 46,980 KB
testcase_58	AC	947 ms 46,848 KB
testcase_59	AC	959 ms 47,076 KB
testcase_60	AC	938 ms 46,964 KB
testcase_61	AC	954 ms 47,044 KB
testcase_62	AC	943 ms 46,972 KB
testcase_63	AC	946 ms 46,828 KB
testcase_64	AC	937 ms 46,808 KB
testcase_65	AC	941 ms 46,980 KB
testcase_66	AC	257 ms 19,700 KB
testcase_67	AC	830 ms 31,304 KB
testcase_68	AC	957 ms 46,824 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

結果

テストケース

ソースコード