fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. using ll = long long;
  5.  
  6. int main() {
  7. 	ios::sync_with_stdio(0), cin.tie(0);
  8. 	int N; cin >> N;
  9. 	vector<ll> L(N), R(N);
  10. 	for (int i = 0; i < N; i++) {
  11. 		cin >> L[i] >> R[i];
  12. 	}
  13.  
  14. 	ll cost = 0;
  15. 	ll los = 0, his = 0;
  16. 	priority_queue<ll, vector<ll>, less<ll>> lo;
  17. 	priority_queue<ll, vector<ll>, greater<ll>> hi;
  18. 	lo.push(L[0]), hi.push(L[0]);
  19.  
  20. 	for (int i = 1; i < N; i++) {
  21. 		los -= (R[i] - L[i]);
  22. 		his += (R[i-1] - L[i-1]);
  23.  
  24. 		ll vlo = lo.top() + los;
  25. 		ll vhi = hi.top() + his;
  26. 		if (vlo <= L[i] && L[i] <= vhi) {
  27. 			lo.push(L[i] - los);
  28. 			hi.push(L[i] - his);
  29. 		} else if (vhi < L[i]) {
  30. 			cost += L[i] - vhi;
  31. 			hi.pop();
  32. 			lo.push(vhi - los);
  33. 			hi.push(L[i] - his);
  34. 			hi.push(L[i] - his);
  35. 		} else if (L[i] < vlo) {
  36. 			cost += vlo - L[i];
  37. 			lo.pop();
  38. 			hi.push(vlo - his);
  39. 			lo.push(L[i] - los);
  40. 			lo.push(L[i] - los);
  41. 		}
  42. 	}
  43.  
  44. 	cout << cost << '\n';
  45.  
  46. 	return 0;
  47. }
  48.  
Success #stdin #stdout 0s 4360KB
comments (?)
stdin
copy 
5
123456 789012
123 456
12 345678901
123456 789012
1 23
stdout
copy 
246433
https://ideone.com/zwqbJv
language:
C++14 (gcc 8.3)
created:
4 years 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!