結果

問題 No.1888 Odd Insertion
コンテスト
ユーザー 👑 ygussany
提出日時 2022-03-10 18:48:39
言語 C
(gcc 13.3.0)
結果
TLE  
実行時間 -
コード長 3,868 bytes
コンパイル時間 1,530 ms
コンパイル使用メモリ 33,536 KB
実行使用メモリ 21,564 KB
最終ジャッジ日時 2024-09-14 19:56:13
合計ジャッジ時間 17,738 ms
ジャッジサーバーID
（参考情報） 		judge6 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 31 TLE * 1 -- * 5
権限があれば一括ダウンロードができます

ソースコード

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, 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].lb = -1;
	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].lb < 0) return;
	j = k << 1;
	v[j].max = v[k].lb;
	v[j].lb = v[k].lb;
	j ^= 1;
	v[j].max = v[k].lb;
	v[j].lb = v[k].lb;
	v[k].lb = -1;
}

void update_segment(lazy_seg_node v[], int k, int l, int r, 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 = b;
		v[k].lb = b;
		update_max_to_root(v, k);
	} else {
		push_update_below(v, k);
		update_segment(v, k << 1, l, r, b);
		update_segment(v, (k << 1) ^ 1, l, r, b);
	}
}

int get_max(lazy_seg_node v[], int k, int l, int r)
{
	int tmp[2];
	if (r < v[k].left || v[k].right < l) return -1;
	else if (l <= v[k].left && v[k].right <= r) return v[k].max;
	else {
		push_update_below(v, k);
		tmp[0] = get_max(v, k << 1, l, r);
		tmp[1] = get_max(v, (k << 1) ^ 1, l, r);
		return (tmp[0] > tmp[1])? tmp[0]: tmp[1];
	}
}

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 BS_right(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 l - 1;
	else if (v[k].left == v[k].right) return v[k].left;
	else {
		push_update_below(v, k);
		tmp = BS_right(v, (k << 1) ^ 1, l, r, x);
		if (tmp >= l) return tmp;
		else return BS_right(v, k << 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);
		if (k % 2 == 0) {
			if (i == 1 || start[i-1] > 0) start[i] = i;
			update_segment(v, 1, 1, j - 1, 0);
			if (start[i] == 0) {
				for (l = BS_left(v, 1, j + 1, N, 1); l <= N; l = BS_left(v, 1, l + 1, N, 1)) if (sum_BIT(BIT, l - 1) % 2 == 0) break;
				if (l <= N) start[i] = P[l];
			}
		} else {
			update_segment(v, 1, j + 1, N, 0);
			for (l = BS_right(v, 1, 1, j - 1, 1); l >= 1; l = BS_right(v, 1, 1, l - 1, 1)) if (sum_BIT(BIT, l - 1) % 2 == 0) break;
			if (l >= 1) start[i] = P[l];
		}
		if (i == 1 || start[i-1] > 0) update_segment(v, 1, j, j, 1);
	}
	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