結果
問題 |
No.2543 Many Meetings
|
ユーザー |
|
提出日時 | 2023-12-08 11:37:38 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 898 bytes |
コンパイル時間 | 3,268 ms |
コンパイル使用メモリ | 264,996 KB |
実行使用メモリ | 39,168 KB |
最終ジャッジ日時 | 2024-09-27 02:44:22 |
合計ジャッジ時間 | 8,860 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 18 WA * 22 |
ソースコード
#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); vector<vector<ll>> nxt(20, vector<ll>(N, -1)); for(ll i = 0; i < N; i++) { auto it = ranges::lower_bound(v, make_pair(v[i].second, 0LL)); if(it != v.end()) { nxt[0][i] = it - v.begin(); } } for(ll i = 0; i < 20; 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"; }