fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int main() {
  5.     int t;
  6.     cin >> t;
  7.     while (t--) {
  8.         int n;
  9.         cin >> n;
  10.         int lim = n + 64, ans = 0;
  11.         long long ex = 0;
  12.         vector<long long> a(lim + 1);
  13.         for (int i = 0; i < n; i++) {
  14.             int x;
  15.             long long y;
  16.             cin >> x >> y;
  17.             ans = max(ans, x);
  18.             if (x > lim) ex += y;
  19.             else a[x] = y;
  20.         }
  21.         auto f = [&](int k, long long ex) {
  22.             long long cnt = 1;
  23.             for (int i = lim; i >= 1; i--) {
  24.                 if (cnt > (long long)1e16) break;
  25.                 if (i >= k) ex += a[i];
  26.                 else if (a[i] >= cnt) ex += a[i] - cnt;
  27.                 else cnt += cnt - a[i];
  28.             }
  29.             return cnt <= a[0] + ex;
  30.         };
  31.         int lo = 1, hi = lim, ch = 0;
  32.         while (lo < hi) {
  33.             int mid = (lo + hi + ch) / 2;
  34.             ch ^= 1;
  35.             if (f(mid, ex)) lo = mid;
  36.             else hi = mid - 1;
  37.         }
  38.         cout << max(ans, lo) << '\n';
  39.     }
  40. }
  41.  
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/psSRlT
language:
C++ (gcc 8.3)
created:
1 day ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!