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

提出ソース

結果

問題	No.5011 Better Mo's Algorithm is Needed!! (Weighted)
ユーザー	titia
提出日時	2022-12-17 03:28:10
言語	PyPy3 (7.3.15)
結果	AC
実行時間	4,868 ms / 5,000 ms
コード長	1,812 bytes
コンパイル時間	934 ms
実行使用メモリ	186,968 KB
スコア	37,016,148,509
最終ジャッジ日時	2022-12-17 03:38:49
合計ジャッジ時間	633,058 ms
ジャッジサーバーID （参考情報）	judge14 / judge12
	純コード判定しない問題か言語

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	4,859 ms 177,172 KB
testcase_01	AC	4,859 ms 182,668 KB
testcase_02	AC	4,853 ms 180,572 KB
testcase_03	AC	4,851 ms 179,700 KB
testcase_04	AC	4,857 ms 183,828 KB
testcase_05	AC	4,850 ms 175,752 KB
testcase_06	AC	4,863 ms 182,304 KB
testcase_07	AC	4,858 ms 186,100 KB
testcase_08	AC	4,863 ms 180,464 KB
testcase_09	AC	4,855 ms 182,004 KB
testcase_10	AC	4,858 ms 182,612 KB
testcase_11	AC	4,852 ms 179,996 KB
testcase_12	AC	4,849 ms 180,892 KB
testcase_13	AC	4,852 ms 185,324 KB
testcase_14	AC	4,853 ms 178,424 KB
testcase_15	AC	4,855 ms 179,280 KB
testcase_16	AC	4,855 ms 183,784 KB
testcase_17	AC	4,853 ms 182,516 KB
testcase_18	AC	4,864 ms 177,228 KB
testcase_19	AC	4,846 ms 181,240 KB
testcase_20	AC	4,853 ms 168,432 KB
testcase_21	AC	4,849 ms 178,240 KB
testcase_22	AC	4,852 ms 184,892 KB
testcase_23	AC	4,857 ms 181,216 KB
testcase_24	AC	4,851 ms 180,576 KB
testcase_25	AC	4,856 ms 182,948 KB
testcase_26	AC	4,853 ms 181,476 KB
testcase_27	AC	4,860 ms 181,476 KB
testcase_28	AC	4,857 ms 184,064 KB
testcase_29	AC	4,868 ms 185,072 KB
testcase_30	AC	4,849 ms 177,196 KB
testcase_31	AC	4,852 ms 182,712 KB
testcase_32	AC	4,852 ms 179,144 KB
testcase_33	AC	4,848 ms 180,168 KB
testcase_34	AC	4,851 ms 185,348 KB
testcase_35	AC	4,850 ms 181,016 KB
testcase_36	AC	4,853 ms 170,436 KB
testcase_37	AC	4,848 ms 183,204 KB
testcase_38	AC	4,847 ms 183,624 KB
testcase_39	AC	4,850 ms 180,304 KB
testcase_40	AC	4,856 ms 183,468 KB
testcase_41	AC	4,845 ms 182,092 KB
testcase_42	AC	4,859 ms 182,056 KB
testcase_43	AC	4,854 ms 185,292 KB
testcase_44	AC	4,861 ms 183,288 KB
testcase_45	AC	4,854 ms 178,716 KB
testcase_46	AC	4,853 ms 183,356 KB
testcase_47	AC	4,851 ms 184,944 KB
testcase_48	AC	4,845 ms 181,980 KB
testcase_49	AC	4,849 ms 182,404 KB
testcase_50	AC	4,847 ms 179,296 KB
testcase_51	AC	4,848 ms 180,616 KB
testcase_52	AC	4,855 ms 185,860 KB
testcase_53	AC	4,855 ms 178,256 KB
testcase_54	AC	4,848 ms 183,908 KB
testcase_55	AC	4,850 ms 186,968 KB
testcase_56	AC	4,844 ms 181,408 KB
testcase_57	AC	4,848 ms 182,272 KB
testcase_58	AC	4,853 ms 184,476 KB
testcase_59	AC	4,860 ms 183,392 KB
testcase_60	AC	4,855 ms 183,208 KB
testcase_61	AC	4,847 ms 180,132 KB
testcase_62	AC	4,847 ms 179,844 KB
testcase_63	AC	4,857 ms 178,152 KB
testcase_64	AC	4,853 ms 183,312 KB
testcase_65	AC	4,858 ms 183,420 KB
testcase_66	AC	4,852 ms 178,692 KB
testcase_67	AC	4,852 ms 185,024 KB
testcase_68	AC	4,849 ms 181,536 KB
testcase_69	AC	4,851 ms 179,072 KB
testcase_70	AC	4,855 ms 183,768 KB
testcase_71	AC	4,852 ms 179,992 KB
testcase_72	AC	4,860 ms 181,052 KB
testcase_73	AC	4,850 ms 182,520 KB
testcase_74	AC	4,847 ms 180,628 KB
testcase_75	AC	4,853 ms 179,564 KB
testcase_76	AC	4,857 ms 181,472 KB
testcase_77	AC	4,860 ms 180,856 KB
testcase_78	AC	4,848 ms 178,136 KB
testcase_79	AC	4,852 ms 184,604 KB
testcase_80	AC	4,854 ms 182,356 KB
testcase_81	AC	4,850 ms 178,980 KB
testcase_82	AC	4,853 ms 182,584 KB
testcase_83	AC	4,856 ms 179,104 KB
testcase_84	AC	4,856 ms 176,908 KB
testcase_85	AC	4,855 ms 181,336 KB
testcase_86	AC	4,861 ms 179,188 KB
testcase_87	AC	4,864 ms 180,880 KB
testcase_88	AC	4,852 ms 182,740 KB
testcase_89	AC	4,853 ms 181,440 KB
testcase_90	AC	4,854 ms 175,944 KB
testcase_91	AC	4,847 ms 185,088 KB
testcase_92	AC	4,854 ms 183,564 KB
testcase_93	AC	4,855 ms 176,932 KB
testcase_94	AC	4,853 ms 186,376 KB
testcase_95	AC	4,852 ms 180,724 KB
testcase_96	AC	4,847 ms 178,396 KB
testcase_97	AC	4,856 ms 181,408 KB
testcase_98	AC	4,850 ms 181,764 KB
testcase_99	AC	4,846 ms 179,236 KB
testcase_100	AC	4,859 ms 178,684 KB
testcase_101	AC	4,857 ms 182,236 KB
testcase_102	AC	4,852 ms 177,056 KB
testcase_103	AC	4,859 ms 183,684 KB
testcase_104	AC	4,861 ms 174,304 KB
testcase_105	AC	4,848 ms 182,124 KB
testcase_106	AC	4,848 ms 184,980 KB
testcase_107	AC	4,858 ms 183,508 KB
testcase_108	AC	4,847 ms 178,596 KB
testcase_109	AC	4,854 ms 183,772 KB
testcase_110	AC	4,847 ms 181,556 KB
testcase_111	AC	4,851 ms 177,228 KB
testcase_112	AC	4,846 ms 180,648 KB
testcase_113	AC	4,858 ms 183,868 KB
testcase_114	AC	4,843 ms 181,424 KB
testcase_115	AC	4,855 ms 182,380 KB
testcase_116	AC	4,843 ms 182,148 KB
testcase_117	AC	4,855 ms 181,100 KB
testcase_118	AC	4,861 ms 182,584 KB
testcase_119	AC	4,856 ms 181,580 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//500].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

結果

テストケース

ソースコード