結果
問題 | No.2543 Many Meetings |
ユーザー |
![]() |
提出日時 | 2023-11-15 03:50:25 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 286 ms / 2,000 ms |
コード長 | 1,474 bytes |
コンパイル時間 | 3,350 ms |
コンパイル使用メモリ | 259,700 KB |
実行使用メモリ | 37,496 KB |
最終ジャッジ日時 | 2024-09-26 04:32:50 |
合計ジャッジ時間 | 11,790 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 40 |
ソースコード
#include <bits/stdc++.h> using namespace std; using P = pair<int, int>; int main(){ int N, K; cin >> N >> K; vector<int> L(N), R(N); vector<P> v(N); for(int i = 0; i < N; i++){ cin >> L[i] >> R[i]; v[i] = P(L[i], R[i]); } sort(v.begin(), v.end()); vector<P> w; for(int idx = 0; auto [l, r] : v){ w.emplace_back(l, idx); w.emplace_back(r, -(idx + 1)); idx++; } sort(w.begin(), w.end()); const int B = 20; vector<vector<int>> doubling(N, vector<int>(B, -1)); priority_queue<P, vector<P>, greater<P>> pq; for(int i = (int)w.size() - 1; i >= 0; i--){ auto [t, idx] = w[i]; if(idx >= 0){ pq.emplace(v[idx].second, idx); }else if(!pq.empty()){ auto [tt, tidx] = pq.top(); doubling[-1 * idx - 1][0] = tidx; } } for(int i = 0; i < B - 1; i++){ for(int j = 0; j < N; j++){ if(doubling[j][i] == -1) continue; doubling[j][i + 1] = doubling[doubling[j][i]][i]; } } const int inf = 1'000'000'100; // 1e9 + 100 int ans = inf; for(int i = 0; i < N; i++){ int cur = i; for(int j = 0; j < B; j++){ if(cur == -1) break; if(((K - 1) >> j) & 1) cur = doubling[cur][j]; } if(cur != -1) ans = min(ans, v[cur].second - v[i].first); } if(ans != inf) cout << ans << endl; else cout << -1 << endl; }