fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. bool memory1;
  4.  
  5. typedef long long ll;
  6. typedef unsigned long long ull;
  7. typedef double dbe;
  8. typedef pair<ll, ll> pll;
  9. typedef pair<int, int> pii;
  10. typedef vector<ll> vll;
  11. typedef vector<int> vii;
  12.  
  13. #define openFile(name) freopen((name ".inp"), "r", stdin), freopen((name ".out"), "w", stdout)
  14. #define FOR(i, a, b, x) for (int i = (a); i <= (b); i += (x))
  15. #define ROF(i, a, b, x) for (int i = (a); i >= (b); i += (x))
  16. #define fi first
  17. #define se second
  18. #define MASK(x) (1LL << (x))
  19. #define getBit(mask, i) (((mask) >> (i)) & 1)
  20. #define BitOn(mask) (__builtin_popcountll(mask))
  21.  
  22. const int maxN = 2e5 + 5;
  23. //const ll maxBit = MASK(8) + 2;
  24. const ll LOG = 20;
  25. const ll INF18 = 1e18;
  26. const int INF9 = 1e9;
  27. //const ll INF3f = 0x3f3f3f3f3f3f3f3f;
  28. const ll MOD = 1e9 + 7;
  29.  
  30. //////////////////////////////////////////////
  31. /////////////////nhan0123456//////////////////
  32. //////////////////////////////////////////////
  33.  
  34. struct SegmentTree {
  35.     vll stWei, stMin;
  36.     int n;
  37.     SegmentTree() {}
  38.     SegmentTree(int _) {
  39.         n = _;
  40.         stWei.assign(4 * n + 7, 0);
  41.         stMin.assign(4 * n + 7, 0);
  42.     }
  43.     void update(int u, ll v) {
  44.         int id = 1, l = 1, r = n;
  45.         while (l < r) {
  46.             int mid = (l + r) >> 1;
  47.             if (u > mid) {id = 2 * id + 1; l = mid + 1;}
  48.             else {id = 2 * id; r = mid;}
  49.         }
  50.         stWei[id] = v;
  51.         stMin[id] = stWei[id];
  52.  
  53.         while (id /= 2) {
  54.             stWei[id] = stWei[2 * id] + stWei[2 * id + 1];
  55.             stMin[id] = min(stMin[2 * id], stMin[2 * id + 1]);
  56.         }
  57.     }
  58.     // tim vi tri i xa 1 nhat sao cho 1..i <= val
  59.     int walkSum(ll val) {return walkSum(val, 1, 1, n);}
  60.     int walkSum(ll val, int id, int l, int r) {
  61.         if (l == r) return stWei[id] <= val ? l : -1;
  62.  
  63.         int mid = (l + r) >> 1;
  64.         if (stWei[2 * id] > val) return walkSum(val, 2 * id, l, mid);
  65.         int t = walkSum(val - stWei[2 * id], 2 * id + 1, mid + 1, r);
  66.         if (t != -1) return t;
  67.         return walkSum(val, 2 * id, l, mid);
  68.     }
  69.     // tim vi tri i gan 1 nhat sao cho ai <= val
  70.     int walkMin(int L, ll val) {return walkMin(L, val, 1, 1, n);}
  71.     int walkMin(int L, ll val, int id, int l, int r) {
  72.         if (stMin[id] > val) return -1;
  73.         if (r < L) return -1;
  74.         if (l == r) return stMin[id] <= val ? l : -1;
  75.  
  76.         int mid = (l + r) >> 1;
  77.         int t = walkMin(L, val, 2 * id, l, mid);
  78.         if (t != -1) return t;
  79.         return walkMin(L, val, 2 * id + 1, mid + 1, r);
  80.     }
  81.     ll get(int u, int v) {return get(u, v, 1, 1, n);}
  82.     ll get(int u, int v, int id, int l, int r) {
  83.         if (r < u || v < l || u > v) return 0;
  84.         if (u <= l && r <= v) return stWei[id];
  85.  
  86.         int mid = (l + r) >> 1;
  87.         ll g1 = get(u, v, 2 * id, l, mid);
  88.         ll g2 = get(u, v, 2 * id + 1, mid + 1, r);
  89.         return g1 + g2;
  90.     }
  91. };
  92.  
  93. struct BIT {
  94.     vll bit;
  95.     int n;
  96.     BIT() {}
  97.     BIT(int _) {
  98.         n = _;
  99.         bit.assign(n + 2, 0);
  100.     }
  101.     void update(int i, ll val) {
  102.         for (; i <= n; i += i & -i) bit[i] += val;
  103.     }
  104.     ll get(int i) {
  105.         ll ans = 0;
  106.         for (; i > 0; i -= i & -i) ans += bit[i];
  107.         return ans;
  108.     }
  109.     ll get(int l, int r) {return get(r) - get(l - 1);}
  110. };
  111.  
  112. ll n, P;
  113. pll a[maxN];
  114. int id[maxN];
  115.  
  116. bool ssHp(int i, int j) {
  117.     return a[i].fi > a[j].fi;
  118. }
  119.  
  120. void Solve() {
  121.     FOR (i, 1, n, 1) id[i] = i;
  122.     sort(id + 1, id + n + 1, ssHp);
  123. //    FOR (i, 1, n, 1) cout << i << " " << a[id[i]].fi << " " << a[id[i]].se << "\n";
  124.     SegmentTree ST(n);
  125.     BIT bit(n);
  126.     ll ansHp = 0, ansT = INF18; // chon hp mx kchon T min
  127.  
  128.     FOR (i, 1, n, 0) {
  129.         int j = i;
  130.         while (j <= n && a[id[i]].fi == a[id[j]].fi) {
  131.             ST.update(id[j], a[id[j]].se);
  132.             bit.update(id[j], a[id[j]].fi);
  133.             ++j;
  134.         }
  135.         ll tmpHp = 0, tmpT = a[id[j]].fi;
  136.         if (j > n) tmpT = 0;
  137.  
  138.         ll val = P;
  139.         int cur = ST.walkMin(1, val);
  140.         while (cur != -1) {
  141.             ll tmpVal = ST.get(1, cur - 1) + val;
  142.             int nxt = ST.walkSum(tmpVal);
  143.             if (nxt == -1) break;
  144.  
  145.             tmpHp += bit.get(cur, nxt);
  146.             val -= ST.get(cur, nxt);
  147.             if (nxt + 1 > n) break;
  148.             cur = ST.walkMin(nxt + 1, val);
  149.         }
  150.         if (ansHp < tmpHp) {
  151.             ansHp = tmpHp;
  152.             ansT = tmpT;
  153.         }
  154.         else if (ansHp == tmpHp)
  155.             ansT = min(ansT, tmpT);
  156. //        if (ansHp == 13487) {
  157. //            int x = 1;
  158. //        }
  159.         i = j;
  160.     }
  161.     cout << ansHp << " " << ansT;
  162. }
  163.  
  164. void input() {
  165.     int T;
  166.     cin >> T;
  167.     while (T--) {
  168.         cin >> n >> P;
  169.         FOR (i, 1, n, 1) cin >> a[i].fi >> a[i].se;
  170.         Solve();
  171.         cout << "\n";
  172.     }
  173. }
  174.  
  175. int main() {
  176.     openFile("FESTIVAL");
  177.     ios_base::sync_with_stdio(0);
  178.     cin.tie(0);
  179.     input();
  180.  
  181.     //bool memory2;
  182.     //cerr << "\n\n\nTime: "<< 1000.0 * clock() / CLOCKS_PER_SEC << " ms";
  183.     //cerr << "\n\n\nMemory: "<< abs(&memory1 - &memory2) * 1.0 / MASK(20) <<" MB";
  184.  
  185.     return 0;
  186. }
  187.  
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/VSwwSL
language:
C++14 (gcc 8.3)
created:
11 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!