結果

問題 No.1675 Strange Minimum Query
ユーザー ygussanyygussany
提出日時 2021-09-10 21:45:27
言語 C
(gcc 12.3.0)
結果
WA  
実行時間 -
コード長 2,216 bytes
コンパイル時間 1,229 ms
コンパイル使用メモリ 31,232 KB
実行使用メモリ 16,508 KB
最終ジャッジ日時 2024-06-11 23:14:49
合計ジャッジ時間 14,316 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 WA -
testcase_01 AC 2 ms
6,944 KB
testcase_02 WA -
testcase_03 AC 200 ms
6,940 KB
testcase_04 AC 201 ms
10,416 KB
testcase_05 AC 17 ms
10,180 KB
testcase_06 AC 235 ms
6,944 KB
testcase_07 AC 272 ms
10,260 KB
testcase_08 WA -
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 WA -
testcase_18 WA -
testcase_19 WA -
testcase_20 WA -
testcase_21 WA -
testcase_22 WA -
testcase_23 WA -
testcase_24 WA -
testcase_25 WA -
testcase_26 WA -
testcase_27 WA -
testcase_28 WA -
testcase_29 WA -
testcase_30 WA -
testcase_31 WA -
testcase_32 WA -
testcase_33 WA -
testcase_34 WA -
testcase_35 WA -
testcase_36 WA -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <stdio.h>

const int sup = 1 << 30;

void chmax(int* a, int b)
{
	if (*a < b) *a = b;
}

typedef struct {
	int left, right, flag, min, lb, lc;
} 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].flag = 0;
	v[k].min = 1;
	v[k].lb = 1;
	v[k].lc = 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_segment(lazy_seg_node v[], int k, int l, int r, int b, int c)
{
	int i, j;
	if (v[k].left > r || v[k].right < l) return;
	else if (v[k].left >= l && v[k].right <= r) {
		v[k].flag = 1;
		v[k].lb = v[k].lb * b;
		chmax(&(v[k].lc), v[k].lc * b + c);
		chmax(&(v[k].min), v[k].min * b + c);
		for (j = k, i = j >> 1; i > 0; j = i, i >>= 1) v[i].min = (v[j].min < v[j^1].min)? v[j].min: v[j^1].min;
	} else {
		if (v[k].flag == 1) {
			j = k << 1;
			chmax(&(v[j].min), v[j].min * v[k].lb + v[k].lc);
			chmax(&(v[j^1].min), v[j^1].min * v[k].lb + v[k].lc);
			v[j].flag = 1;
			v[j^1].flag = 1;
			v[j].lb = v[j].lb * v[k].lb;
			v[j^1].lb = v[j^1].lb * v[k].lb;
			chmax(&(v[j].lc), v[j].lc * v[k].lb + v[k].lc);
			chmax(&(v[j^1].lc), v[j^1].lc * v[k].lb + v[k].lc);
			v[k].flag = 0;
			v[k].lb = 1;
			v[k].lc = 0;
		}
		update_segment(v, k << 1, l, r, b, c);
		update_segment(v, (k << 1) ^ 1, l, r, b, c);
	}
}

int get_min(lazy_seg_node v[], int k, int l, int r)
{
	int tmp[2];
	if (k == 1) update_segment(v, 1, l, r, 1, 0);
	if (v[k].left > r || v[k].right < l) 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]));

	lazy_seg_node v[524288];
	init_node(v, 1, 1, N);
	for (i = 1; i <= Q; i++) update_segment(v, 1, l[i], r[i], 0, B[i]);
	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 ", get_min(v, 1, i, i));
		printf("\n");
	}
	fflush(stdout);
	return 0;
}
0