fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. typedef long long ll;
  6. typedef unsigned long long ull;
  7. typedef pair<int, int> pii;
  8. typedef pair<ll, ll> pll;
  9. typedef vector<int> vi;
  10. typedef vector<ll> vll;
  11. typedef string str;
  12.  
  13. #define pb push_back
  14. #define mp make_pair
  15. #define fi first
  16. #define se second
  17. #define all(x) (x).begin(), (x).end()
  18. #define len(x) ((int)(x).size())
  19.  
  20. #define forn(i, n) for (int i = 0; i < (int)(n); ++i)
  21. #define forr(i, l, r) for (int i = (int)(l); i <= (int)(r); ++i)
  22. #define ford(i, r, l) for (int i = (int)(r); i >= (int)(l); --i)
  23.  
  24. #define cmin(a, b) a = min(a, b)
  25. #define cmax(a, b) a = max(a, b)
  26.  
  27. const ll INF = 2e15; // Ngưỡng chặn trên để ngăn tràn số hệ nhị phân
  28.  
  29. bool check(ll T, const vector<pll>& elements) {
  30.     ll surplus = 0;
  31.     vector<pll> under_T;
  32.  
  33.     // Tách tài nguyên: các số >= T tự động hóa thành 0
  34.     for (const auto& p : elements) {
  35.         if (p.fi >= T) {
  36.             surplus += p.se;
  37.         } else {
  38.             under_T.pb(p);
  39.         }
  40.     }
  41.  
  42.     ll R = 1; // Yêu cầu ban đầu tại đích T
  43.     ll curr = T;
  44.  
  45.     for (const auto& p : under_T) {
  46.         ll u = p.fi;
  47.         ll cnt = p.se;
  48.  
  49.         ll L = curr - 1 - u; // Số lượng tầng trống bị bỏ qua giữa các số
  50.         if (L > 0) {
  51.             if (R > 0 && L >= 60) R = INF;
  52.             else {
  53.                 if (R > 0 && (INF / (1LL << L) < R)) R = INF;
  54.                 else R = R * (1LL << L);
  55.             }
  56.         }
  57.  
  58.         if (u > 0) {
  59.             if (cnt >= R) {
  60.                 surplus += (cnt - R); // Lượng dư thừa đẩy về làm tài nguyên số 0
  61.                 R = 0; 
  62.             } else {
  63.                 R = 2 * R - cnt; // Lan truyền nhân đôi lượng thiếu hụt xuống dưới
  64.             }
  65.             curr = u;
  66.         } else { // Khi chạm tới u == 0
  67.             ll extra = (R > cnt) ? (R - cnt) : 0LL;
  68.             return surplus >= extra;
  69.         }
  70.         if (R > INF) R = INF;
  71.     }
  72.  
  73.     // Xử lý khoảng trống cuối cùng nếu danh sách chưa chạm đến số 0
  74.     ll L = curr;
  75.     if (L > 0) {
  76.         if (R > 0 && L >= 60) R = INF;
  77.         else {
  78.             if (R > 0 && (INF / (1LL << L) < R)) R = INF;
  79.             else R = R * (1LL << L);
  80.         }
  81.     }
  82.     return surplus >= R;
  83. }
  84.  
  85. void solve() {
  86.     int n;
  87.     if (!(cin >> n)) return;
  88.  
  89.     vector<pll> elements(n);
  90.     ll max_x = 0;
  91.     forn(i, n) {
  92.         cin >> elements[i].fi >> elements[i].se;
  93.         cmax(max_x, elements[i].fi);
  94.     }
  95.  
  96.     // Sắp xếp các phần tử giảm dần theo giá trị x_i
  97.     sort(all(elements), [](const pll& a, const pll& b) {
  98.         return a.fi > b.fi;
  99.     });
  100.  
  101.     // Phạm vi tìm kiếm tối ưu quanh max_x do tính chất tăng lũy thừa của yêu cầu trống
  102.     ll low = max_x, high = max_x + 65, ans = max_x;
  103.     while (low <= high) {
  104.         ll mid = low + (high - low) / 2;
  105.         if (check(mid, elements)) {
  106.             ans = mid;
  107.             low = mid + 1;
  108.         } else {
  109.             high = mid - 1;
  110.         }
  111.     }
  112.     cout << ans << "\n";
  113. }
  114.  
  115. int main() {
  116.     ios_base::sync_with_stdio(false);
  117.     cin.tie(NULL);
  118.  
  119.     int t;
  120.     if (cin >> t) {
  121.         while (t--) {
  122.             solve();
  123.         }
  124.     }
  125.     return 0;
  126. }
  127.  
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
10
4
2 2
0 3
4 1
1 2
1
10 1
1
2 3
3
0 1
2 2
3 1
3
0 4
1 2
2 1
1
0 100
2
2 7
3 1
2
0 1
3 3
3
0 1
1 1
59 1
4
0 5
1 1
2 3
3 1
stdout
copy 
5
11
4
4
4
7
6
5
60
5
https://ideone.com/AOQSgI
language:
C++14 (gcc 8.3)
created:
2 days 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!