結果
| 問題 | No.1768 The frog in the well knows the great ocean. |
| ユーザー |
👑  ygussany
|
| 提出日時 | 2021-11-13 13:25:38 |
| 言語 | C (gcc 13.3.0) |
| 結果 |
AC
|
| 実行時間 | 139 ms / 3,000 ms |
| コード長 | 3,610 bytes |
| コンパイル時間 | 723 ms |
| コンパイル使用メモリ | 33,536 KB |
| 実行使用メモリ | 19,652 KB |
| 最終ジャッジ日時 | 2024-06-29 18:53:47 |
| 合計ジャッジ時間 | 3,838 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 |
| other | AC * 27 |
ソースコード
#include <stdio.h>typedef struct {long long key;int id;} data;typedef struct {data obj[200001];int size;} min_heap;void push(min_heap* h, data x){int i = ++(h->size), j = i >> 1;data tmp;h->obj[i] = x;while (j > 0) {if (h->obj[i].key < h->obj[j].key) {tmp = h->obj[j];h->obj[j] = h->obj[i];h->obj[i] = tmp;i = j;j >>= 1;} else break;}}data pop(min_heap* h){int i = 1, j = 2;data output = h->obj[1], tmp;h->obj[1] = h->obj[(h->size)--];while (j <= h->size) {if (j < h->size && h->obj[j^1].key < h->obj[j].key) j ^= 1;if (h->obj[j].key < h->obj[i].key) {tmp = h->obj[j];h->obj[j] = h->obj[i];h->obj[i] = tmp;i = j;j <<= 1;} else break;}return output;}const int inf = -1;int leaf[200001];typedef struct {int left, right, max;} seg_node;void init_node(seg_node v[], int k, int l, int r){v[k].left = l;v[k].right = r;v[k].max = inf;if (l < r) {init_node(v, k << 1, l, (l + r) / 2);init_node(v, (k << 1) ^ 1, (l + r) / 2 + 1, r);} else leaf[l] = k;}void update_node(seg_node v[], int k, int x){int i, j = leaf[k];v[j].max = x;for (i = j >> 1; i > 0; j = i, i >>= 1) v[i].max = (v[j].max > v[j^1].max)? v[j].max: v[j^1].max;}int get_max(seg_node v[], int k, int l, int r){int tmp[2];if (v[k].right < l || v[k].left > r) return inf;else if (v[k].left >= l && v[k].right <= r) return v[k].max;else {tmp[0] = get_max(v, k << 1, l, r);tmp[1] = get_max(v, (k << 1) ^ 1, l, r);return (tmp[0] < tmp[1])? tmp[1]: tmp[0];}}int BS_left(seg_node v[], int k, int l, int r, int x){int tmp;if (v[k].max < x || v[k].right < l || v[k].left > r) return r + 1;else if (v[k].left == v[k].right) return v[k].left;else {tmp = BS_left(v, k << 1, l, r, x);if (tmp <= r) return tmp;else return BS_left(v, (k << 1) ^ 1, l, r, x);}}int BS_right(seg_node v[], int k, int l, int r, int x){int tmp;if (v[k].max < x || v[k].right < l || v[k].left > r) return l - 1;else if (v[k].left == v[k].right) return v[k].left;else {tmp = BS_right(v, (k << 1) ^ 1, l, r, x);if (tmp >= l) return tmp;else return BS_right(v, k << 1, l, r, x);}}int solve(int N, int A[], int B[]){int i;static min_heap h;data d;h.size = 0;for (i = 1; i <= N; i++) {d.key = ((long long)B[i] << 20) + i;d.id = i;push(&h, d);}int k, kk, l, r;static seg_node v[2][524288];init_node(v[0], 1, 1, N);init_node(v[1], 1, 1, N);for (i = 1; i <= N; i++) update_node(v[0], i, A[i]);while (h.size > 0) {d = pop(&h);l = d.id;r = d.id;k = B[l];while (h.size > 0 && h.obj[1].id == r + 1 && B[h.obj[1].id] == k) {pop(&h);r++;}kk = get_max(v[0], 1, l, r);if (kk > k) return 0;else if (kk == k) {for (i = l; i <= r; i++) update_node(v[1], i, 0);continue;}if (l > 1) {i = BS_right(v[0], 1, 1, l - 1, k);if (i >= 1 && A[i] == k && get_max(v[1], 1, i, l - 1) == inf) {for (i = l; i <= r; i++) update_node(v[1], i, 0);continue;}}if (r < N) {i = BS_left(v[0], 1, r + 1, N, k);if (i <= N && A[i] == k && get_max(v[1], 1, r + 1, i) == inf) {for (i = l; i <= r; i++) update_node(v[1], i, 0);continue;}}return 0;}return 1;}int main(){int i, t, T, N, A[200001], B[200001];scanf("%d", &T);for (t = 1; t <= T; t++) {scanf("%d", &N);for (i = 1; i <= N; i++) scanf("%d", &(A[i]));for (i = 1; i <= N; i++) scanf("%d", &(B[i]));if (solve(N, A, B) == 0) printf("No\n");else printf("Yes\n");}fflush(stdout);return 0;}