提出 #375935

ソースコード 拡げる

module main;
import std.stdio, std.conv, std.string, std.algorithm, std.array;
import std.typecons;
alias Interval = Tuple!(ulong, ulong);

void main()
{	
	auto n = readln.strip.to!int;
	auto tree = new SegmentTreeNode(0, 10_0000_0000, 0);
	foreach (i; 0..n)
	{
		auto buf = readln.strip.split.map!(to!ulong);
		tree.addRange(buf[0].convert.expand, buf[1]).writeln;
	}
}


class SegmentTreeNode
{
	ulong left, right;
	ulong maximum;
	SegmentTreeNode[] children;
	this (ulong left, ulong right, ulong amount)
	{
		this.left = left;
		this.right = right;
		if (left < right)
			this.maximum = amount;
	}
	ulong addRange(ulong left, ulong right, ulong amount)
	{
		if (right <= left)
			return this.maximum;
		if (children.empty) // I am a leaf.
		{
			assert (this.left <= left && right <= this.right);
			if (this.left < left)
				this.children ~= new SegmentTreeNode(this.left, left, maximum);
			this.children ~= new SegmentTreeNode(left, right, maximum + amount);
			if (right < this.right)
				this.children ~= new SegmentTreeNode(right, this.right, maximum);
			return maximum = children.map!(child => child.maximum).reduce!max;
		}
		foreach (child; children)
			maximum = maximum.max(child.addRange(left.max(child.left), right.min(child.right), amount));
		return maximum;
	}
}

auto convert(ulong suffix)
{
	if (suffix == 0)
		return Interval(0, 100_000_000);

	ulong prefix;
	int numDigits;
	foreach (i; 0..9)
	{
		prefix *= 10;
		prefix += suffix % 10;
		suffix /= 10;
		if (suffix)
			continue;
		numDigits = i + 1;
		break;
	}
	auto left = prefix, right = prefix + 1;
	foreach (i; 0 .. 9-numDigits)
	{
		left *= 10;
		right *= 10;
	}
	return Interval(left, right);
}

提出情報

提出日時
問題 E - 宝くじ
ユーザ TSG09
言語 D (DMD 2.066.1)
得点 0
コード長 1752 Byte
結果 TLE
実行時間 5039 ms
メモリ 31060 KiB

ジャッジ結果

セット名 All
得点 / 配点 0 / 200
結果
AC × 9
TLE × 16
セット名 テストケース
All scrambled_00.txt, scrambled_01.txt, scrambled_02.txt, scrambled_03.txt, scrambled_04.txt, scrambled_05.txt, scrambled_06.txt, scrambled_07.txt, scrambled_08.txt, scrambled_09.txt, scrambled_10.txt, scrambled_11.txt, scrambled_12.txt, scrambled_13.txt, scrambled_14.txt, scrambled_15.txt, scrambled_16.txt, scrambled_17.txt, scrambled_18.txt, scrambled_19.txt, scrambled_20.txt, scrambled_21.txt, scrambled_22.txt, scrambled_23.txt, scrambled_24.txt
ケース名 結果 実行時間 メモリ
scrambled_00.txt AC 28 ms 728 KiB
scrambled_01.txt AC 25 ms 800 KiB
scrambled_02.txt TLE 5034 ms 5524 KiB
scrambled_03.txt TLE 5035 ms 5276 KiB
scrambled_04.txt TLE 5036 ms 4752 KiB
scrambled_05.txt TLE 5034 ms 5968 KiB
scrambled_06.txt TLE 5036 ms 5956 KiB
scrambled_07.txt AC 3068 ms 4328 KiB
scrambled_08.txt TLE 5032 ms 4808 KiB
scrambled_09.txt TLE 5033 ms 5600 KiB
scrambled_10.txt TLE 5034 ms 5692 KiB
scrambled_11.txt TLE 5033 ms 5656 KiB
scrambled_12.txt TLE 5033 ms 5684 KiB
scrambled_13.txt TLE 5034 ms 5620 KiB
scrambled_14.txt TLE 5037 ms 30848 KiB
scrambled_15.txt TLE 5037 ms 30360 KiB
scrambled_16.txt TLE 5039 ms 30144 KiB
scrambled_17.txt TLE 5037 ms 31060 KiB
scrambled_18.txt TLE 5037 ms 30832 KiB
scrambled_19.txt AC 730 ms 26524 KiB
scrambled_20.txt AC 751 ms 26448 KiB
scrambled_21.txt AC 461 ms 18112 KiB
scrambled_22.txt AC 463 ms 18052 KiB
scrambled_23.txt AC 99 ms 4700 KiB
scrambled_24.txt AC 204 ms 8444 KiB