結果

問題 No.1675 Strange Minimum Query
ユーザー 👑 ygussanyygussany
提出日時 2021-09-10 22:03:02
言語 C
(gcc 12.3.0)
結果
AC  
実行時間 284 ms / 2,000 ms
コード長 2,462 bytes
コンパイル時間 1,588 ms
コンパイル使用メモリ 31,892 KB
実行使用メモリ 21,924 KB
最終ジャッジ日時 2023-09-02 17:41:50
合計ジャッジ時間 9,950 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
7,948 KB
testcase_01 AC 2 ms
7,944 KB
testcase_02 AC 2 ms
8,116 KB
testcase_03 AC 98 ms
16,720 KB
testcase_04 AC 79 ms
17,488 KB
testcase_05 AC 10 ms
12,600 KB
testcase_06 AC 116 ms
16,008 KB
testcase_07 AC 113 ms
19,484 KB
testcase_08 AC 2 ms
10,044 KB
testcase_09 AC 3 ms
8,024 KB
testcase_10 AC 82 ms
15,308 KB
testcase_11 AC 21 ms
12,656 KB
testcase_12 AC 93 ms
14,988 KB
testcase_13 AC 84 ms
21,924 KB
testcase_14 AC 146 ms
19,272 KB
testcase_15 AC 146 ms
19,076 KB
testcase_16 AC 2 ms
8,112 KB
testcase_17 AC 34 ms
10,660 KB
testcase_18 AC 50 ms
12,480 KB
testcase_19 AC 68 ms
15,380 KB
testcase_20 AC 174 ms
17,804 KB
testcase_21 AC 148 ms
16,008 KB
testcase_22 AC 209 ms
17,044 KB
testcase_23 AC 157 ms
14,740 KB
testcase_24 AC 141 ms
15,244 KB
testcase_25 AC 96 ms
14,516 KB
testcase_26 AC 45 ms
12,792 KB
testcase_27 AC 130 ms
17,300 KB
testcase_28 AC 63 ms
14,944 KB
testcase_29 AC 41 ms
14,972 KB
testcase_30 AC 44 ms
12,920 KB
testcase_31 AC 202 ms
19,916 KB
testcase_32 AC 284 ms
20,140 KB
testcase_33 AC 282 ms
19,564 KB
testcase_34 AC 275 ms
20,460 KB
testcase_35 AC 276 ms
17,304 KB
testcase_36 AC 278 ms
17,772 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <stdio.h>

typedef struct {
	long long key;
	int id;
} data;

typedef struct {
	data obj[1000001];
	int size;
} max_heap;

void push(max_heap* h, data x)
{
	int i = ++(h->size), j = i >> 1;
	data tmp;
	h->obj[i] = x;
	while (j > 0) {
		if (h->obj[i].key > h->obj[j].key) {
			tmp = h->obj[j];
			h->obj[j] = h->obj[i];
			h->obj[i] = tmp;
			i = j;
			j >>= 1;
		} else break;
	}
}

data pop(max_heap* h)
{
	int i = 1, j = 2;
	data output = h->obj[1], tmp;
	h->obj[1] = h->obj[(h->size)--];
	while (j <= h->size) {
		if (j < h->size && h->obj[j^1].key > h->obj[j].key) j ^= 1;
		if (h->obj[j].key > h->obj[i].key) {
			tmp = h->obj[j];
			h->obj[j] = h->obj[i];
			h->obj[i] = tmp;
			i = j;
			j <<= 1;
		} else break;
	}
	return output;
}

const int sup = 1 << 30;
int leaf[200001];

typedef struct {
	int left, right, min;
} seg_node;

void init_node(seg_node v[], int k, int l, int r)
{
	v[k].left = l;
	v[k].right = r;
	v[k].min = sup;
	if (l < r) {
		init_node(v, k << 1, l, (l + r) / 2);
		init_node(v, (k << 1) ^ 1, (l + r) / 2 + 1, r);
	} else leaf[l] = k;
}
 
int get_min(seg_node v[], int k, int l, int r)
{
	int tmp[2];
	if (v[k].right < l || v[k].left > r) return sup;
	else if (v[k].left >= l && v[k].right <= r) return v[k].min;
	else {
		tmp[0] = get_min(v, k << 1, l, r);
		tmp[1] = get_min(v, (k << 1) ^ 1, l, r);
		return (tmp[0] < tmp[1])? tmp[0]: tmp[1];
	}
}


int main()
{
	int i, N, Q, l[200001], r[200001], B[200001];
	scanf("%d %d", &N, &Q);
	for (i = 1; i <= Q; i++) scanf("%d %d %d", &(l[i]), &(r[i]), &(B[i]));

	int j, k, A[200001];
	max_heap h[2];
	data d;
	h[0].size = 0;
	h[1].size = 0;
	for (i = 1; i <= Q; i++) {
		d.key = r[i];
		d.id = i;
		push(&(h[0]), d);
	}
	d.key = 1;
	d.id = 0;
	push(&(h[1]), d);
	l[0] = 1;
	for (k = N; k >= 1; k--) {
		while (h[0].size > 0 && h[0].obj[1].key == k) {
			d = pop(&(h[0]));
			i = d.id;
			d.key = B[i];
			d.id = i;
			push(&(h[1]), d);
		}
		while (l[h[1].obj[1].id] > k) pop(&(h[1]));
		A[k] = h[1].obj[1].key;
	}

	seg_node v[524288];
	init_node(v, 1, 1, N);
	for (i = 1; i <= N; i++) v[leaf[i]].min = A[i];
	for (i = leaf[N]; i >= 1; i--) {
		if (v[i].left == v[i].right) continue;
		j = i << 1;
		v[i].min = (v[j].min < v[j^1].min)? v[j].min: v[j^1].min;
	}
	for (i = 1; i <= Q; i++) if (get_min(v, 1, l[i], r[i]) != B[i]) break;
	if (i <= Q) printf("-1\n");
	else {
		for (i = 1; i < N; i++) printf("%d ", A[i]);
		printf("%d\n", A[N]);
	}
	fflush(stdout);
	return 0;
}
0