fork download
copy 
  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 (ll i = (a); i <= (b); i += (x))
  15. #define ROF(i, a, b, x) for (ll 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 stVal, stWei, stMin;
  36.     int n;
  37.     SegmentTree() {}
  38.     SegmentTree(int _) {
  39.         n = _;
  40.         stVal.assign(4 * n + 7, 0);
  41.         stWei.assign(4 * n + 7, 0);
  42.         stMin.assign(4 * n + 7, 0);
  43.     }
  44.     void update(int u, pll &v) {
  45.         int id = 1, l = 1, r = n;
  46.         while (l < r) {
  47.             int mid = (l + r) >> 1;
  48.             if (u > mid) {id = 2 * id + 1; l = mid + 1;}
  49.             else {id = 2 * id; r = mid;}
  50.         }
  51.         tie(stVal[id], stWei[id]) = v;
  52.         stMin[id] = stWei[id];
  53.  
  54.         while (id /= 2) {
  55.             stVal[id] = stVal[2 * id] + stVal[2 * id + 1];
  56.             stWei[id] = stWei[2 * id] + stWei[2 * id + 1];
  57.             stMin[id] = min(stMin[2 * id], stMin[2 * id + 1]);
  58.         }
  59.     }
  60.     // tim vi tri i xa 1 nhat sao cho 1..i <= val
  61.     int walkSum(ll val) {return walkSum(val, 1, 1, n);}
  62.     int walkSum(ll val, int id, int l, int r) {
  63.         if (l == r) return stWei[id] <= val ? l : -1;
  64.  
  65.         int mid = (l + r) >> 1;
  66.         if (stWei[2 * id] > val) return walkSum(val, 2 * id, l, mid);
  67.         int t = walkSum(val - stWei[2 * id], 2 * id + 1, mid + 1, r);
  68.         if (t != -1) return t;
  69.         return walkSum(val, 2 * id, l, mid);
  70.     }
  71.     // tim vi tri i gan 1 nhat sao cho ai <= val
  72.     int walkMin(int L, ll val) {return walkMin(L, val, 1, 1, n);}
  73.     int walkMin(int L, ll val, int id, int l, int r) {
  74.         if (stMin[id] > val) return -1;
  75.         if (r < L) return -1;
  76.         if (l == r) return stMin[id] <= val ? l : -1;
  77.  
  78.         int mid = (l + r) >> 1;
  79.         int t = walkMin(L, val, 2 * id, l, mid);
  80.         if (t != -1) return t;
  81.         return walkMin(L, val, 2 * id + 1, mid + 1, r);
  82.     }
  83.     ll get(int u, int v, int ty) {return get(u, v, ty, 1, 1, n);}
  84.     ll get(int u, int v, int ty, int id, int l, int r) {
  85.         if (r < u || v < l || u > v) return 0;
  86.         if (u <= l && r <= v) {
  87.             if (ty == 0) return stVal[id];
  88.             else return stWei[id];
  89.         }
  90.         int mid = (l + r) >> 1;
  91.         ll g1 = get(u, v, ty, 2 * id, l, mid);
  92.         ll g2 = get(u, v, ty, 2 * id + 1, mid + 1, r);
  93.         return g1 + g2;
  94.     }
  95. };
  96.  
  97. ll n, P;
  98. pll a[maxN];
  99. int id[maxN];
  100. SegmentTree ST;
  101.  
  102. bool ssHp(int i, int j) {
  103.     return a[i].fi > a[j].fi;
  104. }
  105.  
  106. void Solve() {
  107.     FOR (i, 1, n, 1) id[i] = i;
  108.     sort(id + 1, id + n + 1, ssHp);
  109. //    FOR (i, 1, n, 1) cout << i << " " << a[id[i]].fi << " " << a[id[i]].se << "\n";
  110.     ST = SegmentTree(n);
  111.     ll ansHp = 0, ansT = INF18; // chon hp mx kchon T min
  112.  
  113.     FOR (i, 1, n, 0) {
  114.         int j = i;
  115.         while (j <= n && a[id[i]].fi == a[id[j]].fi) {
  116.             ST.update(id[j], a[id[j]]);
  117.             ++j;
  118.         }
  119.         ll tmpHp = 0, tmpT = a[id[j]].fi;
  120.         if (j > n) tmpT = 0;
  121.  
  122.         ll val = P;
  123.         int cur = ST.walkMin(1, val);
  124.         while (cur != -1) {
  125.             ll tmpVal = ST.get(1, cur - 1, 1) + val;
  126.             int nxt = ST.walkSum(tmpVal);
  127.             if (nxt == -1) break;
  128.  
  129.             tmpHp += ST.get(cur, nxt, 0);
  130.             val -= ST.get(cur, nxt, 1);
  131.             if (nxt + 1 > n) break;
  132.             cur = ST.walkMin(nxt + 1, val);
  133.         }
  134.         if (ansHp < tmpHp) {
  135.             ansHp = tmpHp;
  136.             ansT = tmpT;
  137.         }
  138.         else if (ansHp == tmpHp)
  139.             ansT = min(ansT, tmpT);
  140. //        if (ansHp == 13487) {
  141. //            int x = 1;
  142. //        }
  143.         i = j;
  144.     }
  145.     cout << ansHp << " " << ansT;
  146. }
  147.  
  148. void input() {
  149.     int T;
  150.     cin >> T;
  151.     while (T--) {
  152.         cin >> n >> P;
  153.         FOR (i, 1, n, 1) cin >> a[i].fi >> a[i].se;
  154.         Solve();
  155.         cout << "\n";
  156.     }
  157. }
  158.  
  159. int main() {
  160.     openFile("FESTIVAL");
  161.     ios_base::sync_with_stdio(0);
  162.     cin.tie(0);
  163.     input();
  164.  
  165.     //bool memory2;
  166.     //cerr << "\n\n\nTime: "<< 1000.0 * clock() / CLOCKS_PER_SEC << " ms";
  167.     //cerr << "\n\n\nMemory: "<< abs(&memory1 - &memory2) * 1.0 / MASK(20) <<" MB";
  168.  
  169.     return 0;
  170. }
  171.  
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/c7qE25
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!