結果
問題 | No.808 Kaiten Sushi? |
ユーザー | 沙耶花 |
提出日時 | 2020-12-08 14:28:57 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 799 ms / 2,000 ms |
コード長 | 1,603 bytes |
コンパイル時間 | 2,299 ms |
コンパイル使用メモリ | 215,732 KB |
実行使用メモリ | 18,944 KB |
最終ジャッジ日時 | 2023-10-17 17:14:10 |
合計ジャッジ時間 | 17,272 ms |
ジャッジサーバーID (参考情報) |
judge15 / judge13 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
4,348 KB |
testcase_01 | AC | 2 ms
4,348 KB |
testcase_02 | AC | 2 ms
4,348 KB |
testcase_03 | AC | 2 ms
4,348 KB |
testcase_04 | AC | 2 ms
4,348 KB |
testcase_05 | AC | 2 ms
4,348 KB |
testcase_06 | AC | 2 ms
4,348 KB |
testcase_07 | AC | 6 ms
4,348 KB |
testcase_08 | AC | 6 ms
4,348 KB |
testcase_09 | AC | 12 ms
4,348 KB |
testcase_10 | AC | 8 ms
4,348 KB |
testcase_11 | AC | 6 ms
4,348 KB |
testcase_12 | AC | 8 ms
4,348 KB |
testcase_13 | AC | 7 ms
4,348 KB |
testcase_14 | AC | 4 ms
4,348 KB |
testcase_15 | AC | 11 ms
4,348 KB |
testcase_16 | AC | 9 ms
4,348 KB |
testcase_17 | AC | 5 ms
4,348 KB |
testcase_18 | AC | 3 ms
4,348 KB |
testcase_19 | AC | 3 ms
4,348 KB |
testcase_20 | AC | 4 ms
4,348 KB |
testcase_21 | AC | 3 ms
4,348 KB |
testcase_22 | AC | 3 ms
4,348 KB |
testcase_23 | AC | 179 ms
10,608 KB |
testcase_24 | AC | 138 ms
7,828 KB |
testcase_25 | AC | 165 ms
10,456 KB |
testcase_26 | AC | 155 ms
10,336 KB |
testcase_27 | AC | 498 ms
17,848 KB |
testcase_28 | AC | 127 ms
7,476 KB |
testcase_29 | AC | 463 ms
17,584 KB |
testcase_30 | AC | 284 ms
11,392 KB |
testcase_31 | AC | 523 ms
18,088 KB |
testcase_32 | AC | 602 ms
18,808 KB |
testcase_33 | AC | 278 ms
11,360 KB |
testcase_34 | AC | 329 ms
11,848 KB |
testcase_35 | AC | 418 ms
17,104 KB |
testcase_36 | AC | 277 ms
11,304 KB |
testcase_37 | AC | 2 ms
4,348 KB |
testcase_38 | AC | 2 ms
4,348 KB |
testcase_39 | AC | 715 ms
18,384 KB |
testcase_40 | AC | 133 ms
7,284 KB |
testcase_41 | AC | 127 ms
7,444 KB |
testcase_42 | AC | 543 ms
17,408 KB |
testcase_43 | AC | 179 ms
10,272 KB |
testcase_44 | AC | 398 ms
11,848 KB |
testcase_45 | AC | 180 ms
10,272 KB |
testcase_46 | AC | 93 ms
7,052 KB |
testcase_47 | AC | 793 ms
18,944 KB |
testcase_48 | AC | 780 ms
18,944 KB |
testcase_49 | AC | 799 ms
18,944 KB |
testcase_50 | AC | 788 ms
18,944 KB |
testcase_51 | AC | 799 ms
18,944 KB |
testcase_52 | AC | 556 ms
17,136 KB |
testcase_53 | AC | 788 ms
18,808 KB |
testcase_54 | AC | 2 ms
4,348 KB |
testcase_55 | AC | 2 ms
4,348 KB |
testcase_56 | AC | 2 ms
4,348 KB |
testcase_57 | AC | 246 ms
10,368 KB |
testcase_58 | AC | 401 ms
11,528 KB |
ソースコード
#include <bits/stdc++.h> #include <atcoder/segtree> using namespace atcoder; using namespace std; #define rep(i,n) for (int i = 0; i < (n); ++i) #define Inf 1000000000000000000 array<int,2> op(array<int,2> a,array<int,2> b){ rep(i,2)a[i] = max(a[i],b[i]); return a; } array<int,2> e(){ return array<int,2>{-1,-1}; } int main(){ int N; cin>>N; long long L; cin>>L; vector<pair<long long,int>> V(2*N); rep(i,N){ scanf("%lld",&V[i].first); V[i].second = 0; } rep(i,N){ scanf("%lld",&V[i+N].first); V[i+N].second = 1; } sort(V.begin(),V.end()); vector<array<int,2>> y(4*N,e()); rep(i,2*N){ y[i][V[i].second] = i; y[i+2*N][V[i].second] = 2*N+i; } segtree<array<int,2>,op,e> seg(y); vector<int> ans; int now = 0; while(ans.size()!=2*N){ int temp = 0; if(ans.size()>0)temp = ans.back(); int ok = 4*N,ng = temp; while(ok-ng>1){ int mid = (ok+ng)/2; array<int,2> ret = seg.prod(temp,mid); if(ret[now]==-1)ng = mid; else ok = mid; } int x; { array<int,2> ret = seg.prod(temp,ok); x = ret[now^1]; } ok = temp,ng = 4*N; while(ng-ok>1){ int mid = (ok+ng)/2; array<int,2> ret = seg.prod(temp,mid); if(ret[now^1]<=x)ok = mid; else ng = mid; } array<int,2> ret = seg.prod(temp,ok); x = ret[now]%(2*N); ans.push_back(x); seg.set(x,e()); seg.set(x+2*N,e()); now ^= 1; } long long Ans = 0LL; rep(i,2*N){ if(i==0)Ans += V[ans[i]].first; else{ long long temp = V[ans[i]].first - V[ans[i-1]].first; if(temp<0)temp += L; Ans += temp; } } cout<<Ans<<endl; return 0; }