1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4. #define endl "\n"
  5. #define quick ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
  6. #define ALL(x) x.begin(),x.end()
  7. #define SORT(x) sort(ALL(x))
  8. #define FOR(a,b,c) for(ll (a)= (b);(a)<(c);++(a))
  9. #define REP(a,b) FOR(a,0,b)
  10. #define mp make_pair
  11. #define pb push_back
  12. #define pll pair<ll,ll>
  13. #define pii pair<int,int>
  14. #define vl vector<ll>
  15. #define vi vector<int>
  16. #define f first
  17. #define s second
  18. #define yy cout<<"YES"<<endl;return
  19. #define nn cout<<"NO"<<endl;return
  20. #define minus1 cout<<-1<<endl;return
  21. #define rd(a,x) REP(i,x)cin >> a[i]
  22. int ttt = 1, case_ = 0;
  23. ll n, m, k, p;
  24. template <class myType>
  25. void print_arr(myType &arr, ll L, string sep){
  26. REP(i,L){ cout << arr[i] << (i < L-1 ? sep : "\n"); }
  27. return; }
  28. /*
  29. We're interested fundamentally in the top M values of (a[i] - b[i]) added to all the values of b[i] between each two stops
  30. We have a seat of people sitting, and a set of people standing
  31. Put everyone who gets on into seats
  32. Move everyone better than them who is standing into seats
  33. Move anyone not in the top M out of a seat
  34. Move anyone with diff < 0 out of a seat
  35. */
  36. void solve() {
  37. cin >> n >> m >> p;
  38. vector<vl> people;
  39. REP(i, n) {
  40. ll a, b, l, r;
  41. cin >> a >> b >> l >> r;
  42. people.pb({l, 1, a, b});
  43. people.pb({r, -1, a, b});
  44. }
  45. SORT(people);
  46. multiset<ll> seats, stood;
  47. int j = 0;
  48. ll curr_b = 0, curr_diff = 0;
  49. ll ans = 0;
  50. FOR(i, 1, p) {
  51. while (j < 2*n && people[j][0] == i) {
  52. if (people[j][1] == 1) {
  53. // person is joining the bus
  54. ll a = people[j][2], b = people[j][3];
  55. ll diff = a - b;
  56. seats.insert(diff);
  57. curr_diff += diff;
  58. curr_b += b;
  59. }
  60. else {
  61. // person is leaving the bus
  62. ll a = people[j][2], b = people[j][3];
  63. ll diff = a - b;
  64. auto it = stood.find(diff);
  65. if (it != stood.end()) {
  66. stood.erase(stood.lower_bound(diff));
  67. }
  68. else {
  69. seats.erase(seats.lower_bound(diff));
  70. curr_diff -= diff;
  71. }
  72. curr_b -= b;
  73. }
  74. j++;
  75. }
  76. // I've put everyon
  77. while (seats.size() > m) {
  78. auto it = seats.begin();
  79. auto x = *it;
  80. seats.erase(seats.lower_bound(x));
  81. stood.insert(x);
  82. curr_diff -= x;
  83. }
  84. while (seats.size() < m && stood.size() > 0 && *stood.rbegin() > 0) {
  85. auto it = stood.rbegin();
  86. seats.insert(*it);
  87. curr_diff += *it;
  88. stood.erase(stood.lower_bound(*it));
  89. }
  90. while (seats.size() > 0 && stood.size() > 0 && *seats.begin() < *stood.rbegin() && *stood.rbegin() > 0) {
  91. auto it = stood.rbegin();
  92. auto it2 = seats.begin();
  93. auto x = *it;
  94. auto y = *it2;
  95. stood.erase(stood.lower_bound(x));
  96. seats.erase(seats.lower_bound(y));
  97. stood.insert(y);
  98. seats.insert(x);
  99. curr_diff += x - y;
  100. }
  101. while (seats.size() > 0 && *seats.begin() < 0) {
  102. auto it = seats.begin();
  103. auto x = *it;
  104. seats.erase(seats.lower_bound(x));
  105. stood.insert(x);
  106. curr_diff -= x;
  107. }
  108. ans += curr_b + curr_diff;
  109. }
  110. cout << ans << endl;
  111. return;
  112. }
  113. int main() {
  114. quick;
  115. //cin >> ttt;
  116. while (ttt--) solve();
  117. return 0;
  118. }
Comments powered by Disqus