Kevin_Zhang

Untitled

Oct 23rd, 2021
1,032
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. using ll = long long;
  4. #define pb emplace_back
  5. #define AI(i) begin(i), end(i)
  6. template<class T> bool chmin(T &a, T b) { return b < a && (a = b, true); }
  7. template<class T> bool chmax(T &a, T b) { return a < b && (a = b, true); }
  8. #ifdef KEV
  9. #define DE(args...) kout("[ " + string(#args) + " ] = ", args)
  10. void kout() { cerr << endl; }
  11. template<class T, class ...U> void kout(T a, U ...b) { cerr << a << ' ', kout(b...); }
  12. template<class T> void debug(T l, T r) { while (l != r) cerr << *l << " \n"[next(l)==r], ++l; }
  13. #else
  14. #define DE(...) 0
  15. #define debug(...) 0
  16. #endif
  17. // My bug list :
  18. // integer overflow
  19. // 0based, 1based forgotten
  20. // index out of bound
  21. // n, m, i, j typo
  22. // some cases are missing
  23.  
  24. const int MAX_N = 3010, inf = 1e9;
  25.  
  26. int need(vector<tuple<int,int,int>> lhs) {
  27.     sort(AI(lhs));
  28.     //     r, x
  29.     priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;
  30.     int lst = -1;
  31.     for (auto [l, r, x] : lhs) {
  32.         int d = l - lst;
  33.         while (pq.size() && d) {
  34.             auto [r, x] = pq.top(); pq.pop();
  35.             int v = min(x, d);
  36.             x -= v, d -= v;
  37.             lst += v;
  38.             if (x > 0) pq.emplace(r, x);
  39.         }
  40.         pq.emplace(r, x);
  41.         lst = l;
  42.     }
  43.     while (pq.size()) {
  44.         auto [r, x] = pq.top(); pq.pop();
  45.         if (lst+x-1 > r) return false;
  46.         lst += x;
  47.     }
  48.     return true;
  49. }
  50.  
  51. vector<tuple<int,int,int>> operator + (vector<tuple<int,int,int>> t, tuple<int,int,int> v) { t.pb(v); return t; }
  52.  
  53. int32_t main() {
  54.     ios_base::sync_with_stdio(0), cin.tie(0);
  55.     int n;
  56.     cin >> n;
  57.     vector<tuple<int,int,int,int>> seg(n);
  58.     for (auto &[p, l, r, x] : seg)
  59.         cin >> l >> r >> x >> p;
  60.  
  61.     vector<tuple<int,int,int>> vset;
  62.  
  63.     ll res = 0;
  64.  
  65.     sort(AI(seg), greater<>());
  66.  
  67.     for (auto [p, l, r, x] : seg) {
  68.         int lo = 0, hi = x, mid;
  69.         while (lo < hi) {
  70.             mid = lo + hi >> 1;
  71.             if (valid(vset + make_tuple(l, r, mid+1)))
  72.                 lo = mid+1;
  73.             else
  74.                 hi = mid;
  75.         }
  76.         ll c = lo;
  77.         assert(c <= x);
  78.         res += c * p;
  79.         if (c) {
  80.             vset.pb(l, r, c);
  81.         }
  82.     }
  83.  
  84.     cout << res << '\n';
  85. }
  86.  
RAW Paste Data