結果
問題 | No.1804 Intersection of LIS |
ユーザー |
👑 |
提出日時 | 2022-01-07 23:24:48 |
言語 | C (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 77 ms / 2,000 ms |
コード長 | 817 bytes |
コンパイル時間 | 612 ms |
コンパイル使用メモリ | 30,592 KB |
実行使用メモリ | 8,932 KB |
最終ジャッジ日時 | 2024-11-14 09:15:46 |
合計ジャッジ時間 | 3,039 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
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] = {}, lis[300001] = {};for (i = 1; i <= N; i++) {l = 0;r = k;while (l < r) {m = (l + r + 1) / 2;if (dp[m] > P[i]) r = m - 1;else l = m;}if (l == k) k++;dp[l+1] = P[i];lis[i] = l + 1;}int last[300001] = {}, ans = 0, flag[300001] = {}, num[300001] = {};for (i = N, last[k] = N + 1; i >= 1; i--) {if (P[i] < last[lis[i]]) {num[lis[i]]++;flag[i] = 1;if (P[i] > last[lis[i]-1]) last[lis[i]-1] = P[i];}}for (i = 1; i <= k; i++) if (num[i] == 1) ans++;printf("%d\n", ans);for (i = 1; i <= N; i++) if (num[lis[i]] == 1 && flag[i] != 0) printf("%d ", P[i]);printf("\n");fflush(stdout);return 0;}