結果

問題 No.817 Coin donation
ユーザー MarcusAureliusAntoninusMarcusAureliusAntoninus
提出日時 2019-04-19 21:52:40
言語 C++17
(gcc 11.2.0 + boost 1.78.0)
結果
AC  
実行時間 35 ms / 2,000 ms
コード長 1,067 bytes
コンパイル時間 1,930 ms
使用メモリ 4,740 KB
最終ジャッジ日時 2022-11-22 08:59:40
合計ジャッジ時間 3,334 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge14
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
使用メモリ
testcase_00 AC 1 ms
3,664 KB
testcase_01 AC 1 ms
3,636 KB
testcase_02 AC 2 ms
3,644 KB
testcase_03 AC 1 ms
3,560 KB
testcase_04 AC 1 ms
3,664 KB
testcase_05 AC 2 ms
3,596 KB
testcase_06 AC 6 ms
3,564 KB
testcase_07 AC 7 ms
3,636 KB
testcase_08 AC 24 ms
4,216 KB
testcase_09 AC 8 ms
3,640 KB
testcase_10 AC 35 ms
4,676 KB
testcase_11 AC 34 ms
4,680 KB
testcase_12 AC 33 ms
4,740 KB
testcase_13 AC 2 ms
3,632 KB
testcase_14 AC 1 ms
3,560 KB
testcase_15 AC 1 ms
3,664 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

using pll = std::pair<long long, long long>;

std::vector<pll> AB;
int N, K;

// 引数より小さい物<kならtrue
bool lower_fewer(long long);
bool exist(long long);

int main()
{
	scanf("%d%d", &N, &K);
	AB.resize(N);
	for (auto& e: AB) scanf("%lld%lld", &e.first, &e.second);
	std::sort(AB.begin(), AB.end(),
		[](const auto& a, const auto& b) { return a.second < b.second; }
	);

	long long left{1}, right{1LL << 30};
	while (left + 1 < right)
	{
		long long mid{(left + right) / 2};
		if (lower_fewer(mid)) left = mid;
		else right = mid;
	}
	if (exist(left)) printf("%lld\n", left);
	else printf("%lld\n", std::lower_bound(AB.begin(), AB.end(), pll(left, 0))->first);

	return 0;
}

bool lower_fewer(long long num)
{
	long long sum{};
	for (auto& e: AB)
	{
		if (num <= e.first) continue;
		if (e.second < num) sum += e.second + 1 - e.first;
		else sum += num - e.first;
	}
	return sum < K;
}

bool exist(long long candidate)
{
	for (auto& e: AB)
		if (e.first <= candidate && candidate <= e.second)
			return true;
	return false;
}
0