結果

問題 No.817 Coin donation
コンテスト
ユーザー Rumain831
提出日時 2026-08-11 16:10:03
言語 C++23(gcc16)
(gcc 16.1.0 + boost 1.90.0)
コンパイル:
g++-16 -O2 -lm -std=c++23 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
AC  
実行時間 71 ms / 2,000 ms
+ 744µs
コード長 683 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,220 ms
コンパイル使用メモリ 183,248 KB
実行使用メモリ 7,776 KB
最終ジャッジ日時 2026-08-11 16:10:09
合計ジャッジ時間 3,073 ms
ジャッジサーバーID
（参考情報） 		judge1_0 / judge2_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 14
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function 'int main()':
main.cpp:27:8: warning: 'r' may be used uninitialized [-Wmaybe-uninitialized]
   27 |     ll len=r-pos;
      |        ^~~
main.cpp:20:29: note: 'r' was declared here
   20 |     ll pos=event[id].first, r;
      |                             ^

ソースコード

diff #
raw source code 

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
using ll = long long;
using P = pair<ll, int>;

int main(void){
  ll n, k; cin >> n >> k;
  vector<P> event;
  for(int i=0; i<n; i++){
    int a, b; cin >> a >> b;
    event.emplace_back(a, 1);
    event.emplace_back(b+1, -1);
  }
  int m=event.size();
  sort(begin(event), end(event));
  ll id=0, c=0;
  while(k){
    ll pos=event[id].first, r;
    while(id<m){
      auto [npos, t]=event[id];
      r=npos;
      if(pos!=npos) break;
      c+=t, id++;
    }
    ll len=r-pos;
    if(len*c<k) k-=len*c;
    else{
      k--;
      ll ad=k/c;
      cout << pos+ad << endl; return 0;
    }
  }
  return 0; 
}
0