Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- using ll = long long;
- #define pb emplace_back
- #define AI(i) begin(i), end(i)
- template<class T> bool chmin(T &a, T b) { return b < a && (a = b, true); }
- template<class T> bool chmax(T &a, T b) { return a < b && (a = b, true); }
- #ifdef KEV
- #define DE(args...) kout("[ " + string(#args) + " ] = ", args)
- void kout() { cerr << endl; }
- template<class T, class ...U> void kout(T a, U ...b) { cerr << a << ' ', kout(b...); }
- template<class T> void debug(T l, T r) { while (l != r) cerr << *l << " \n"[next(l)==r], ++l; }
- #else
- #define DE(...) 0
- #define debug(...) 0
- #endif
- // My bug list :
- // integer overflow
- // 0based, 1based forgotten
- // index out of bound
- // n, m, i, j typo
- // some cases are missing
- const int MAX_N = 3010, inf = 1e9;
- int need(vector<tuple<int,int,int>> lhs) {
- sort(AI(lhs));
- // r, x
- priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;
- int lst = -1;
- for (auto [l, r, x] : lhs) {
- int d = l - lst;
- while (pq.size() && d) {
- auto [r, x] = pq.top(); pq.pop();
- int v = min(x, d);
- x -= v, d -= v;
- lst += v;
- if (x > 0) pq.emplace(r, x);
- }
- pq.emplace(r, x);
- lst = l;
- }
- while (pq.size()) {
- auto [r, x] = pq.top(); pq.pop();
- if (lst+x-1 > r) return false;
- lst += x;
- }
- return true;
- }
- vector<tuple<int,int,int>> operator + (vector<tuple<int,int,int>> t, tuple<int,int,int> v) { t.pb(v); return t; }
- int32_t main() {
- ios_base::sync_with_stdio(0), cin.tie(0);
- int n;
- cin >> n;
- vector<tuple<int,int,int,int>> seg(n);
- for (auto &[p, l, r, x] : seg)
- cin >> l >> r >> x >> p;
- vector<tuple<int,int,int>> vset;
- ll res = 0;
- sort(AI(seg), greater<>());
- for (auto [p, l, r, x] : seg) {
- int lo = 0, hi = x, mid;
- while (lo < hi) {
- mid = lo + hi >> 1;
- if (valid(vset + make_tuple(l, r, mid+1)))
- lo = mid+1;
- else
- hi = mid;
- }
- ll c = lo;
- assert(c <= x);
- res += c * p;
- if (c) {
- vset.pb(l, r, c);
- }
- }
- cout << res << '\n';
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement