fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. using ll = long long;
  5.  
  6. template<typename X, typename Y>
  7. bool chmax(X& a, Y b) { return (a < b) ? a = b, 1 : 0; }
  8. template<typename X, typename Y>
  9. bool chmin(X& a, Y b) { return (a > b) ? a = b, 1 : 0; }
  10.  
  11. void print(__int128 x) {
  12.     if (x == 0) {
  13.         cout << "0\n";
  14.         return;
  15.     }
  16.     if (x < 0) { cout << "-"; x = -x; }
  17.     string s;
  18.     while (x) {
  19.         s.push_back((char)(x % 10) + '0');
  20.         x /= 10;
  21.     }
  22.     reverse(s.begin(), s.end());
  23.     cout << s << '\n';
  24. }
  25.  
  26. const int N = 1e5+5;
  27.  
  28. struct Del {
  29.     ll s, f, w;
  30. };
  31.  
  32. struct Event {
  33.     ll t, w, op;
  34.     bool operator<(const Event& o) const {
  35.         return t < o.t;
  36.     }
  37. };
  38.  
  39. int n, m;
  40. vector<ll> vals;
  41.  
  42. struct Node {
  43.     int cnt;
  44.     __int128 sum;
  45. } st[4*N];
  46.  
  47. void update(int id, int l, int r, int k, ll s, ll x) {
  48.     if (l == r) {
  49.         st[id].cnt += s;
  50.         st[id].sum += (__int128)s * x;
  51.         return;
  52.     }
  53.     int mid = (l + r) >> 1;
  54.     if (k <= mid) update(id << 1, l, mid, k, s, x);
  55.     else update(id << 1 | 1, mid + 1, r, k, s, x);
  56.     st[id].cnt = st[id << 1].cnt + st[id << 1 | 1].cnt; 
  57.     st[id].sum = st[id << 1].sum + st[id << 1 | 1].sum; 
  58. }
  59.  
  60. __int128 walk(int id, int l, int r, ll x) {
  61.     if (x <= 0 || st[id].cnt == 0) return 0;
  62.     if (st[id].cnt <= x) return st[id].sum;
  63.     if (l == r) return (__int128)x * vals[l - 1];
  64.     int mid = (l + r) >> 1;
  65.     if (st[id << 1 | 1].cnt >= x) return walk(id << 1 | 1, mid + 1, r, x);
  66.     return st[id << 1 | 1].sum + walk(id << 1, l, mid, x - st[id << 1 | 1].cnt);
  67. }
  68.  
  69. void solve() {
  70.     cin >> n >> m;
  71.     vector<Del> dels;
  72.     __int128 base = 0;
  73.     for (int i = 0; i < n; i++) {
  74.         int a, b, s, f; cin >> a >> b >> s >> f;
  75.         base += (__int128)(f - s) * b;
  76.         if (a > b) {
  77.             dels.push_back({s, f, a - b});
  78.             vals.push_back(a - b);
  79.         }
  80.     }
  81.     if (dels.empty()) {
  82.         print(base);
  83.         return;
  84.     }
  85.     sort(vals.begin(), vals.end());
  86.     vals.erase(unique(vals.begin(), vals.end()), vals.end());
  87.     int sz = vals.size();
  88.     vector<Event> events;
  89.     for (auto& [s, f, w] : dels) {
  90.         events.push_back({s, w, 1});
  91.         events.push_back({f, w, -1});
  92.     }
  93.     sort(events.begin(), events.end());
  94.     __int128 ans = base;
  95.     ll last_t = events[0].t;
  96.     for (int i = 0; i < (int)events.size(); ) {
  97.         int j = i;
  98.         if (events[i].t > last_t) {
  99.             ans += walk(1, 1, sz, m) * (events[i].t - last_t);
  100.             last_t = events[i].t;
  101.         }
  102.         while (j < (int)events.size() && events[j].t == events[i].t) {
  103.             int idx = lower_bound(vals.begin(), vals.end(), events[j].w) - vals.begin() + 1;
  104.             update(1, 1, sz, idx, events[j].op, events[j].w);
  105.             j++;
  106.         }
  107.         i = j;
  108.     }
  109.     print(ans);
  110. }
  111.  
  112. int main() {
  113.     ios_base::sync_with_stdio(false); cin.tie(NULL);
  114.  
  115.     #define TASK "ORCONF"
  116.     if (fopen(TASK".INP", "r")) {
  117.         freopen(TASK".INP", "r", stdin);
  118.         freopen(TASK".OUT", "w", stdout);
  119.     }
  120.  
  121.     int tests = 1; // cin >> tests;
  122.     while (tests--) solve();
  123.  
  124.     #ifndef LOCAL
  125.     cerr << "\nTime elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
  126.     #endif
  127.     return 0;
  128. }
  129.  
Success #stdin #stdout #stderr 0s 5328KB
comments (?)
stdin
copy 
4 2
10 -10 2 3
-1 -3 1 4
6 -6 1 3
7 4 2 4
stdout
copy 
28
stderr
copy 
Time elapsed: 0.004434 s.
https://ideone.com/rbN8N5
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!