結果

問題 No.1888 Odd Insertion
コンテスト
ユーザー 👑 ygussany
提出日時 2022-03-10 19:22:12
言語 C
(gcc 13.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
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 37
権限があれば一括ダウンロードができます

ソースコード

diff # 

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