結果
問題 | No.3134 二分探索木 |
ユーザー |
![]() |
提出日時 | 2025-05-02 22:53:43 |
言語 | C (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 85 ms / 2,000 ms |
コード長 | 1,986 bytes |
コンパイル時間 | 1,065 ms |
コンパイル使用メモリ | 26,368 KB |
実行使用メモリ | 9,600 KB |
最終ジャッジ日時 | 2025-05-02 22:53:47 |
合計ジャッジ時間 | 3,554 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 5 |
other | AC * 15 |
コンパイルメッセージ
main.c: In function ‘main’: main.c:78:9: warning: ignoring return value of ‘scanf’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 78 | scanf("%d", &n); | ^~~~~~~~~~~~~~~ main.c:82:17: warning: ignoring return value of ‘scanf’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 82 | scanf("%d", &a[i]); | ^~~~~~~~~~~~~~~~~~
ソースコード
#include<stdio.h> int min(int a, int b) { if (a < b) return a; else return b; } int max(int a, int b) { if (a > b) return a; else return b; } int seg_min[800005], seg_max[800005], ss; void update_min(int x, int v) { x += ss - 1; seg_min[x] = v; while (x > 0) { x = (x - 1) / 2; seg_min[x] = min(seg_min[2 * x + 1], seg_min[2 * x + 2]); } return; } void update_max(int x, int v) { x += ss - 1; seg_max[x] = v; while (x > 0) { x = (x - 1) / 2; seg_max[x] = max(seg_max[2 * x + 1], seg_max[2 * x + 2]); } return; } int n; int get_min(int l, int r) { l += ss - 1; r += ss - 1; int res = n; while (l < r) { res = min(res, seg_min[l]); l /= 2; res = min(res, seg_min[r]); r = r / 2 - 1; } if (l == r) res = min(res, seg_min[l]); return res; } int get_max(int l, int r) { l += ss - 1; r += ss - 1; int res = -1; while (l < r) { res = max(res, seg_max[l]); l /= 2; res = max(res, seg_max[r]); r = r / 2 - 1; } if (l == r) res = max(res, seg_max[l]); return res; } int a[200005]; int a_inv[200005]; int b[200005], c[200005]; int par[200005]; int main() { scanf("%d", &n); int i, j, k; for (i = 0; i < n; i++) { scanf("%d", &a[i]); a[i]--; } for (i = 0; i < n; i++) a_inv[a[i]] = i; for (ss = 1; ss < n; ss *= 2); for (i = 0; i < n; i++) b[i] = c[i] = 0; for (i = 0; i < 2 * ss - 1; i++) { seg_min[i] = n; seg_max[i] = -1; } update_min(a[0], a[0]); update_max(a[0], a[0]); for (i = 1; i < n; i++) { j = get_max(0, a[i]); k = get_min(a[i], n - 1); if (j < 0) j = a_inv[k]; else if (k >= n) j = a_inv[j]; else { j = a_inv[j]; k = a_inv[k]; if (b[j] < b[k]) j = k; } b[i] = b[j] + 1; par[i] = j; update_min(a[i], a[i]); update_max(a[i], a[i]); } for (i = n - 1; i > 0; i--) c[par[i]] += c[i] + 1; for (i = 0; i < n - 1; i++) printf("%d ", b[i]); printf("%d\n", b[i]); for (i = 0; i < n - 1; i++) printf("%d ", c[i]); printf("%d\n", c[i]); return 0; }