結果

問題 No.230 Splarraay ｽﾌﾟﾗﾚｪｰｲ
コンテスト
ユーザー ゴリポン先生
提出日時 2026-04-27 16:54:12
言語 D
(dmd 2.112.0)
コンパイル:
dmd -fPIE -m64 -w -wi -O -release -inline -I/opt/dmd/src/druntime/import/ -I/opt/dmd/src/phobos -L-L/opt/dmd/linux/lib64/ -fPIC _filename_
実行:
./Main
結果
AC  
実行時間 138 ms / 5,000 ms
コード長 1,582 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 4,584 ms
コンパイル使用メモリ 195,896 KB
実行使用メモリ 36,864 KB
最終ジャッジ日時 2026-04-27 16:54:25
合計ジャッジ時間 7,156 ms
ジャッジサーバーID
（参考情報） 		judge3_1 / judge2_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 17
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

module main;
// https://kmjp.hatenablog.jp/entry/2015/06/21/1030 より
// 遅延評価セグメント木
import std;

struct SegTreeLazy(int NV) {
	int[NV * 2] val, to;
	int comp(int l, int r) { return l + r; }
	int getVal(int x, int y, int l = 0, int r = NV, int k = 1)
	{
		if (r <= x || y <= l) return 0;
		if (x <= l && r <= y) return to[k];
		x = max(x, l);
		y = min(y, r);
		if (val[k] >= 0) return val[k] ? y - x : 0;
		return comp(getVal(x, y, l, (l + r) / 2, k * 2), getVal(x, y, (l + r) / 2, r, k * 2 + 1));
	}
	void update(int x, int y, int v, int l = 0, int r = NV, int k = 1)
	{
		if (l >= r) return;
		if (x <= l && r <= y) {
			val[k] = v;
			to[k] = val[k] ? r - l : 0;
		}
		else if (l < y && x < r) {
			if (val[k] != -1) {
				val[k * 2] = val[k * 2 + 1] = val[k];
				to[k * 2] = to[k * 2 + 1] = val[k] ? (r - l) / 2 : 0;
				val[k] = -1;
			}
			update(x, y, v, l, (l + r) / 2, k * 2);
			update(x, y, v, (l + r) / 2, r, k * 2 + 1);
			to[k] = comp(to[k * 2], to[k * 2 + 1]);
		}
	}
}

void main()
{
	// 入力
	int N = readln.chomp.to!int;
	// クエリの処理
	auto st = new SegTreeLazy!(1 << 20)[](2);
	long AA, BB;
	foreach (_; 0 .. readln.chomp.to!int) {
		int x, l, r;
		readln.chomp.formattedRead("%d %d %d", x, l, r);
		if (x == 0) {
			int a = st[0].getVal(l, r + 1);
			int b = st[1].getVal(l, r + 1);

			if (a > b) AA += a;
			if (a < b) BB += b;
		}
		else {
			st[x - 1].update(l, r + 1, 1);
			st[(x - 1) ^ 1].update(l, r + 1, 0);
		}
	}
	AA += st[0].getVal(0, N);
	BB += st[1].getVal(0, N);
	// 答えの出力
	writefln("%d %d", AA, BB);
}
0