結果
問題 | No.1804 Intersection of LIS |
ユーザー |
👑 |
提出日時 | 2022-01-07 22:55:20 |
言語 | C (gcc 13.3.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,024 bytes |
コンパイル時間 | 278 ms |
コンパイル使用メモリ | 30,848 KB |
実行使用メモリ | 11,248 KB |
最終ジャッジ日時 | 2024-11-14 09:00:54 |
合計ジャッジ時間 | 3,466 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 10 WA * 27 |
ソースコード
#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] = {}, lis[300001] = {}, sec[300001] = {}, num[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++;else sec[i] = P[dp[l+1]];dp[l+1] = i;prev[i] = dp[l];num[l+1]++;lis[i] = l + 1;}int last[300001] = {}, ans = 0, flag[300001] = {};for (i = dp[k]; i > 0; i = prev[i]) flag[i] = 1;for (i = N, last[k] = N + 1; i >= 1; i--) {num[lis[i]]--;if (flag[i] != 0) {if (k == lis[i] && (num[lis[i]] == 0 || sec[i] > last[lis[i]])) ans++;else flag[i] = 0;}if (P[i] < last[lis[i]] && P[i] > last[lis[i]-1]) last[lis[i]-1] = P[i];while (k > 0 && num[k] == 0) k--;}printf("%d\n", ans);for (i = 1; i <= N; i++) if (flag[i] != 0) printf("%d ", P[i]);printf("\n");fflush(stdout);return 0;}