結果
問題 | No.817 Coin donation |
ユーザー |
![]() |
提出日時 | 2020-05-12 01:26:12 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 195 ms / 2,000 ms |
コード長 | 1,926 bytes |
コンパイル時間 | 1,874 ms |
コンパイル使用メモリ | 176,380 KB |
実行使用メモリ | 18,980 KB |
最終ジャッジ日時 | 2024-07-19 13:02:57 |
合計ジャッジ時間 | 3,253 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 14 |
ソースコード
#include <bits/stdc++.h> using namespace std; typedef long long ll; #define rep(i, n) for(ll i = 0, i##_len = (n); i < i##_len; i++) #define reps(i, s, n) for(ll i = (s), i##_len = (n); i < i##_len; i++) #define rrep(i, n) for(ll i = (n) - 1; i >= 0; i--) #define rreps(i, e, n) for(ll i = (n) - 1; i >= (e); i--) #define all(x) (x).begin(), (x).end() #define rall(x) (x).rbegin(), (x).rend() #define sz(x) ((ll)(x).size()) #define len(x) ((ll)(x).length()) #define endl "\n" ll n, k; vector<ll> a, b; vector<ll> pat, dp; ll get_index(ll val) { return lower_bound(all(pat), val) - pat.begin(); } ll get_count(ll val) { ll ans = 0; ll pc = sz(pat); rep(i, pc) { if (val < pat[i]) break; if (i == (pc - 1)) { ans += dp[i * 2]; break; } ans += dp[i * 2]; if (pat[i + 1] <= val) { ll d = pat[i + 1] - pat[i] - 1; ans += dp[i * 2 + 1] * d; } else { ll d = val - pat[i]; ans += dp[i * 2 + 1] * d; } } return ans; } int main() { cin.tie(0); ios::sync_with_stdio(false); // ifstream in("input.txt"); // cin.rdbuf(in.rdbuf()); cin >> n >> k; a.resize(n); b.resize(n); rep(i, n) cin >> a[i] >> b[i]; set<ll> tmp; rep(i, n) { tmp.insert(a[i]); tmp.insert(b[i]); } for(auto x : tmp) pat.push_back(x); dp.resize(2 * sz(pat), 0); rep(i, n) { ll lidx = get_index(a[i]); ll ridx = get_index(b[i]); dp[lidx * 2]++; dp[ridx * 2 + 1]--; } rep(i, 2 * sz(pat)) dp[i + 1] += dp[i]; ll low = 0, high = LONG_LONG_MAX; while((low + 1) < high) { ll mid = (low + high) / 2; ll cnt = get_count(mid); if (cnt >= k) { high = mid; } else { low = mid; } } cout << high << endl; return 0; }