結果
問題 | No.2543 Many Meetings |
ユーザー |
![]() |
提出日時 | 2023-11-24 22:33:10 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 532 ms / 2,000 ms |
コード長 | 1,837 bytes |
コンパイル時間 | 1,502 ms |
コンパイル使用メモリ | 130,708 KB |
実行使用メモリ | 77,748 KB |
最終ジャッジ日時 | 2024-09-26 09:37:34 |
合計ジャッジ時間 | 10,956 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 40 |
ソースコード
#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; }