結果

問題 No.1675 Strange Minimum Query
コンテスト
ユーザー 👑 ygussany
提出日時 2021-09-10 22:03:02
言語 C
(gcc 13.3.0)
結果
AC  
実行時間 283 ms / 2,000 ms
コード長 2,462 bytes
コンパイル時間 676 ms
コンパイル使用メモリ 33,152 KB
実行使用メモリ 18,176 KB
最終ジャッジ日時 2024-06-12 00:09:25
合計ジャッジ時間 9,317 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 34
権限があれば一括ダウンロードができます

ソースコード

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