fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int buildTree(int v,int* segmentTree,int* a,int l,int r)
  4. {
  5. 	if(l>r)
  6. 		return -150007;
  7. 	if(l == r)
  8. 	{	
  9. 	//	cout<<"l==r :"<<l<<endl;
  10. 	//	cout<<"segmentTree[v] : "<<segmentTree[v]<<"a[l] : "<<a[l]<<endl;
  11. 		segmentTree[v]=a[l];
  12. 		return a[l] ;
  13. 	}
  14. 	int mid = (l+r)/2;
  15. 	int left = buildTree(2*v,segmentTree,a,l,mid);
  16. 	int right = buildTree(2*v+1,segmentTree,a,mid+1,r);
  17. 	segmentTree[v] = max(left,right);
  18.  
  19. }
  20. int maxInRange(int v,int* segmentTree,int l,int r,int lg,int rg)
  21. {
  22. 	if(l>r || lg > rg)
  23. 		return -150007 ;// min val
  24. 	if(l == lg && r==rg)
  25. 	{
  26. 		return segmentTree[v];
  27. 	}
  28. 	int mid = (l+r)/2;
  29.  
  30. 	int left = maxInRange(2*v,segmentTree,l,mid,lg,min(mid,rg));
  31. 	int right = maxInRange(2*v+1,segmentTree,mid+1,r,max(mid+1,lg),rg);
  32. 	//cout<<"left : "<<left<<"right : "<<right<<endl;
  33. 	return max(left,right);
  34. }
  35. int main()
  36. {
  37. 	int n;
  38. 	cin>>n;
  39. 	int a[n+50];
  40. 	for(int i=1;i<=n;i++)
  41. 		cin>>a[i];
  42. 	int m;
  43. 	cin>>m;
  44. 	int segmentTree[4*n+50]={0};
  45. 	// build segment tree
  46. 	// for(int i=1;i<=4*n;i++)
  47. 	// 	cout<<segmentTree[i]<<" ";
  48. 	// cout<<endl;
  49. 	buildTree(1,segmentTree,a,1,n);
  50. 	// for(int i=1;i<=4*n;i++)
  51. 	// 	cout<<segmentTree[i]<<" ";
  52. 	// cout<<endl;
  53. 	while(m--)
  54. 	{
  55. 		int l,r;
  56. 		cin>>l>>r;
  57. 		cout<<maxInRange(1,segmentTree,1,n,l,r)<<endl;
  58. 	}
  59. 	return 0;
  60. }
Runtime error #stdin #stdout 0s 5596KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/Ne2UYo
problem GSS1, based on SPOJ submission 27800858 (CPP14), 2021-04-28 21:40:31
language:
C++14 (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!