fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. using ll = long long;
  5.  
  6. const int N = 1e5+5;
  7.  
  8. struct TopK {
  9.     int M;
  10.     multiset<ll> ms, res;
  11.     ll sum;
  12.     TopK(int m) : M(m), sum(0) {}
  13.     void insert(ll v) {
  14.         if (M <= 0) return;
  15.         if ((int)ms.size() < M) {
  16.             ms.insert(v);
  17.             sum += v;
  18.         } else {
  19.             ll Min = *ms.begin();
  20.             if (v > Min) {
  21.                 ms.erase(ms.begin());
  22.                 sum -= Min;
  23.                 res.insert(Min);
  24.  
  25.                 ms.insert(v);
  26.                 sum += v;
  27.             } else res.insert(v);
  28.         }
  29.     }
  30.     void erase(ll v) {
  31.         if (M <= 0) return;
  32.         auto it = res.find(v);
  33.         if (it != res.end()) res.erase(it);
  34.         else {
  35.             auto it2 = ms.find(v);
  36.             if (it2 != ms.end()) {
  37.                 sum -= v;
  38.                 ms.erase(it2);
  39.                 if (!res.empty()) {
  40.                     auto it_max = prev(res.end());
  41.                     ll Max = *it_max;
  42.                     ms.insert(Max);
  43.                     sum += Max;
  44.                     res.erase(it_max);
  45.                 }
  46.             }
  47.         }
  48.     }
  49. };
  50.  
  51. struct Event {
  52.     ll t;
  53.     int op, id;
  54.     bool operator<(const Event& o) const {
  55.         if (t != o.t) return t < o.t;
  56.         return op < o.op;
  57.     }
  58. };
  59.  
  60. int n, m;
  61. ll a[N], b[N], s[N], f[N];
  62.  
  63. void solve() {
  64.     cin >> n >> m;
  65.     vector<Event> events;
  66.     for (int i = 0; i < n; i++) {
  67.         cin >> a[i] >> b[i] >> s[i] >> f[i];
  68.         events.push_back({s[i], 1, i});
  69.         events.push_back({f[i], -1, i});
  70.     }
  71.     sort(events.begin(), events.end());
  72.     TopK manager(m); 
  73.     ll ans = 0, base = 0, last = 0;
  74.     int i = 0, N = events.size();
  75.     while (i < N) {
  76.         ll cur = events[i].t;
  77.         if (i > 0 && cur > last) ans += (cur - last) * (base + manager.sum);
  78.         while (i < N && events[i].t == cur) {
  79.             int id = events[i].id;
  80.             ll d = a[id] - b[id];
  81.             if (events[i].op == 1) {
  82.                 base += b[id];
  83.                 if (d > 0) manager.insert(d);
  84.             } else {
  85.                 base -= b[id];
  86.                 if (d > 0) manager.erase(d);
  87.             }
  88.             i++;
  89.         }
  90.         last = cur;
  91.     }
  92.     cout << ans << '\n';
  93. }
  94.  
  95. int main() {
  96.     ios_base::sync_with_stdio(false); cin.tie(NULL);
  97.  
  98.     #define TASK "ORCONF"
  99.     if (fopen(TASK".INP", "r")) {
  100.         freopen(TASK".INP", "r", stdin);
  101.         freopen(TASK".OUT", "w", stdout);
  102.     }
  103.  
  104.     int tests = 1; // cin >> tests;
  105.     while (tests--) solve();
  106.  
  107.     #ifndef ONLINE_JUDGE
  108.     cerr << "\nTime elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
  109.     #endif
  110.  
  111.     return 0;
  112. }
Success #stdin #stdout 0.01s 5600KB
comments (?)
stdin
copy 
4 2
10 -10 2 3
-1 -3 1 4
6 -6 1 3
7 4 2 4
stdout
copy 
28
https://ideone.com/R41k7L
language:
C++14 (gcc 8.3)
created:
11 hours 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!