#340424 (C++17) No.817 Coin donation

• 問題: No.817 Coin donation
• ユーザー: MarcusAureliusAntoninus
• 提出日時: 2019-04-19 21:52:40
• 言語: C++17 (gcc 13.2.0 + boost 1.83.0)
• 結果: AC
• 実行時間: 39 ms / 2,000 ms
• コード長: 1,067 bytes
• コンパイル時間: 2,274 ms
• コンパイル使用メモリ: 209,080 KB
• 実行使用メモリ: 4,868 KB
• 最終ジャッジ日時: 2023-10-24 01:43:38
• 合計ジャッジ時間: 3,404 ms
• ジャッジサーバーID （参考情報）: judge14 / judge12

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	2 ms; 4,348 KB
testcase_01	AC	2 ms; 4,348 KB
testcase_02	AC	2 ms; 4,348 KB
testcase_03	AC	2 ms; 4,348 KB
testcase_04	AC	1 ms; 4,348 KB
testcase_05	AC	3 ms; 4,348 KB
testcase_06	AC	7 ms; 4,348 KB
testcase_07	AC	8 ms; 4,348 KB
testcase_08	AC	27 ms; 4,348 KB
testcase_09	AC	9 ms; 4,348 KB
testcase_10	AC	39 ms; 4,868 KB
testcase_11	AC	39 ms; 4,868 KB
testcase_12	AC	39 ms; 4,868 KB
testcase_13	AC	2 ms; 4,348 KB
testcase_14	AC	2 ms; 4,348 KB
testcase_15	AC	2 ms; 4,348 KB

ソースコード

#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;
}