結果
問題 |
No.1804 Intersection of LIS
|
ユーザー |
|
提出日時 | 2025-01-01 16:18:22 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,524 bytes |
コンパイル時間 | 3,529 ms |
コンパイル使用メモリ | 250,860 KB |
実行使用メモリ | 11,288 KB |
最終ジャッジ日時 | 2025-01-01 16:18:30 |
合計ジャッジ時間 | 7,110 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 WA * 1 |
other | AC * 34 WA * 3 |
ソースコード
#include<bits/stdc++.h> using i64 = long long; using l64 = long double; void DAOQI() { int n; std::cin >> n; std::vector<int> a(n + 1); for (int i = 1; i <= n; i++) { std::cin >> a[i]; } std::vector<int> pre(n + 1), suf(n + 1), cnt(n + 1); auto calc = [&](std::vector<int> &vec) { std::vector<int> dp; for (int i = 1; i <= n; i++) { if (dp.empty() || a[i] > dp.back()) { dp.push_back(a[i]); vec[i] = dp.size(); } else { int p = std::lower_bound(dp.begin(), dp.end(), a[i]) - dp.begin(); vec[i] = p + 1; dp[p] = a[i]; } } return dp.size(); }; int len = calc(pre); std::reverse(a.begin() + 1, a.end()); for (int i = 1; i <= n; i++) a[i] = -a[i]; calc(suf); std::reverse(suf.begin() + 1, suf.end()); std::reverse(a.begin() + 1, a.end()); std::vector<int> ans; for (int i = 1; i <= n; i++) { a[i] = -a[i]; if (pre[i] + suf[i] - 1 == len) { cnt[pre[i]]++; } } for (int i = 1; i <= n; i++) { if (pre[i] + suf[i] - 1 == len && cnt[pre[i]] == 1) { ans.push_back(a[i]); } } std::cout << ans.size() << "\n"; for (int x: ans) std::cout << x << " \n"[x == ans.back()]; } signed main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); int T = 1; //std::cin >> T; while (T--) DAOQI(); return 0; }