#744602 (C) No.1888 Odd Insertion

• 問題: No.1888 Odd Insertion
• ユーザー: ygussany
• 提出日時: 2022-03-10 19:22:12
• 言語: C (gcc 12.3.0)
• 結果: AC
• 実行時間: 363 ms / 2,000 ms
• コード長: 3,035 bytes
• コンパイル時間: 484 ms
• コンパイル使用メモリ: 33,664 KB
• 実行使用メモリ: 16,768 KB
• 最終ジャッジ日時: 2024-09-14 20:13:45
• 合計ジャッジ時間: 17,448 ms
• ジャッジサーバーID （参考情報）: judge4 / judge3

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	2 ms; 5,248 KB
testcase_01	AC	2 ms; 5,376 KB
testcase_02	AC	2 ms; 5,376 KB
testcase_03	AC	2 ms; 5,376 KB
testcase_04	AC	2 ms; 5,376 KB
testcase_05	AC	2 ms; 5,376 KB
testcase_06	AC	248 ms; 15,232 KB
testcase_07	AC	245 ms; 14,976 KB
testcase_08	AC	358 ms; 16,768 KB
testcase_09	AC	343 ms; 16,640 KB
testcase_10	AC	358 ms; 16,640 KB
testcase_11	AC	349 ms; 16,640 KB
testcase_12	AC	363 ms; 16,640 KB
testcase_13	AC	358 ms; 16,768 KB
testcase_14	AC	347 ms; 16,640 KB
testcase_15	AC	350 ms; 16,640 KB
testcase_16	AC	325 ms; 15,232 KB
testcase_17	AC	359 ms; 16,640 KB
testcase_18	AC	321 ms; 14,976 KB
testcase_19	AC	304 ms; 14,976 KB
testcase_20	AC	319 ms; 15,104 KB
testcase_21	AC	310 ms; 15,104 KB
testcase_22	AC	322 ms; 15,104 KB
testcase_23	AC	326 ms; 15,104 KB
testcase_24	AC	323 ms; 15,104 KB
testcase_25	AC	329 ms; 14,976 KB
testcase_26	AC	251 ms; 16,768 KB
testcase_27	AC	226 ms; 16,640 KB
testcase_28	AC	263 ms; 16,768 KB
testcase_29	AC	199 ms; 15,104 KB
testcase_30	AC	202 ms; 14,976 KB
testcase_31	AC	193 ms; 15,232 KB
testcase_32	AC	256 ms; 16,640 KB
testcase_33	AC	263 ms; 16,768 KB
testcase_34	AC	263 ms; 16,640 KB
testcase_35	AC	250 ms; 16,768 KB
testcase_36	AC	249 ms; 16,768 KB
testcase_37	AC	265 ms; 16,640 KB
testcase_38	AC	244 ms; 16,640 KB

ソースコード

#include <stdio.h>

void add_BIT(int N, int BIT[], int i, int k)
{
	while (i <= N) {
		BIT[i] += k;
		i += (i & -i);
	}
}

int sum_BIT(int BIT[], int r)
{
	int sum = 0;
	while (r > 0) {
		sum += BIT[r];
		r -= (r & -r);
	}
	return sum;
}

typedef struct {
	int left, right, max, la, lb;
} lazy_seg_node;

void init_node(lazy_seg_node v[], int k, int l, int r)
{
	v[k].left = l;
	v[k].right = r;
	v[k].max = 0;
	v[k].la = 3;
	v[k].lb = 0;
	if (l < r) {
		init_node(v, k << 1, l, (l + r) / 2);
		init_node(v, (k << 1) ^ 1, (l + r) / 2 + 1, r); 
	}
}

void update_max_to_root(lazy_seg_node v[], int k)
{
	int j;
	for (j = k >> 1; j > 0; k = j, j >>= 1) v[j].max = (v[k].max > v[k^1].max)? v[k].max: v[k^1].max;
}

void push_update_below(lazy_seg_node v[], int k)
{
	int j;
	if (v[k].left == v[k].right || (v[k].la == 3 && v[k].lb == 0)) return;
	j = k << 1;
	v[j].max = v[j].max & v[k].la ^ v[k].lb;
	v[j].la &= v[k].la;
	v[j].lb = v[j].lb & v[k].la ^ v[k].lb;
	j ^= 1;
	v[j].max = v[j].max & v[k].la ^ v[k].lb;
	v[j].la &= v[k].la;
	v[j].lb = v[j].lb & v[k].la ^ v[k].lb;
	v[k].la = 3;
	v[k].lb = 0;
}

void update_segment(lazy_seg_node v[], int k, int l, int r, int a, int b)
{
	if (r < v[k].left || v[k].right < l) return;
	else if (l <= v[k].left && v[k].right <= r) {
		v[k].max = v[k].max & a ^ b;
		v[k].la &= a;
		v[k].lb = v[k].lb & a ^ b;
		update_max_to_root(v, k);
	} else {
		push_update_below(v, k);
		update_segment(v, k << 1, l, r, a, b);
		update_segment(v, (k << 1) ^ 1, l, r, a, b);
	}
}

int BS_left(lazy_seg_node v[], int k, int l, int r, int x)
{
	int tmp;
	if (v[k].max < x || r < v[k].left || v[k].right < l) return r + 1;
	else if (v[k].left == v[k].right) return v[k].left;
	else {
		push_update_below(v, k);
		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 main()
{
	int i, N, P[200001], P_inv[200001];
	scanf("%d", &N);
	for (i = 1; i <= N; i++) scanf("%d", &(P[i]));
	for (i = 1; i <= N; i++) P_inv[P[i]] = i;
	
	int j, k, l, BIT[200001] = {}, start[200001] = {};
	lazy_seg_node v[524288];
	init_node(v, 1, 1, N);
	for (i = 1; i <= N; i++) {
		j = P_inv[i];
		k = sum_BIT(BIT, j - 1);
		add_BIT(N, BIT, j, 1);
		update_segment(v, 1, j, N, 3, 1);
		if (k % 2 == 0) {
			if (i == 1 || start[i-1] > 0) start[i] = i;
			update_segment(v, 1, 1, j - 1, 1, 0);
		} else update_segment(v, 1, j + 1, N, 1, 0);
		if (start[i] == 0) {
			l = BS_left(v, 1, 1, N, 3);
			if (l <= N) start[i] = P[l];
		}
		if (i == 1 || start[i-1] > 0) update_segment(v, 1, j, j, 3, 2);
	}
	if (start[N] == 0) {
		printf("No\n");
		fflush(stdout);
		return 0;
	}
	
	int ans[200001][2];
	for (i = N, k = N; i >= 1; i--) {
		j = start[i];
		ans[k][0] = j;
		ans[k--][1] = sum_BIT(BIT, P_inv[j]);
		add_BIT(N, BIT, P_inv[j], -1);
		for (; i > j; i--) {
			ans[k][0] = i;
			ans[k--][1] = sum_BIT(BIT, P_inv[i]);
			add_BIT(N, BIT, P_inv[i], -1);
		}
	}
	printf("Yes\n");
	for (i = 1; i <= N; i++) printf("%d %d\n", ans[i][0], ans[i][1]);
	fflush(stdout);
	return 0;
}