結果
問題 |
No.5011 Better Mo's Algorithm is Needed!! (Weighted)
|
ユーザー |
![]() |
提出日時 | 2022-12-17 14:45:55 |
言語 | cLay (20241019-1) |
結果 |
AC
|
実行時間 | 4,966 ms / 5,000 ms |
コード長 | 839 bytes |
コンパイル時間 | 3,586 ms |
実行使用メモリ | 18,392 KB |
スコア | 42,667,521,828 |
最終ジャッジ日時 | 2022-12-17 14:56:48 |
合計ジャッジ時間 | 647,151 ms |
ジャッジサーバーID (参考情報) |
judge16 / judge12 |
純コード判定しない問題か言語 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 120 |
ソースコード
ull xs[2d5]; ll ys[2d5]; ll ls[2d5],rs[2d5]; ll d(ll i,ll j){ return abs(ls[ys[j]]-ls[ys[i]])+abs(rs[ys[j]]-rs[ys[i]]); } void opt1(ll b){ rep(i,2d5-1-b){ if(d(i,i+1)+d(i+b,i+b+1)>d(i,i+b)+d(i+1,i+b+1)){ reverse(ys+(i+1),ys+(i+1+b)); } } } { Timer timer; timer.set(); ll@n,@q,@wt,@st,w[n+1]; rep(i,n){ ll@wi; w[i+1]=w[i]+wi; } rep(i,q){ ll@l,@r; ls[i]=l=w[l-1]; rs[i]=r=w[r]; ll m=w[n]+1>>1; ull x=0; rep(32){ x<<=2; if(r<m){ x|=0; (l,r)=(l,r); }else if(l>=m){ x|=3; (l,r)=(l-m,r-m); }else if(l+r<2m){ x|=1; (l,r)=(r-m,m-1-l); }else{ x|=2; (l,r)=(2m-1-r,l); } l*=2; r*=2; } xs[i]=x; ys[i]=i; } sortA(q,xs,ys); rrep(i,4096){ long k=i%512+2; opt1(k); if(timer.get()>=4.95){ break; } } rep(i,q){ ys[i]+=1; } wt(ys(q)); }