#703523 (C) No.1698 Face to Face

提出ソース

結果

問題	No.1698 Face to Face
ユーザー	ygussany
提出日時	2021-09-30 00:43:19
言語	C (gcc 12.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

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	1 ms 5,248 KB
testcase_01	AC	1 ms 5,376 KB
testcase_02	AC	1 ms 5,376 KB
testcase_03	AC	138 ms 39,040 KB
testcase_04	AC	220 ms 39,936 KB
testcase_05	AC	312 ms 39,168 KB
testcase_06	AC	297 ms 39,168 KB
testcase_07	AC	236 ms 39,124 KB
testcase_08	AC	246 ms 39,040 KB
testcase_09	AC	258 ms 39,040 KB
testcase_10	AC	210 ms 39,168 KB
testcase_11	AC	308 ms 39,628 KB
testcase_12	AC	384 ms 39,636 KB
testcase_13	AC	2 ms 5,376 KB
testcase_14	AC	1 ms 5,376 KB
testcase_15	AC	495 ms 39,884 KB
testcase_16	AC	491 ms 39,764 KB
testcase_17	AC	481 ms 39,808 KB
testcase_18	AC	418 ms 36,992 KB
testcase_19	AC	420 ms 37,248 KB
testcase_20	AC	393 ms 36,096 KB
testcase_21	AC	179 ms 19,968 KB
testcase_22	AC	134 ms 17,664 KB
testcase_23	AC	27 ms 6,016 KB
testcase_24	AC	212 ms 21,376 KB
testcase_25	AC	500 ms 38,272 KB
testcase_26	AC	15 ms 5,376 KB
testcase_27	AC	82 ms 11,392 KB
testcase_28	AC	92 ms 11,776 KB
testcase_29	AC	63 ms 10,112 KB
testcase_30	AC	240 ms 22,912 KB
testcase_31	AC	174 ms 20,096 KB
testcase_32	AC	321 ms 33,664 KB
testcase_33	AC	316 ms 33,664 KB
testcase_34	AC	448 ms 38,784 KB
testcase_35	AC	1 ms 5,376 KB
testcase_36	AC	1 ms 5,376 KB
testcase_37	AC	1 ms 5,376 KB
testcase_38	AC	1 ms 5,376 KB
testcase_39	AC	1 ms 5,376 KB
testcase_40	AC	1 ms 5,376 KB
testcase_41	AC	1 ms 5,376 KB
testcase_42	AC	1 ms 5,376 KB
testcase_43	AC	1 ms 5,376 KB
testcase_44	AC	1 ms 5,376 KB
testcase_45	AC	280 ms 39,808 KB
testcase_46	AC	283 ms 40,448 KB
testcase_47	AC	326 ms 39,248 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#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;
}

yukicoder

結果

テストケース

ソースコード