結果
問題 |
No.2796 Small Matryoshka
|
ユーザー |
|
提出日時 | 2024-06-28 21:57:19 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 750 bytes |
コンパイル時間 | 3,067 ms |
コンパイル使用メモリ | 173,080 KB |
実行使用メモリ | 6,948 KB |
最終ジャッジ日時 | 2024-06-28 21:57:26 |
合計ジャッジ時間 | 3,724 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 8 WA * 11 |
ソースコード
#include<bits/stdc++.h> using namespace std; #ifdef LOCAL #include "../debug.h" #else #define dbg(...) #endif int32_t main() { ios_base::sync_with_stdio(0); cin.tie(0); int N; cin >> N; vector<int> L(N), R(N); for(int i = 0 ; i < N ; ++i) { cin >> L[i] >> R[i]; } vector<int> dp(N + 1), ord(N); iota(ord.begin(), ord.end(), 0); sort(ord.begin(), ord.end(), [&](int i, int j) { return R[i] < R[j]; }); for(int i = 0 ; i < N ; ++i) { int lo = -1, hi = i; while(hi - lo > 1) { int mid = (lo + hi) / 2; if(L[ord[i]] >= R[ord[mid]]) lo = mid; else hi = mid; } dp[i + 1] = max(dp[hi] + 1, dp[i]); dbg(i, dp[i + 1]); } cout << N - dp[N] << '\n'; return 0; }