結果
問題 | No.2543 Many Meetings |
ユーザー |
![]() |
提出日時 | 2024-06-19 13:21:08 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 103 ms / 2,000 ms |
コード長 | 1,434 bytes |
コンパイル時間 | 659 ms |
コンパイル使用メモリ | 46,972 KB |
最終ジャッジ日時 | 2025-02-21 23:18:13 |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 40 |
コンパイルメッセージ
main.cpp: In function ‘int main()’: main.cpp:33:8: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 33 | scanf("%d%d", &n, &k); | ~~~~~^~~~~~~~~~~~~~~~ main.cpp:34:36: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 34 | for (int i = 0; i < n; i++) scanf("%d%d", ls + i, rs + i); | ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
ソースコード
/* -*- coding: utf-8 -*-** 2543.cc: No.2543 Many Meetings - yukicoder*/#include<cstdio>#include<algorithm>#include<utility>using namespace std;/* constant */const int MAX_N = 200000;const int BN = 18;const int INF = 1 << 30;/* typedef */using pii = pair<int,int>;/* global variables */int ls[MAX_N], rs[MAX_N], ps[MAX_N][BN];pii rls[MAX_N], lis[MAX_N];/* subroutines *//* main */int main() {int n, k;scanf("%d%d", &n, &k);for (int i = 0; i < n; i++) scanf("%d%d", ls + i, rs + i);for (int i = 0; i < n; i++) rls[i] = {rs[i], ls[i]};sort(rls, rls + n);int c = 0, m = 0;for (int i = 0, pr = 0; i < n; i++) {auto [ri, li] = rls[i];if (pr <= li) c++, pr = ri;if (m == 0 || lis[m - 1].first < li) lis[m++] = {li, i};}if (c < k) { puts("-1"); return 0; }for (int i = 0; i < n; i++) {auto [ri, li] = rls[i];int j = lower_bound(lis, lis + m, pii(ri, -1)) - lis;ps[i][0] = (j < m) ? lis[j].second : -1;}for (int i = 0; i < BN - 1; i++)for (int u = 0; u < n; u++)ps[u][i + 1] = (ps[u][i] >= 0) ? ps[ps[u][i]][i] : -1;int minl = INF;k--;for (int u = 0; u < n; u++) {int v = u;for (int i = 0, bi = 1; v >= 0 && i < BN; i++, bi <<= 1)if (k & bi) v = ps[v][i];if (v < 0) break;minl = min(minl, rls[v].first - rls[u].second);}printf("%d\n", (minl < INF) ? minl : -1);return 0;}