fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. template <typename T> void setmax(T& a, T b) {
  5. 	if (b > a) a = b;
  6. }
  7. template <typename T> void setmin(T& a, T b) {
  8. 	if (b < a) a = b;
  9. }
  10.  
  11. using ll = long long;
  12. const ll INF = 1e18;
  13.  
  14. const int MAXN = 1.1e5;
  15. int N, Q;
  16. ll A[MAXN];
  17. ll B[MAXN];
  18.  
  19. const int S = 250;
  20. const int MAXC = MAXN / S + 10;
  21.  
  22. pair<ll, ll> evts[MAXN];
  23. ll pref[MAXN];
  24. ll suff[MAXN];
  25.  
  26. struct range_t {
  27. 	int l, r;
  28. 	ll val;
  29.  
  30. 	range_t(int l_, int r_) : l(l_), r(r_), val(0) {
  31. 		// initialize here
  32.  
  33. 		for (int i = l; i < r; i++) {
  34. 			evts[i] = {B[i] - A[i], B[i]};
  35. 		}
  36. 		sort(evts + l, evts + r);
  37.  
  38. 		{
  39. 			ll curVal = INF;
  40. 			for (int i = l; i < r; i++) {
  41. 				setmin(curVal, evts[i].second - evts[i].first);
  42. 				pref[i] = curVal;
  43. 			}
  44. 		}
  45. 		{
  46. 			ll curVal = INF;
  47. 			for (int i = r-1; i >= l; i--) {
  48. 				setmin(curVal, evts[i].second);
  49. 				suff[i] = curVal;
  50. 			}
  51. 		}
  52. 	}
  53.  
  54. 	void add(int d) {
  55. 		val += d;
  56. 	}
  57.  
  58. 	void finalize() {
  59. 		for (int i = l; i < r; i++) {
  60. 			A[i] += val;
  61. 		}
  62. 	}
  63.  
  64. 	ll query() {
  65. 		int pos = int(lower_bound(evts + l, evts + r, make_pair(val, 0ll)) - evts);
  66. 		ll ans = INF;
  67. 		if (l < pos) {
  68. 			setmin(ans, pref[pos-1] + val);
  69. 		}
  70. 		if (pos < r) {
  71. 			setmin(ans, suff[pos]);
  72. 		}
  73. 		return ans;
  74. 	}
  75. };
  76.  
  77. struct query_t {
  78. 	int t, l, r, x;
  79. };
  80.  
  81. int main() {
  82. 	ios::sync_with_stdio(0), cin.tie(0);
  83.  
  84. 	cin >> N >> Q;
  85. 	for (int i = 0; i < N; i++) {
  86. 		cin >> A[i] >> B[i];
  87. 	}
  88.  
  89. 	for (int st = 0; st < Q; st += S) {
  90. 		int M = min(Q, st+S) - st;
  91. 		vector<query_t> queries(M);
  92. 		vector<int> pts; pts.reserve(2*M);
  93. 		for (auto& it : queries) {
  94. 			cin >> it.t >> it.l >> it.r;
  95. 			it.l--;
  96. 			if (it.t == 1) {
  97. 				cin >> it.x;
  98. 			} else if (it.t == 2) {
  99. 				// do nothing
  100. 			} else assert(false);
  101. 			pts.push_back(it.l);
  102. 			pts.push_back(it.r);
  103. 		}
  104.  
  105. 		sort(pts.begin(), pts.end());
  106. 		pts.erase(unique(pts.begin(), pts.end()), pts.end());
  107.  
  108. 		int K = int(pts.size());
  109. 		assert(K > 1);
  110. 		vector<range_t> range; range.reserve(K-1);
  111. 		for (int i = 0; i+1 < K; i++) {
  112. 			range.push_back(range_t(pts[i], pts[i+1]));
  113. 		}
  114.  
  115. 		for (auto it : queries) {
  116. 			int l = int(lower_bound(pts.begin(), pts.end(), it.l) - pts.begin());
  117. 			int r = int(lower_bound(pts.begin(), pts.end(), it.r) - pts.begin());
  118. 			if (it.t == 1) {
  119. 				for (int i = l; i < r; i++) {
  120. 					range[i].add(it.x);
  121. 				}
  122. 			} else if (it.t == 2) {
  123. 				ll ans = INF;
  124. 				for (int i = l; i < r; i++) {
  125. 					setmin(ans, range[i].query());
  126. 				}
  127. 				cout << ans << '\n';
  128. 			} else assert(false);
  129. 		}
  130.  
  131. 		for (int i = 0; i+1 < K; i++) {
  132. 			range[i].finalize();
  133. 		}
  134. 	}
  135.  
  136. 	return 0;
  137. }
  138.  
Success #stdin #stdout 0s 4512KB
comments (?)
stdin
copy 
6 6
8 1
6 1
9 4
1 5
2 1
1 4
2 1 3
1 1 3 3
2 1 3
2 4 6
1 4 6 3
2 4 6
stdout
copy 
6
9
2
4
https://ideone.com/REiwCW
language:
C++14 (gcc 8.3)
created:
5 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!