#826360 (PyPy3) No.5011 Better Mo's Algorithm is Needed!! (Weighted)

提出ソース

結果

問題	No.5011 Better Mo's Algorithm is Needed!! (Weighted)
ユーザー	titia
提出日時	2022-12-17 04:13:17
言語	PyPy3 (7.3.15)
結果	AC
実行時間	4,862 ms / 5,000 ms
コード長	1,812 bytes
コンパイル時間	1,131 ms
実行使用メモリ	188,872 KB
スコア	37,332,038,863
最終ジャッジ日時	2022-12-17 04:23:54
合計ジャッジ時間	630,978 ms
ジャッジサーバーID （参考情報）	judge14 / judge12
	純コード判定しない問題か言語

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	4,859 ms 180,668 KB
testcase_01	AC	4,854 ms 183,464 KB
testcase_02	AC	4,859 ms 181,788 KB
testcase_03	AC	4,846 ms 180,956 KB
testcase_04	AC	4,853 ms 185,316 KB
testcase_05	AC	4,852 ms 187,044 KB
testcase_06	AC	4,846 ms 183,444 KB
testcase_07	AC	4,851 ms 186,972 KB
testcase_08	AC	4,852 ms 181,060 KB
testcase_09	AC	4,843 ms 180,952 KB
testcase_10	AC	4,849 ms 185,828 KB
testcase_11	AC	4,849 ms 186,936 KB
testcase_12	AC	4,842 ms 177,640 KB
testcase_13	AC	4,848 ms 184,284 KB
testcase_14	AC	4,847 ms 182,564 KB
testcase_15	AC	4,849 ms 179,468 KB
testcase_16	AC	4,849 ms 183,820 KB
testcase_17	AC	4,841 ms 180,172 KB
testcase_18	AC	4,840 ms 175,324 KB
testcase_19	AC	4,840 ms 179,296 KB
testcase_20	AC	4,845 ms 184,680 KB
testcase_21	AC	4,847 ms 181,436 KB
testcase_22	AC	4,851 ms 183,176 KB
testcase_23	AC	4,845 ms 183,124 KB
testcase_24	AC	4,849 ms 181,864 KB
testcase_25	AC	4,851 ms 183,864 KB
testcase_26	AC	4,851 ms 184,660 KB
testcase_27	AC	4,843 ms 180,268 KB
testcase_28	AC	4,847 ms 185,340 KB
testcase_29	AC	4,855 ms 183,248 KB
testcase_30	AC	4,846 ms 178,428 KB
testcase_31	AC	4,847 ms 181,880 KB
testcase_32	AC	4,843 ms 179,556 KB
testcase_33	AC	4,841 ms 180,656 KB
testcase_34	AC	4,842 ms 185,176 KB
testcase_35	AC	4,847 ms 186,488 KB
testcase_36	AC	4,850 ms 182,044 KB
testcase_37	AC	4,845 ms 186,596 KB
testcase_38	AC	4,841 ms 178,752 KB
testcase_39	AC	4,847 ms 182,160 KB
testcase_40	AC	4,845 ms 184,968 KB
testcase_41	AC	4,847 ms 184,396 KB
testcase_42	AC	4,839 ms 185,220 KB
testcase_43	AC	4,847 ms 188,872 KB
testcase_44	AC	4,850 ms 188,352 KB
testcase_45	AC	4,842 ms 180,044 KB
testcase_46	AC	4,838 ms 185,800 KB
testcase_47	AC	4,841 ms 183,424 KB
testcase_48	AC	4,857 ms 178,552 KB
testcase_49	AC	4,848 ms 184,856 KB
testcase_50	AC	4,839 ms 179,368 KB
testcase_51	AC	4,846 ms 180,620 KB
testcase_52	AC	4,839 ms 186,668 KB
testcase_53	AC	4,860 ms 182,096 KB
testcase_54	AC	4,855 ms 183,360 KB
testcase_55	AC	4,843 ms 184,312 KB
testcase_56	AC	4,851 ms 178,792 KB
testcase_57	AC	4,847 ms 182,608 KB
testcase_58	AC	4,862 ms 183,136 KB
testcase_59	AC	4,851 ms 179,640 KB
testcase_60	AC	4,845 ms 179,100 KB
testcase_61	AC	4,839 ms 182,964 KB
testcase_62	AC	4,843 ms 178,784 KB
testcase_63	AC	4,846 ms 179,920 KB
testcase_64	AC	4,846 ms 182,736 KB
testcase_65	AC	4,853 ms 185,900 KB
testcase_66	AC	4,845 ms 183,056 KB
testcase_67	AC	4,849 ms 185,692 KB
testcase_68	AC	4,859 ms 184,636 KB
testcase_69	AC	4,839 ms 181,896 KB
testcase_70	AC	4,854 ms 182,500 KB
testcase_71	AC	4,848 ms 182,908 KB
testcase_72	AC	4,840 ms 181,172 KB
testcase_73	AC	4,841 ms 185,420 KB
testcase_74	AC	4,849 ms 185,020 KB
testcase_75	AC	4,850 ms 183,612 KB
testcase_76	AC	4,848 ms 184,768 KB
testcase_77	AC	4,857 ms 176,272 KB
testcase_78	AC	4,840 ms 173,212 KB
testcase_79	AC	4,850 ms 184,676 KB
testcase_80	AC	4,845 ms 185,380 KB
testcase_81	AC	4,837 ms 180,988 KB
testcase_82	AC	4,851 ms 184,376 KB
testcase_83	AC	4,847 ms 179,552 KB
testcase_84	AC	4,858 ms 181,524 KB
testcase_85	AC	4,842 ms 178,956 KB
testcase_86	AC	4,842 ms 184,608 KB
testcase_87	AC	4,844 ms 180,272 KB
testcase_88	AC	4,840 ms 180,812 KB
testcase_89	AC	4,852 ms 179,816 KB
testcase_90	AC	4,843 ms 177,540 KB
testcase_91	AC	4,855 ms 188,120 KB
testcase_92	AC	4,853 ms 177,104 KB
testcase_93	AC	4,842 ms 181,960 KB
testcase_94	AC	4,843 ms 184,004 KB
testcase_95	AC	4,847 ms 180,592 KB
testcase_96	AC	4,857 ms 180,352 KB
testcase_97	AC	4,847 ms 180,076 KB
testcase_98	AC	4,841 ms 183,028 KB
testcase_99	AC	4,839 ms 179,624 KB
testcase_100	AC	4,840 ms 182,368 KB
testcase_101	AC	4,847 ms 181,580 KB
testcase_102	AC	4,840 ms 177,356 KB
testcase_103	AC	4,840 ms 187,652 KB
testcase_104	AC	4,847 ms 178,740 KB
testcase_105	AC	4,848 ms 178,836 KB
testcase_106	AC	4,846 ms 184,300 KB
testcase_107	AC	4,844 ms 183,488 KB
testcase_108	AC	4,854 ms 178,612 KB
testcase_109	AC	4,845 ms 182,512 KB
testcase_110	AC	4,842 ms 179,132 KB
testcase_111	AC	4,843 ms 179,048 KB
testcase_112	AC	4,841 ms 182,868 KB
testcase_113	AC	4,846 ms 181,640 KB
testcase_114	AC	4,839 ms 175,208 KB
testcase_115	AC	4,837 ms 179,192 KB
testcase_116	AC	4,841 ms 181,468 KB
testcase_117	AC	4,854 ms 179,212 KB
testcase_118	AC	4,852 ms 182,652 KB
testcase_119	AC	4,841 ms 182,304 KB

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

