結果

問題 No.1888 Odd Insertion
ユーザー 👑 ygussanyygussany
提出日時 2022-03-10 19:22:12
言語 C
(gcc 12.3.0)
結果
AC  
実行時間 350 ms / 2,000 ms
コード長 3,035 bytes
コンパイル時間 757 ms
コンパイル使用メモリ 32,856 KB
実行使用メモリ 16,824 KB
最終ジャッジ日時 2023-10-12 21:59:09
合計ジャッジ時間 17,363 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,876 KB
testcase_01 AC 2 ms
5,884 KB
testcase_02 AC 2 ms
5,892 KB
testcase_03 AC 2 ms
6,068 KB
testcase_04 AC 2 ms
6,252 KB
testcase_05 AC 2 ms
5,936 KB
testcase_06 AC 244 ms
16,752 KB
testcase_07 AC 240 ms
16,752 KB
testcase_08 AC 347 ms
16,708 KB
testcase_09 AC 333 ms
16,656 KB
testcase_10 AC 348 ms
16,760 KB
testcase_11 AC 335 ms
16,820 KB
testcase_12 AC 345 ms
16,820 KB
testcase_13 AC 350 ms
16,820 KB
testcase_14 AC 336 ms
16,760 KB
testcase_15 AC 338 ms
16,756 KB
testcase_16 AC 305 ms
16,752 KB
testcase_17 AC 348 ms
16,756 KB
testcase_18 AC 310 ms
16,760 KB
testcase_19 AC 297 ms
16,744 KB
testcase_20 AC 310 ms
16,644 KB
testcase_21 AC 296 ms
16,620 KB
testcase_22 AC 304 ms
16,640 KB
testcase_23 AC 313 ms
16,692 KB
testcase_24 AC 316 ms
16,628 KB
testcase_25 AC 318 ms
16,688 KB
testcase_26 AC 242 ms
16,756 KB
testcase_27 AC 219 ms
16,824 KB
testcase_28 AC 256 ms
16,760 KB
testcase_29 AC 192 ms
16,696 KB
testcase_30 AC 198 ms
16,636 KB
testcase_31 AC 188 ms
16,756 KB
testcase_32 AC 249 ms
16,820 KB
testcase_33 AC 258 ms
16,688 KB
testcase_34 AC 257 ms
16,696 KB
testcase_35 AC 242 ms
16,752 KB
testcase_36 AC 240 ms
16,760 KB
testcase_37 AC 259 ms
16,768 KB
testcase_38 AC 236 ms
16,820 KB
権限があれば一括ダウンロードができます

ソースコード

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