結果
問題 | No.2543 Many Meetings |
ユーザー |
![]() |
提出日時 | 2024-10-21 10:29:26 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,352 bytes |
コンパイル時間 | 2,033 ms |
コンパイル使用メモリ | 203,240 KB |
最終ジャッジ日時 | 2025-02-24 22:09:40 |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 WA * 1 |
other | AC * 9 WA * 31 |
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; int main(){ cin.tie(nullptr); ios_base::sync_with_stdio(false); ll N, K, L, R, r=1, ans=1e18; cin >> N >> K; K--; vector<pair<ll, ll>> RL(N+1); for (int i=1; i<=N; i++){ cin >> L >> R; RL[i] = {R, L}; } if (K == 1){ for (auto [R, L] : RL) ans = min(ans, R-L); cout << ans << endl; return 0; } sort(RL.begin(), RL.end()); /* f(i) = iのミーティングに参加したとき、次に参加するミーティング R_i<=L_jかつR_jが最小のものを選ぶ f^(K-1)(i)<=NならOK */ vector<ll> dp(N+2), v(N+2); for (int l=1; l<=N; l++){ while(r <= N && RL[l].first > RL[r].second) r++; dp[l] = r; } iota(v.begin(), v.end(), 0); dp[N+1] = N+1; //for (int i=1; i<=N; i++) cout << dp[i] << " "; //cout << endl; while(K){ if (K&1){ for (int i=1; i<=N; i++) v[i] = v[dp[i]]; } vector<ll> pd(N+2); for (int i=1; i<=N; i++) pd[i] = dp[dp[i]]; swap(dp, pd); K >>= 1; } for (int i=1; i<=N; i++){ if (v[i] <= N){ ans = min(ans, RL[v[i]].first-RL[i].second); } } cout << (ans != 1e18 ? ans : -1) << endl; return 0; }