ソースコード

raw source code

import sys
input = sys.stdin.readline
from operator import itemgetter
import time
from random import randint

time0=time.time()

N,Q,WT,ST=map(int,input().split())
W=list(map(int,input().split()))
LR=[list(map(int,input().split()))+[i+1] for i in range(Q)]

LR2=sorted(LR,key=itemgetter(0))

LIST=[[] for i in range(1000)]

for x,y,ind in LR2:
    LIST[x//530].append((y,ind))

ANS=[]

count=0
for i in range(1000):
    if LIST[i]==[]:
        continue
    if count%2==0:
        LIST[i].sort(key=itemgetter(0))
    else:
        LIST[i].sort(key=itemgetter(0),reverse=True)
        
    for _,ind in LIST[i]:
        ANS.append(ind)

    count+=1

SUM=[0]

for w in W:
    SUM.append(SUM[-1]+w)

def score(x,y):
    if x==-1:
        a,b,_=LR[y-1]
        return SUM[b]-SUM[a-1]
    else:
        a,b,_=LR[y-1]
        c,d,_=LR[x-1]

        a2,b2=min(a,c),max(a,c)
        c2,d2=min(b,d),max(b,d)

        return SUM[b2-1]-SUM[a2-1]+SUM[d2]-SUM[c2]
    
def score_reverse(x,y):
    sc=0

    if x==0:
        a=ANS[x]
        b=ANS[y]
        c=ANS[y+1]

        sc-=score(-1,a)+score(a,b)+score(b,c)
        sc+=score(-1,b)+score(b,a)+score(a,c)

        return sc

    if y==len(ANS)-1:
        a=ANS[x-1]
        b=ANS[x]
        c=ANS[y]

        sc-=score(a,b)+score(b,c)
        sc+=score(a,c)+score(c,b)

        return sc

    a=ANS[x-1]
    b=ANS[x]
    c=ANS[y]
    d=ANS[y+1]

    sc-=score(a,b)+score(b,c)+score(c,d)
    sc+=score(a,c)+score(c,b)+score(b,d)

    return sc

def last_score(ANS):
    sc=0
    for i in range(len(ANS)):
        if i==0:
            sc+=score(-1,ANS[0])
        else:
            sc+=score(ANS[i-1],ANS[i])

    return sc
    
while time.time()-time0<4.7:
    k=randint(0,len(ANS)-2)

    if score_reverse(k,k+1)<0:
        ANS[k],ANS[k+1]=ANS[k+1],ANS[k]

print(*ANS)

yukicoder

結果

テストケース

ソースコード