結果
問題 | No.2543 Many Meetings |
ユーザー |
![]() |
提出日時 | 2024-06-19 11:12:50 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,783 bytes |
コンパイル時間 | 685 ms |
コンパイル使用メモリ | 59,572 KB |
最終ジャッジ日時 | 2025-02-21 23:18:08 |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 32 WA * 8 |
コンパイルメッセージ
main.cpp: In function ‘int main()’: main.cpp:35:8: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 35 | scanf("%d%d", &n, &k); | ~~~~~^~~~~~~~~~~~~~~~ main.cpp:39:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 39 | scanf("%d%d", ls + i, rs + i); | ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
ソースコード
/* -*- coding: utf-8 -*-** 2543.cc: No.2543 Many Meetings - yukicoder*/#include<cstdio>#include<vector>#include<algorithm>using namespace std;/* constant */const int MAX_N = 200000;const int MAX_M = MAX_N * 2;const int BN = 19;const int INF = 1 << 30;/* typedef */using vi = vector<int>;/* global variables */int ls[MAX_N], rs[MAX_N], uxs[MAX_M];vi nbrs[MAX_M];int dp[MAX_M], ps[MAX_M][BN];/* subroutines *//* main */int main() {int n, k;scanf("%d%d", &n, &k);int m = 0;for (int i = 0; i < n; i++) {scanf("%d%d", ls + i, rs + i);uxs[m++] = ls[i], uxs[m++] = rs[i];}sort(uxs, uxs + m);m = unique(uxs, uxs + m) - uxs;for (int i = 0; i < n; i++) {int li = lower_bound(uxs, uxs + m, ls[i]) - uxs;int ri = lower_bound(uxs, uxs + m, rs[i]) - uxs;nbrs[li].push_back(ri);}fill(dp, dp + m, -1);dp[0] = 0, ps[0][0] = -1;for (int i = 0; i < m; i++) {if (i + 1 < m) {if (dp[i + 1] < dp[i] ||(dp[i + 1] == dp[m] && ps[i + 1][0] < ps[i][0]))dp[i + 1] = dp[i], ps[i + 1][0] = ps[i][0];}for (auto j: nbrs[i]) {if (dp[j] < dp[i] + 1 ||(dp[j] == dp[i] + 1 && ps[j][0] < ps[i][0]))dp[j] = dp[i] + 1, ps[j][0] = i;}}//for (int i = 0; i < m; i++)//printf(" %d,%d,%d", uxs[i], dp[i], ps[i][0]);//putchar('\n');if (dp[m - 1] < k) { puts("-1"); return 0; }for (int i = 0; i < BN - 1; i++)for (int u = 0; u < m; u++)ps[u][i + 1] = (ps[u][i] >= 0) ? ps[ps[u][i]][i] : -1;int minl = INF;for (int u = m - 1; u >= 0 && dp[u] >= k; u--) {int v = u;for (int i = 0, bi = 1; i < BN; i++, bi <<= 1)if (k & bi) v = ps[v][i];minl = min(minl, uxs[u] - uxs[v]);}printf("%d\n", minl);return 0;}