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. 	int getMin(int s, int e)
  20. 	{
  21. 		if(s==-1)
  22. 			return e;
  23. 		if(e==-1)
  24. 			return s;
  25. 		return (vec[s] < vec[e] ? s : e);
  26. 	}
  27.  
  28. 	void build(int s, int e, int node)
  29. 	{
  30. 		if(s==e)
  31. 			tree[node] = s;
  32. 		else
  33. 		{
  34. 			int m = s + (e-s>>1);
  35. 			build(s,m,node<<1);
  36. 			build(m+1,e,node<<1|1);
  37. 			tree[node] = getMin(tree[node<<1],tree[node<<1|1]);
  38. 		}
  39. 	}
  40.  
  41. 	long RMQ(int s, int e, int l, int r, int node)
  42. 	{
  43. 		if(s>e || s>r || e<l)
  44. 			return -1;
  45. 		if(s>=l && e<=r)
  46. 			return tree[node];
  47. 		else
  48. 		{
  49. 			int m = s + (e-s>>1);
  50. 			long lQuery = RMQ(s,m,l,r,node<<1);
  51. 			long rQuery = RMQ(m+1,e,l,r,node<<1|1);
  52. 			return getMin(lQuery,rQuery);
  53. 		}
  54. 	}
  55.  
  56. 	long query(int s, int e)
  57. 	{
  58. 		if(s>e)
  59. 			return -INF;
  60. 		if(s==e)
  61. 			return vec[s];
  62.  
  63. 		int m = RMQ(0,n-1,s,e,1);
  64. 		long lQuery = query(s,m-1);
  65. 		long rQuery = query(m+1,e);
  66. 		return max({lQuery, rQuery, (e-s+1) * vec[m]});
  67. 	}
  68.  
  69.  
  70. public:
  71. 	SegmentTree(const vector<long> &v)
  72. 	{
  73. 		this->vec = v;
  74. 		this->n = v.size();
  75. 		tree.resize(n<<2);
  76. 		build(0,n-1,1);
  77. 	}
  78.  
  79. 	long query()
  80. 	{
  81. 		return query(0,n-1);
  82. 	}
  83. };
  84.  
  85. int main()
  86. {
  87. 	fastIO;
  88. 	while(true)
  89. 	{
  90. 		int n; cin >> n;
  91. 		if(n==0)
  92. 			break;
  93. 		vector<long> h(n);
  94. 		for(int i=0;i<n;i++)
  95. 			cin >> h[i];
  96. 		SegmentTree st(h);
  97. 		cout << st.query() << endl;
  98. 	}
  99. 	return 0;
  100. }
  101.  
Success #stdin #stdout 0s 15264KB
comments (?)
stdin
copy 
7 2 1 4 5 1 3 3
4 1000 1000 1000 1000
0
stdout
copy 
8
4000
https://ideone.com/H6LYjx
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!