結果
| 問題 | No.1698 Face to Face |
| ユーザー |
👑  ygussany
|
| 提出日時 | 2021-09-30 00:43:19 |
| 言語 | C (gcc 13.3.0) |
| 結果 |
AC
|
| 実行時間 | 500 ms / 5,000 ms |
| コード長 | 13,855 bytes |
| コンパイル時間 | 860 ms |
| コンパイル使用メモリ | 40,960 KB |
| 実行使用メモリ | 40,448 KB |
| 最終ジャッジ日時 | 2024-07-19 10:18:52 |
| 合計ジャッジ時間 | 11,503 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 45 |
ソースコード
#include <stdio.h>#include <stdlib.h>typedef struct {int key, id;} data;typedef struct {data *obj;int size, max_size;} min_max_heap;int get_min(min_max_heap* h){return h->obj[0].key;}int get_argmin(min_max_heap* h){return h->obj[0].id;}int get_max(min_max_heap* h){if (h->size == 1) return h->obj[0].key;else return h->obj[1].key;}int get_argmax(min_max_heap* h){if (h->size == 1) return h->obj[0].id;else return h->obj[1].id;}void push(min_max_heap* h, data x){int i = (h->size)++;data tmp;if ((i & 1) != 0 && x.key < h->obj[i^1].key) {h->obj[i] = h->obj[i^1];h->obj[i^1] = x;i ^= 1;} else h->obj[i] = x;int j, k = ((i >> 1) + 1) >> 1;if (k == 0) return;j = (k - 1) << 1;if (h->obj[i].key < h->obj[j].key) {while (k > 0) {if (h->obj[i].key < h->obj[j].key) {tmp = h->obj[j];h->obj[j] = h->obj[i];h->obj[i] = tmp;k >>= 1;i = j;j = (k - 1) << 1;} else break;}} else if (h->obj[i].key > h->obj[j^1].key) {j ^= 1;while (k > 0) {if (h->obj[i].key > h->obj[j].key) {tmp = h->obj[j];h->obj[j] = h->obj[i];h->obj[i] = tmp;k >>= 1;i = j;j = ((k - 1) << 1) ^ 1;} else break;}}}data pop_min(min_max_heap* h){int i = 0, j = 2, k = 2;data output = h->obj[0], tmp;h->obj[0] = h->obj[--(h->size)];while (j < h->size) {if (j + 2 < h->size && h->obj[j+2].key < h->obj[j].key) {j += 2;k++;}if (h->obj[i].key > h->obj[j].key) {tmp = h->obj[j];h->obj[j] = h->obj[i];h->obj[i] = tmp;k <<= 1;i = j;j = (k - 1) << 1;} else break;}if (j < h->size) return output;if (i < h->size - 1 && h->obj[i].key > h->obj[i^1].key) {tmp = h->obj[i^1];h->obj[i^1] = h->obj[i];h->obj[i] = tmp;i ^= 1;}k = ((i >> 1) + 1) >> 1;j = ((k - 1) << 1) ^ 1;while (k > 0) {if (h->obj[i].key > h->obj[j].key) {tmp = h->obj[j];h->obj[j] = h->obj[i];h->obj[i] = tmp;k >>= 1;i = j;j = ((k - 1) << 1) ^ 1;} else break;}return output;}data pop_max(min_max_heap* h){if (h->size == 1) return h->obj[--(h->size)];int i = 1, j = 2, k = 2;data output = h->obj[1], tmp;h->obj[1] = h->obj[--(h->size)];while (j < h->size) {if (j + 1 < h->size) {j++;if (j + 2 < h->size && h->obj[j+2].key > h->obj[j].key) {j += 2;k++;} else if (j + 1 < h->size && h->obj[j+1].key > h->obj[j].key) {j++;k++;}}if (h->obj[i].key < h->obj[j].key) {tmp = h->obj[j];h->obj[j] = h->obj[i];h->obj[i] = tmp;k <<= 1;i = j;j = (k - 1) << 1;} else break;}if (j < h->size) return output;i = (i >> 1) << 1;if (i < h->size - 1 && h->obj[i].key > h->obj[i^1].key) {tmp = h->obj[i^1];h->obj[i^1] = h->obj[i];h->obj[i] = tmp;}k = ((i >> 1) + 1) >> 1;j = (k - 1) << 1;while (k > 0) {if (h->obj[i].key < h->obj[j].key) {tmp = h->obj[j];h->obj[j] = h->obj[i];h->obj[i] = tmp;k >>= 1;i = j;j = (k - 1) << 1;} else break;}return output;}const int sup = 1 << 20;typedef struct {int left, right, flag, sum, len;} seg_node;void init_node(seg_node v[], int leaf[], int k, int l, int r){v[k].left = l;v[k].right = r;v[k].flag = 1;v[k].sum = 0;if (l < r) {v[k].len = sup;init_node(v, leaf, k << 1, l, (l + r) / 2);init_node(v, leaf, (k << 1) ^ 1, (l + r) / 2 + 1, r);} else {v[k].len = 1;leaf[l] = k;}}void update_flag(seg_node v[], int leaf[], int k, int x){int i, j = leaf[k];v[j].flag = x;for (i = j >> 1; i > 0; j = i, i >>= 1) v[i].flag = (v[j].flag > v[j^1].flag)? v[j].flag: v[j^1].flag;}void update_sum(seg_node v[], int leaf[], int k, int x){int i, j = leaf[k];v[j].sum += x;for (i = j >> 1; i > 0; j = i, i >>= 1) v[i].sum = ((v[j].sum <= v[j].len)? v[j].sum: v[j].len) + ((v[j^1].sum <= v[j^1].len)? v[j^1].sum: v[j^1].len);}int get_flag(seg_node v[], int leaf[], int k){return v[leaf[k]].flag;}int get_sum(seg_node v[], int k, int l, int r){if (v[k].right < l || v[k].left > r) return 0;else if (v[k].left >= l && v[k].right <= r) return v[k].sum;else return get_sum(v, k << 1, l, r) + get_sum(v, (k << 1) ^ 1, l, r);}int BS_left(seg_node v[], int k, int l, int r){int tmp;if (v[k].flag == 0 || 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);if (tmp <= r) return tmp;else return BS_left(v, (k << 1) ^ 1, l, r);}}int BS_right(seg_node v[], int k, int l, int r){int tmp;if (v[k].flag == 0 || 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);if (tmp >= l) return tmp;else return BS_right(v, k << 1, l, r);}}void chmin(int* a, int b){if (*a > b) *a = b;}int main(){int i, N, A[100001], B[100001], Z[100001];scanf("%d", &N);for (i = 1; i <= N; i++) scanf("%d", &(A[i]));for (i = 1; i <= N; i++) scanf("%d", &(B[i]));for (i = 1; i <= N; i++) scanf("%d", &(Z[i]));int A_inv[100001], B_inv[100001], Z_inv[100001];for (i = 1; i <= N; i++) {A_inv[A[i]] = i;B_inv[B[i]] = i;Z_inv[Z[i]] = i;}char meet[2][100001] = {};data d;min_max_heap h[2][2][100001];int j, k, leaf[3][100001];seg_node v[3][262144];for (i = 0; i < 3; i++) init_node(v[i], leaf[i], 1, 1, N);for (i = 1; i <= N; i++) {for (j = 0; j < 2; j++) {for (k = 0; k < 2; k++) {h[j][k][i].obj = (data*)malloc(sizeof(data) * 2);h[j][k][i].size = 0;h[j][k][i].max_size = 2;}}}for (i = 1; i <= N; i++) {if (Z[A[i]] == B[i]) {meet[0][i] = 1;meet[1][i] = 1;update_sum(v[2], leaf[2], i, 1);} else if (B_inv[Z[A[i]]] > i) {d.key = B_inv[Z[A[i]]];d.id = i;push(&(h[0][1][i]), d);d.key = i;d.id = B_inv[Z[A[i]]];push(&(h[1][0][B_inv[Z[A[i]]]]), d);} else {d.key = B_inv[Z[A[i]]];d.id = i;push(&(h[0][0][i]), d);d.key = i;d.id = B_inv[Z[A[i]]];push(&(h[1][1][B_inv[Z[A[i]]]]), d);}}printf("%d\n", get_sum(v[2], 1, 1, N));int l, tmp;for (k = 2; k < N; k++) {i = A_inv[k];if (i < N && A[i+1] < k) {update_flag(v[0], leaf[0], i + 1, 0);if (get_flag(v[1], leaf[1], i + 1) == 0) {update_flag(v[2], leaf[2], i + 1, 0);v[2][leaf[2][i]].len += v[2][leaf[2][i+1]].len;v[2][leaf[2][i+1]].len = 0;update_sum(v[2], leaf[2], i, v[2][leaf[2][i+1]].sum);update_sum(v[2], leaf[2], i + 1, -v[2][leaf[2][i+1]].sum);}for (j = 0; j < 2; j++) {if (h[0][j][i].size >= h[0][j][i+1].size) {while (h[0][j][i+1].size > 0) {d = pop_min(&(h[0][j][i+1]));push(&(h[0][j][i]), d);if (h[0][j][i].size == h[0][j][i].max_size) {h[0][j][i].max_size *= 2;h[0][j][i].obj = (data*)realloc(h[0][j][i].obj, sizeof(data) * h[0][j][i].max_size);}}free(h[0][j][i+1].obj);} else {while (h[0][j][i].size > 0) {d = pop_min(&(h[0][j][i]));push(&(h[0][j][i+1]), d);if (h[0][j][i+1].size == h[0][j][i+1].max_size) {h[0][j][i+1].max_size *= 2;h[0][j][i+1].obj = (data*)realloc(h[0][j][i+1].obj, sizeof(data) * h[0][j][i+1].max_size);}}free(h[0][j][i].obj);h[0][j][i] = h[0][j][i+1];}}tmp = BS_right(v[1], 1, 1, i);while (h[0][0][i].size > 0 && (get_max(&(h[0][0][i])) >= tmp || meet[0][get_argmax(&(h[0][0][i]))] != 0)) {d = pop_max(&(h[0][0][i]));if (meet[0][d.id] != 0) continue;meet[0][d.id] = 1;meet[1][d.key] = 1;update_sum(v[2], leaf[2], i, 1);}tmp = BS_left(v[1], 1, BS_left(v[0], 1, i + 1, N), N) - 1;while (h[0][1][i].size > 0 && (get_min(&(h[0][1][i])) <= tmp || meet[0][get_argmin(&(h[0][1][i]))] != 0)) {d = pop_min(&(h[0][1][i]));if (meet[0][d.id] != 0) continue;meet[0][d.id] = 1;meet[1][d.key] = 1;update_sum(v[2], leaf[2], BS_right(v[1], 1, 1, d.key), 1);}}if (i > 1 && A[i-1] < k) {update_flag(v[0], leaf[0], i, 0);if (get_flag(v[1], leaf[1], i) == 0) {update_flag(v[2], leaf[2], i, 0);l = BS_right(v[2], 1, 1, i);v[2][leaf[2][l]].len += v[2][leaf[2][i]].len;v[2][leaf[2][i]].len = 0;update_sum(v[2], leaf[2], l, v[2][leaf[2][i]].sum);update_sum(v[2], leaf[2], i, -v[2][leaf[2][i]].sum);}l = BS_right(v[0], 1, 1, i);for (j = 0; j < 2; j++) {if (h[0][j][l].size >= h[0][j][i].size) {while (h[0][j][i].size > 0) {d = pop_min(&(h[0][j][i]));push(&(h[0][j][l]), d);if (h[0][j][l].size == h[0][j][l].max_size) {h[0][j][l].max_size *= 2;h[0][j][l].obj = (data*)realloc(h[0][j][l].obj, sizeof(data) * h[0][j][l].max_size);}}free(h[0][j][i].obj);} else {while (h[0][j][l].size > 0) {d = pop_min(&(h[0][j][l]));push(&(h[0][j][i]), d);if (h[0][j][i].size == h[0][j][i].max_size) {h[0][j][i].max_size *= 2;h[0][j][i].obj = (data*)realloc(h[0][j][i].obj, sizeof(data) * h[0][j][i].max_size);}}free(h[0][j][l].obj);h[0][j][l] = h[0][j][i];}}tmp = BS_right(v[1], 1, 1, l);while (h[0][0][l].size > 0 && (get_max(&(h[0][0][l])) >= tmp || meet[0][get_argmax(&(h[0][0][l]))] != 0)) {d = pop_max(&(h[0][0][l]));if (meet[0][d.id] != 0) continue;meet[0][d.id] = 1;meet[1][d.key] = 1;if (d.key < l) update_sum(v[2], leaf[2], l, 1);else update_sum(v[2], leaf[2], BS_right(v[2], 1, 1, d.key), 1);}tmp = BS_left(v[1], 1, BS_left(v[0], 1, l + 1, N), N) - 1;while (h[0][1][l].size > 0 && (get_min(&(h[0][1][l])) <= tmp || meet[0][get_argmin(&(h[0][1][l]))] != 0)) {d = pop_min(&(h[0][1][l]));if (meet[0][d.id] != 0) continue;meet[0][d.id] = 1;meet[1][d.key] = 1;update_sum(v[2], leaf[2], BS_right(v[1], 1, 1, d.key), 1);}}i = B_inv[k];if (i < N && B[i+1] < k) {update_flag(v[1], leaf[1], i + 1, 0);if (get_flag(v[0], leaf[0], i + 1) == 0) {update_flag(v[2], leaf[2], i + 1, 0);v[2][leaf[2][i]].len += v[2][leaf[2][i+1]].len;v[2][leaf[2][i+1]].len = 0;update_sum(v[2], leaf[2], i, v[2][leaf[2][i+1]].sum);update_sum(v[2], leaf[2], i + 1, -v[2][leaf[2][i+1]].sum);}for (j = 0; j < 2; j++) {if (h[1][j][i].size >= h[1][j][i+1].size) {while (h[1][j][i+1].size > 0) {d = pop_min(&(h[1][j][i+1]));push(&(h[1][j][i]), d);if (h[1][j][i].size == h[1][j][i].max_size) {h[1][j][i].max_size *= 2;h[1][j][i].obj = (data*)realloc(h[1][j][i].obj, sizeof(data) * h[1][j][i].max_size);}}free(h[1][j][i+1].obj);} else {while (h[1][j][i].size > 0) {d = pop_min(&(h[1][j][i]));push(&(h[1][j][i+1]), d);if (h[1][j][i+1].size == h[1][j][i+1].max_size) {h[1][j][i+1].max_size *= 2;h[1][j][i+1].obj = (data*)realloc(h[1][j][i+1].obj, sizeof(data) * h[1][j][i+1].max_size);}}free(h[1][j][i].obj);h[1][j][i] = h[1][j][i+1];}}tmp = BS_right(v[0], 1, 1, i);while (h[1][0][i].size > 0 && (get_max(&(h[1][0][i])) >= tmp || meet[1][get_argmax(&(h[1][0][i]))] != 0)) {d = pop_max(&(h[1][0][i]));if (meet[1][d.id] != 0) continue;meet[1][d.id] = 1;meet[0][d.key] = 1;update_sum(v[2], leaf[2], i, 1);}tmp = BS_left(v[0], 1, BS_left(v[1], 1, i + 1, N), N) - 1;while (h[1][1][i].size > 0 && (get_min(&(h[1][1][i])) <= tmp || meet[1][get_argmin(&(h[1][1][i]))] != 0)) {d = pop_min(&(h[1][1][i]));if (meet[1][d.id] != 0) continue;meet[1][d.id] = 1;meet[0][d.key] = 1;update_sum(v[2], leaf[2], BS_right(v[0], 1, 1, d.key), 1);}}if (i > 1 && B[i-1] < k) {update_flag(v[1], leaf[1], i, 0);if (get_flag(v[0], leaf[0], i) == 0) {update_flag(v[2], leaf[2], i, 0);l = BS_right(v[2], 1, 1, i);v[2][leaf[2][l]].len += v[2][leaf[2][i]].len;v[2][leaf[2][i]].len = 0;update_sum(v[2], leaf[2], l, v[2][leaf[2][i]].sum);update_sum(v[2], leaf[2], i, -v[2][leaf[2][i]].sum);}l = BS_right(v[1], 1, 1, i);for (j = 0; j < 2; j++) {if (h[1][j][l].size >= h[1][j][i].size) {while (h[1][j][i].size > 0) {d = pop_min(&(h[1][j][i]));push(&(h[1][j][l]), d);if (h[1][j][l].size == h[1][j][l].max_size) {h[1][j][l].max_size *= 2;h[1][j][l].obj = (data*)realloc(h[1][j][l].obj, sizeof(data) * h[1][j][l].max_size);}}free(h[1][j][i].obj);} else {while (h[1][j][l].size > 0) {d = pop_min(&(h[1][j][l]));push(&(h[1][j][i]), d);if (h[1][j][i].size == h[1][j][i].max_size) {h[1][j][i].max_size *= 2;h[1][j][i].obj = (data*)realloc(h[1][j][i].obj, sizeof(data) * h[1][j][i].max_size);}}free(h[1][j][l].obj);h[1][j][l] = h[1][j][i];}}tmp = BS_right(v[0], 1, 1, l);while (h[1][0][l].size > 0 && (get_max(&(h[1][0][l])) >= tmp || meet[1][get_argmax(&(h[1][0][l]))] != 0)) {d = pop_max(&(h[1][0][l]));if (meet[1][d.id] != 0) continue;meet[1][d.id] = 1;meet[0][d.key] = 1;if (d.key < l) update_sum(v[2], leaf[2], l, 1);else update_sum(v[2], leaf[2], BS_right(v[2], 1, 1, d.key), 1);}tmp = BS_left(v[0], 1, BS_left(v[1], 1, l + 1, N), N) - 1;while (h[1][1][l].size > 0 && (get_min(&(h[1][1][l])) <= tmp || meet[1][get_argmin(&(h[1][1][l]))] != 0)) {d = pop_min(&(h[1][1][l]));if (meet[1][d.id] != 0) continue;meet[1][d.id] = 1;meet[0][d.key] = 1;update_sum(v[2], leaf[2], BS_right(v[0], 1, 1, d.key), 1);}}printf("%d\n", get_sum(v[2], 1, 1, N));}printf("%d\n", N);fflush(stdout);return 0;}