結果
問題 | No.2543 Many Meetings |
ユーザー | momoyuu |
提出日時 | 2023-11-24 22:33:10 |
言語 | C++23 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 559 ms / 2,000 ms |
コード長 | 1,837 bytes |
コンパイル時間 | 1,589 ms |
コンパイル使用メモリ | 132,444 KB |
実行使用メモリ | 77,832 KB |
最終ジャッジ日時 | 2023-11-24 22:33:42 |
合計ジャッジ時間 | 11,261 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge13 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
6,676 KB |
testcase_01 | AC | 2 ms
6,676 KB |
testcase_02 | AC | 2 ms
6,676 KB |
testcase_03 | AC | 336 ms
77,832 KB |
testcase_04 | AC | 401 ms
77,832 KB |
testcase_05 | AC | 371 ms
77,832 KB |
testcase_06 | AC | 353 ms
77,828 KB |
testcase_07 | AC | 340 ms
77,832 KB |
testcase_08 | AC | 334 ms
77,652 KB |
testcase_09 | AC | 317 ms
77,652 KB |
testcase_10 | AC | 310 ms
77,652 KB |
testcase_11 | AC | 310 ms
77,656 KB |
testcase_12 | AC | 372 ms
77,652 KB |
testcase_13 | AC | 315 ms
62,800 KB |
testcase_14 | AC | 173 ms
37,180 KB |
testcase_15 | AC | 194 ms
36,508 KB |
testcase_16 | AC | 270 ms
52,708 KB |
testcase_17 | AC | 335 ms
59,764 KB |
testcase_18 | AC | 548 ms
69,708 KB |
testcase_19 | AC | 524 ms
63,780 KB |
testcase_20 | AC | 530 ms
64,344 KB |
testcase_21 | AC | 559 ms
74,336 KB |
testcase_22 | AC | 498 ms
62,568 KB |
testcase_23 | AC | 2 ms
6,676 KB |
testcase_24 | AC | 2 ms
6,676 KB |
testcase_25 | AC | 2 ms
6,676 KB |
testcase_26 | AC | 2 ms
6,676 KB |
testcase_27 | AC | 2 ms
6,676 KB |
testcase_28 | AC | 213 ms
57,952 KB |
testcase_29 | AC | 49 ms
21,760 KB |
testcase_30 | AC | 58 ms
22,016 KB |
testcase_31 | AC | 42 ms
18,816 KB |
testcase_32 | AC | 157 ms
54,156 KB |
testcase_33 | AC | 2 ms
6,676 KB |
testcase_34 | AC | 2 ms
6,676 KB |
testcase_35 | AC | 2 ms
6,676 KB |
testcase_36 | AC | 2 ms
6,676 KB |
testcase_37 | AC | 2 ms
6,676 KB |
testcase_38 | AC | 2 ms
6,676 KB |
testcase_39 | AC | 2 ms
6,676 KB |
testcase_40 | AC | 2 ms
6,676 KB |
testcase_41 | AC | 2 ms
6,676 KB |
testcase_42 | AC | 2 ms
6,676 KB |
ソースコード
#include<algorithm> #include<iostream> #include<vector> #include<map> #include<cassert> #include<set> #include<queue> #include<cstdint> #include<unordered_map> using namespace std; using ll = long long; #include<stack> int main(){ cin.tie(nullptr); ios::sync_with_stdio(false); int k,n; cin>>n>>k; vector<ll> l(n),r(n); for(int i = 0;i<n;i++) cin>>l[i]>>r[i]; vector<int> idx(n); for(int i = 0;i<n;i++) idx[i] = i; sort(idx.begin(),idx.end(),[&](int i,int j){ return r[i] < r[j];}); vector<pair<ll,ll>> use; for(int i = 0;i<n;i++){ int ni = idx[i]; if(!use.empty()&&use.back().first>=l[ni]) continue; use.push_back(make_pair(l[ni],i)); } const int B = 40; vector<vector<ll>> dp(n,vector<ll>(B+1,2e9)); for(int i = 0;i<n;i++){ dp[i][0] = r[idx[i]]; } for(int i = 1;i<=B;i++){ for(int j = 0;j<n;j++){ ll now = dp[j][i-1]; if(now==2e9) continue; int ni = lower_bound(use.begin(),use.end(),make_pair(now,(ll)-1)) - use.begin(); if(ni==use.size()) dp[j][i] = (ll)2e9; else{ ll nj = use[ni].second; dp[j][i] = dp[nj][i-1]; } } } ll ans = 1e18; for(int i = 0;i<n;i++){ ll want = k; ll ni = l[idx[i]]; for(int j = 0;j<=B;j++){ if(~want>>j&1) continue; int nj = lower_bound(use.begin(),use.end(),make_pair(ni,(ll)-1)) - use.begin(); if(nj==use.size()) { ni = 2e9; break; } ni = use[nj].second; ni = dp[ni][j]; if(ni==2e9) break; } if(ni==2e9) continue; ans = min(ans,ni-l[idx[i]]); } if(ans==1e18) ans = -1; cout<<ans<<endl; }