fork download
copy 
  1. #include <bits/stdc++.h> 
  2.  
  3. using namespace std;  
  4.  
  5. typedef long long ll;  
  6. typedef pair<int, int> ii;  
  7.  
  8. const int INF = 1e9;  
  9. const ll LINF = 1e18;  
  10.  
  11. const int N = 1e5 + 5; 
  12.  
  13. int n, q;
  14. ii h[N];  
  15.  
  16. struct PersistentSegTree {
  17. 	struct Data {
  18. 		int mx_seg = 0;  
  19. 		int mx_pref = 0, mx_suf = 0;  
  20. 		int len = 0; 
  21.  
  22. 		Data() {}
  23.  
  24. 		Data(int c) {
  25. 			len = 1; 
  26. 			if (c == 1) mx_seg = mx_pref = mx_suf = 1; 
  27. 		}
  28.  
  29. 		Data operator+(const Data& other) const {
  30. 			Data res;  
  31. 			res.mx_seg = max({mx_seg, other.mx_seg, mx_suf + other.mx_pref});
  32. 			res.mx_pref = mx_pref + (mx_pref == len ? other.mx_pref : 0);  
  33. 			res.mx_suf = other.mx_suf + (other.mx_suf == other.len ? mx_suf : 0);   
  34. 			res.len = len + other.len; 
  35. 			return res; 
  36. 		}
  37. 	}; 
  38.  
  39. 	struct Node {
  40. 		int l = 0, r = 0;  
  41. 		Data info; 
  42. 	}; 
  43.  
  44. 	int n;  
  45. 	vector<Node> seg; 
  46.  
  47. 	PersistentSegTree() {}
  48.  
  49. 	PersistentSegTree(int n) : n(n) {}
  50.  
  51. 	int build(int l, int r) {
  52. 		int cur = seg.size(); 
  53. 		seg.push_back(Node());    
  54. 		if (l == r) {
  55. 			seg[cur].info = Data(0); 
  56. 			return cur;  
  57. 		}
  58. 		int mid = (l + r) >> 1; 
  59. 		seg[cur].l = build(l, mid); 
  60. 		seg[cur].r = build(mid + 1, r);  
  61. 		int lc = seg[cur].l, rc = seg[cur].r;  
  62. 		seg[cur].info = seg[lc].info + seg[rc].info; 
  63. 		return cur; 
  64. 	}
  65.  
  66. 	int update(int pre, int l, int r, int pos) {
  67. 		int cur = seg.size();  
  68. 		seg.push_back(seg[pre]); 
  69. 		if (l == r) {
  70. 			seg[cur].info = Data(1); 
  71. 			return cur; 
  72. 		}
  73. 		int mid = (l + r) >> 1; 
  74. 		if (pos <= mid) {
  75. 			seg[cur].l = update(seg[pre].l, l, mid, pos); 
  76. 		}
  77. 		else {
  78. 			seg[cur].r = update(seg[pre].r, mid + 1, r, pos); 
  79. 		}
  80. 		int lc = seg[cur].l, rc = seg[cur].r;  
  81. 		seg[cur].info = seg[lc].info + seg[rc].info; 
  82. 		return cur; 
  83. 	}
  84.  
  85. 	Data get(int rt, int l, int r, int u, int v) {
  86. 		if (l > v || r < u) return Data();   
  87. 		if (u <= l && r <= v) return seg[rt].info;  
  88. 		int mid = (l + r) >> 1; 
  89. 		return get(seg[rt].l, l, mid, u, v) + get(seg[rt].r, mid + 1, r, u, v);
  90. 	}
  91.  
  92. 	int build() {
  93. 		return build(1, n); 
  94. 	}
  95.  
  96. 	int update(int pre, int pos) {
  97. 		return update(pre, 1, n, pos); 
  98. 	}
  99.  
  100. 	Data get(int rt, int u, int v) {
  101. 		return get(rt, 1, n, u, v); 
  102. 	}
  103. }; 
  104.  
  105. PersistentSegTree pst; 
  106. int root[N];  
  107.  
  108. bool check(int mid_h, int l, int r, int w) {
  109. 	int i = lower_bound(h + 1, h + n + 1, make_pair(mid_h, -INF)) - h;
  110. 	return (pst.get(root[i], l, r).mx_seg >= w);
  111. }
  112.  
  113. int main() {
  114. 	ios::sync_with_stdio(false); 
  115. 	cin.tie(nullptr); 	
  116. 	cin >> n; 
  117. 	for (int i = 1; i <= n; i++) {
  118. 		cin >> h[i].first;
  119. 		h[i].second = i; 
  120. 	} 
  121.  
  122. 	sort(h + 1, h + n + 1);  
  123.  
  124. 	pst = PersistentSegTree(n);
  125. 	pst.seg.reserve(18 * n);
  126. 	root[n + 1] = pst.build();  
  127. 	for (int i = n; i >= 1; i--) {
  128. 		root[i] = root[i + 1]; 
  129. 		root[i] = pst.update(root[i], h[i].second); 
  130. 	}	
  131.  
  132. 	cin >> q; 
  133. 	while (q--) {
  134. 		int l, r, w; 
  135. 		cin >> l >> r >> w; 
  136.  
  137. 		int lo = 1, hi = 1e9, ans = -1; 
  138. 		while (lo <= hi) {
  139. 			int mid_h = (lo + hi) >> 1;
  140. 			if (check(mid_h, l, r, w)) {
  141. 				ans = mid_h;     
  142. 				lo = mid_h + 1;   
  143. 			}
  144. 			else {
  145. 				hi = mid_h - 1; 
  146. 			}
  147. 		}
  148. 		cout << ans << '\n';
  149. 	}
  150. }
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
5
1 2 2 3 3
3
2 5 3
2 5 2
1 5 5
stdout
copy 
2
3
1
https://ideone.com/Egm2Bt
language:
C++14 (gcc 8.3)
created:
13 days ago
visibility:
secret

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!