結果
問題 | No.1804 Intersection of LIS |
ユーザー |
👑 |
提出日時 | 2022-01-07 23:15:13 |
言語 | C (gcc 13.3.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,202 bytes |
コンパイル時間 | 289 ms |
コンパイル使用メモリ | 30,976 KB |
実行使用メモリ | 12,452 KB |
最終ジャッジ日時 | 2024-11-14 09:14:44 |
合計ジャッジ時間 | 3,213 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
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] = {}, sec[300001] = {}, prev[300001] = {}, lis[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] = {}, cand[300001] = {};for (i = dp[k], cand[k] = i; 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]]) && cand[lis[i]] == i) ans++;else flag[i] = 0;}if (P[i] < last[lis[i]]) {if (P[i] > last[lis[i]-1]) last[lis[i]-1] = P[i];if (cand[lis[i]-1] == 0) cand[lis[i]-1] = prev[i];else if (cand[lis[i]-1] != prev[i]) cand[lis[i]-1] = -1;}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;}