結果

問題 No.817 Coin donation
ユーザー MarcusAureliusAntoninus
提出日時 2019-04-19 21:52:40
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 36 ms / 2,000 ms
コード長 1,067 bytes
コンパイル時間 1,960 ms
コンパイル使用メモリ 199,020 KB
最終ジャッジ日時 2025-01-07 02:41:31
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 14
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:14:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   14 |         scanf("%d%d", &N, &K);
      |         ~~~~~^~~~~~~~~~~~~~~~
main.cpp:16:32: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   16 |         for (auto& e: AB) scanf("%lld%lld", &e.first, &e.second);
      |                           ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

ソースコード

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