結果
問題 | No.1804 Intersection of LIS |
ユーザー |
👑 |
提出日時 | 2022-01-07 23:37:56 |
言語 | C (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 92 ms / 2,000 ms |
コード長 | 936 bytes |
コンパイル時間 | 403 ms |
コンパイル使用メモリ | 30,976 KB |
実行使用メモリ | 7,720 KB |
最終ジャッジ日時 | 2024-11-14 09:17:34 |
合計ジャッジ時間 | 3,507 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 37 |
ソースコード
#include <stdio.h>int main(){int i, N, P[300001];scanf("%d", &N);for (i = 1; i <= N; i++) scanf("%d", &(P[i]));int k = 0, l, r, m, dp[300001] = {}, prev[300001], ans[2][300001];for (i = 1; i <= N; i++) {l = 0;r = k;while (l < r) {m = (l + r + 1) / 2;if (P[dp[m]] > P[i]) r = m - 1;else l = m;}if (l == k) k++;prev[i] = dp[l];dp[l+1] = i;}for (i = dp[k]; i > 0; i = prev[i]) ans[0][k--] = P[i];int j;for (i = N, k = 0; i >= 1; i--) {l = 0;r = k;while (l < r) {m = (l + r + 1) / 2;if (P[dp[m]] < P[i]) r = m - 1;else l = m;}if (l == k) k++;prev[i] = dp[l];dp[l+1] = i;}for (i = dp[k], j = 1; i > 0; i = prev[i]) ans[1][j++] = P[i];for (i = 1, j = 0; i <= k; i++) if (ans[0][i] == ans[1][i]) j++;printf("%d\n", j);for (i = 1; i <= k; i++) if (ans[0][i] == ans[1][i]) printf("%d ", ans[0][i]);printf("\n");fflush(stdout);return 0;}