結果

問題 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0