fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. template <typename T> T& setmin(T& a, T b) { if (b < a) a = b; return a; }
  5.  
  6. const int INF = 1e9;
  7.  
  8. const int MAXN = 1.1e5;
  9. const int MAXQ = 3.1e5;
  10.  
  11. struct seg_node {
  12. 	vector<int> vals;
  13. 	int minDiff;
  14. } seg[1<<18];
  15.  
  16. int A[MAXN];
  17.  
  18. void build(int i, int l, int r) {
  19. 	seg[i].vals.reserve(r-l);
  20. 	if (l+1 == r) {
  21. 		seg[i].vals.push_back(A[l]);
  22. 	} else {
  23. 		int m = (l+r)/2;
  24. 		build(2*i, l, m);
  25. 		build(2*i+1, m, r);
  26. 		merge(seg[2*i].vals.begin(), seg[2*i].vals.end(), 
  27. 				seg[2*i+1].vals.begin(), seg[2*i+1].vals.end(), back_inserter(seg[i].vals));
  28. 	}
  29. 	assert(r-l == int(seg[i].vals.size()));
  30. 	assert(is_sorted(seg[i].vals.begin(), seg[i].vals.end()));
  31. 	seg[i].minDiff = INF;
  32. 	for (int z = 0; z+1 < int(seg[i].vals.size()); z++) {
  33. 		setmin(seg[i].minDiff, seg[i].vals[z+1] - seg[i].vals[z]);
  34. 	}
  35. }
  36.  
  37. int query(int i, int l, int r, int ql, int qr) {
  38. 	if (qr <= l || r <= ql) {
  39. 		return INF;
  40. 	} else if (ql <= l && r <= qr) {
  41. 		return seg[i].minDiff;
  42. 	} else {
  43. 		int m = (l+r)/2;
  44. 		return min(query(2*i, l, m, ql, qr), query(2*i+1, m, r, ql, qr));
  45. 	}
  46. }
  47.  
  48. void update(int i, int l, int r, int qr, int v, int& d) {
  49. 	if (qr <= l) return;
  50. 	if (l+1 == r) {
  51. 		setmin(seg[i].minDiff, abs(A[l]-v));
  52. 		setmin(d, abs(A[l]-v));
  53. 	} else {
  54. 		auto it = lower_bound(seg[i].vals.begin(), seg[i].vals.end(), v);
  55. 		// doesn't optimize
  56. 		if ((it == seg[i].vals.end() || v+d <= *it) && 
  57. 				(it == seg[i].vals.begin() || *prev(it) <= v-d)) {
  58. 			return;
  59. 		}
  60. 		int m = (l+r)/2;
  61. 		update(2*i+1, m, r, qr, v, d);
  62. 		update(2*i, l, m, qr, v, d);
  63. 		setmin(seg[i].minDiff, min(seg[2*i].minDiff, seg[2*i+1].minDiff));
  64. 	}
  65. }
  66.  
  67. int ans[MAXQ];
  68.  
  69. int main() {
  70. 	ios::sync_with_stdio(0), cin.tie(0);
  71. 	int N; cin >> N;
  72. 	for (int i = 0; i < N; i++) cin >> A[i];
  73.  
  74. 	int Q; cin >> Q;
  75. 	vector<vector<pair<int, int>>> queries(N);
  76. 	for (int q = 0; q < Q; q++) {
  77. 		int l, r; cin >> l >> r; l--, r--;
  78. 		assert(r >= 1);
  79. 		queries[r].emplace_back(l, q);
  80. 	}
  81.  
  82. 	build(1, 0, N);
  83. 	for (int i = 1; i < N; i++) {
  84. 		int tmp = INF;
  85. 		update(1, 0, N, i, A[i], tmp);
  86. 		for (auto it : queries[i]) {
  87. 			int l = it.first;
  88. 			int q = it.second;
  89. 			ans[q] = query(1, 0, N, l, i+1);
  90. 		}
  91. 	}
  92.  
  93. 	for (int q = 0; q < Q; q++) { cout << ans[q] << '\n'; }
  94.  
  95. 	return 0;
  96. }
  97.  
Success #stdin #stdout 0s 11760KB
comments (?)
stdin
copy 
8
3 1 4 1 5 9 2 6
4
1 8
1 3
4 8
5 7
stdout
copy 
0
1
1
3
https://ideone.com/iG5Upp
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!