結果
問題 | No.2543 Many Meetings |
ユーザー |
|
提出日時 | 2023-12-08 12:01:47 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 242 ms / 2,000 ms |
コード長 | 1,304 bytes |
コンパイル時間 | 3,629 ms |
コンパイル使用メモリ | 278,792 KB |
実行使用メモリ | 53,120 KB |
最終ジャッジ日時 | 2024-09-27 02:47:08 |
合計ジャッジ時間 | 9,362 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 40 |
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; int main() { ios::sync_with_stdio(false); cin.tie(0); ll N, K; cin >> N >> K; vector<pair<ll, ll>> v(N); for(auto &[x, y] : v) { cin >> x >> y; } ranges::sort(v, {}, &pair<ll, ll>::second); set<tuple<ll, ll, ll>> s; for(ll i = 0; i < N; i++) { auto [l, r] = v[i]; s.emplace(r, l, i); } vector<ll> sortidx(N); iota(sortidx.begin(), sortidx.end(), 0); ranges::sort(sortidx, [&](auto i, auto j) { return v[i] < v[j]; }); vector<vector<ll>> nxt(20, vector<ll>(N, -1)); ll idx = 0; for(ll i = 0; i < N; i++) { auto [l, r] = v[i]; while(idx < N && v[sortidx[idx]].first < r) { s.erase({v[sortidx[idx]].second, v[sortidx[idx]].first, sortidx[idx]}); idx++; } if(s.empty()) { break; } nxt[0][i] = get<2>(*s.begin()); } for(ll i = 0; i < 19; i++) { for(ll j = 0; j < N; j++) { if(nxt[i][j] == -1) { continue; } nxt[i + 1][j] = nxt[i][nxt[i][j]]; } } ll r = 1e18; for(ll i = 0; i < N; i++) { ll k = K - 1, cur = i; while(k && cur != -1) { ll t = __builtin_ctz(k); cur = nxt[t][cur]; k ^= 1 << t; } if(cur != -1) { r = min(r, v[cur].second - v[i].first); } } cout << (r == 1e18 ? -1 : r) << "\n"; }