fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. typedef pair<int,int> iPair;
  5. typedef vector<int> iVector;
  6. typedef vector<iVector> iMatrix;
  7. #define MOD 1000000007
  8. #define INF 1e18
  9. #define long long long
  10. #define endl ('\n')
  11. #define fill(ar,val) memset(ar,val,sizeof(ar))
  12. #define fastIO ios::sync_with_stdio(false); cin.tie(0)
  13.  
  14. class SegmentTree
  15. {
  16. 	int n;
  17. 	vector<long> vec, tree;
  18.  
  19. 	void build(int s, int e, int node)
  20. 	{
  21. 		if(s==e)
  22. 			tree[node] = vec[s];
  23. 		else
  24. 		{
  25. 			int m = s + (e-s>>1);
  26. 			int l = node<<1, r = l|1;
  27. 			build(s,m,l);
  28. 			build(m+1,e,r);
  29. 			tree[node] = min(tree[l],tree[r]);
  30. 		}
  31. 	}
  32.  
  33. 	long RMQ(int s, int e, int l, int r, int node)
  34. 	{
  35. 		if(s>e || s>r || e<l)
  36. 			return INF;
  37. 		if(s>=l && e<=r)
  38. 			return tree[node];
  39. 		else
  40. 		{
  41. 			int m = s + (e-s>>1);
  42. 			long lQuery = RMQ(s,m,l,r,node<<1);
  43. 			long rQuery = RMQ(m+1,e,l,r,node<<1|1);
  44. 			return min(lQuery,rQuery);
  45. 		}
  46. 	}
  47.  
  48. 	long query(int s, int e)
  49. 	{
  50. 		if(s>e)
  51. 			return -INF;
  52. 		if(s==e)
  53. 			return vec[s];
  54.  
  55. 		int m = s + (e-s>>1);
  56. 		long lQuery = query(s,m);
  57. 		long rQuery = query(m+1,e);
  58. 		long minimum = RMQ(0,n-1,s,e,1);
  59. 		return max({lQuery, rQuery, (e-s+1) * minimum});
  60. 	}
  61.  
  62.  
  63. public:
  64. 	SegmentTree(const vector<long> &v)
  65. 	{
  66. 		this->vec = v;
  67. 		this->n = v.size();
  68. 		tree.resize(n<<2);
  69. 		build(0,n-1,1);
  70. 	}
  71.  
  72. 	long query()
  73. 	{
  74. 		return query(0,n-1);
  75. 	}
  76. };
  77.  
  78. int main()
  79. {
  80. 	fastIO;
  81. 	while(true)
  82. 	{
  83. 		int n; cin >> n;
  84. 		if(n==0)
  85. 			break;
  86. 		vector<long> h(n);
  87. 		for(int i=0;i<n;i++)
  88. 			cin >> h[i];
  89. 		SegmentTree st(h);
  90. 		cout << st.query() << endl;
  91. 	}
  92. 	return 0;
  93. }
  94.  
Success #stdin #stdout 0s 16080KB
comments (?)
stdin
copy 
7 2 1 4 5 1 3 3
4 1000 1000 1000 1000
0
stdout
copy 
8
4000
https://ideone.com/VDtOML
problem HISTOGRA, based on SPOJ submission 18981091 (CPP14), 2017-03-15 18:25:12
language:
C++14 (gcc 8.3)
created:
7 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!