fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. const int N = 50001;
  4. int inter[2][N], arr[N];
  5. int n, q, l, r;
  6. int ls(int indx) {
  7. 	return indx & (-indx);
  8. }
  9. void update(int indx, int val) {
  10. 	int mx = val, mn = val;
  11. 	for (; indx <= n; indx += ls(indx)) {
  12. 		inter[1][indx] = mx = max(mx, inter[1][indx]);
  13. 		inter[0][indx] = mn = min(mn, inter[0][indx]);
  14. 	}
  15. }
  16. int get(int l, int r) {
  17. 	int mx = 0, mn = 1e9;
  18. 	while (r >= l) {
  19. 		while (r - ls(r) < l && r >= l) {
  20. 			mx = max(mx, arr[r]);
  21. 			mn = min(mn, arr[r]);
  22. 			--r;
  23. 		}
  24. 		if (r >= l)
  25. 			mx = max(mx, inter[1][r]), mn = min(mn, inter[0][r]);
  26. 		r -= ls(r);
  27. 	}
  28. 	return mx - mn;
  29. }
  30. int main() {
  31. #ifndef ONLINE_JUDGE
  32. 	freopen("a.in", "r", stdin);
  33. #endif
  34. 	scanf("%d %d", &n, &q);
  35. 	memset(inter[0], 127, sizeof(int) * (n + 1));
  36. 	for (int i = 1; i <= n; ++i)
  37. 		scanf("%d", &arr[i]), update(i, arr[i]);
  38. 	while (q--) {
  39. 		scanf("%d %d", &l, &r);
  40. 		if (l == r) {
  41. 			puts("0");
  42. 			continue;
  43. 		}
  44. 		printf("%d\n", get(l, r));
  45. 	}
  46. 	return 0;
  47. }
  48.  
Success #stdin #stdout 0s 3724KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/o6KSNS
language:
C++ (gcc 8.3)
created:
8 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!