fork download
copy 
  1. #include<iostream>
  2. #include<cmath>
  3. #include<climits>
  4. #include<cstring>
  5. using namespace std;
  6. int a[500001],segTree[500001];
  7. void constructSegTree(int l, int r, int pos)
  8. {
  9.  
  10. 	if(l == r) {
  11. 		segTree[pos] = a[l];
  12. 		return;
  13. 	}
  14. 	int mid = (l+r)>>1;
  15. 	int child = (pos<<1)+1;
  16. 	constructSegTree(l,mid,child);
  17. 	constructSegTree(mid+1,r,child+1);
  18. 	segTree[pos] = min(segTree[child],segTree[child+1]);
  19. }
  20. int rmq(int l, int r, int pos, int qL, int qH)
  21. {
  22. 	if(l>r) return INT_MAX;
  23. 	else if(l>=qL && r<=qH)
  24. 		return segTree[pos];
  25. 	else if(qL > r || qH < l)
  26. 		return INT_MAX;
  27. 	int mid = (l+r)>>1;
  28. 	int child = (pos<<1)+1;
  29.     return min(rmq(l,mid,child,qL,qH),rmq(mid+1,r,child+1,qL,qH));
  30.  // else return min(rmq(l,(l+r)/2,((pos*2)+1),qL,qH),rmq(((l+r)/2)+1,r,(pos*2)+2,qL,qH));
  31. }
  32. int main()
  33. {
  34. 	int t;
  35. 	scanf("%d",&t);
  36. 	int i = 0;
  37. 	memset(segTree,INT_MAX,sizeof(segTree));
  38. 	while(t--)
  39. 	{
  40. 	i++;
  41. 	int n, q;
  42. 	scanf("%d%d",&n,&q);
  43. 	for(int i=0;i<n;i++)
  44. 		scanf("%d",&a[i]);
  45. 	constructSegTree(0,n-1,0);
  46. 	printf("Scenario #%d:\n",i);
  47. 	while(q--)
  48. 	{
  49. 		int l,r;
  50. 		cin >> l >> r;
  51. 		l--;
  52. 		r--;
  53. 		printf("%d\n",rmq(0,n-1,0,l,r) );
  54. 	}
  55. }
  56. 	return 0;
  57. }
Success #stdin #stdout 0s 5480KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/bWfcCI
problem RPLN, based on SPOJ submission 27318377 (CPP), 2021-01-22 05:35:42
language:
C++ (gcc 8.3)
created:
3 years 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!