#include<bits/stdc++.h>
using namespace std;
vector<int64_t>tree;
int64_t func(int64_t a,int64_t b){
return min(a,b);
}
void build(int& n ,vector<int64_t>&arr){
while(__builtin_popcount(n)!=1){
++n;
arr.push_back(0);
}
tree.resize(2*n);
for (int i = 0;i<n;++i){
tree[n+i]=arr[i];
}
for (int i =n-1;i>=1;--i){
tree[i]=func(tree[2*i],tree[2*i+1]);
}
}
int64_t rangesum(int node,int low_node,int high_node,int qlow,int qhigh){
if (qlow<=low_node&&high_node<=qhigh)return tree[node];
if (high_node<qlow||qhigh<low_node){
return INT_MAX;
}
int mid = (low_node+high_node)/2;
return func(rangesum(2*node,low_node,mid,qlow,qhigh),rangesum(2*node + 1,mid+1,high_node,qlow,qhigh));
}
void update(int i , int v,int n){
tree[n+i]=v;
for (int j = (n+i)/2;j>=1;j/=2){
tree[j]=func(tree[j*2],tree[j*2 + 1]);
}
}
int64_t getMaxArea(vector<int64_t>hist, int n,vector<int64_t>l)
{
stack<int64_t> s;
int64_t max_area = 0;
int64_t tp;
int64_t area_with_top;
int64_t maxxy=INT_MAX;
int i = 0;
while (i < n)
{
if (s.empty() || hist[s.top()] <= hist[i]){
s.push(i++);
}
else
{
tp = s.top();
s.pop();
// cout<<hist[tp]<<" ";
//cout<<(s.empty() ? 0 : (i - s.top() - 1))<<" "<< (s.empty() ? rangesum(1,0,l.size()-1,0,i-1) : rangesum(1,0,l.size()-1,s.top(),i-1))<<endl;
area_with_top = hist[tp] * (s.empty() ? i*rangesum(1,0,l.size()-1,0,i-1) :
(i - s.top() - 1)*rangesum(1,0,l.size()-1,s.top(),i-1));
if (max_area < area_with_top)
max_area = area_with_top;
}
}
while (s.empty() == false)
{
tp = s.top();
s.pop();
area_with_top = hist[tp] * (s.empty() ? i*rangesum(1,0,l.size()-1,0,i-1):
(i - s.top() - 1)*rangesum(1,0,l.size()-1,s.top(),i-1));
if (max_area < area_with_top)
max_area = area_with_top;
}
return max_area;
}
int main()
{
int n;cin>>n;
vector<int64_t>h(n),l(n);
for(int i =0;i<n;++i){
cin>>h[i]>>l[i];
}
vector<int64_t>arr=l;
int k=n;
build(k,arr);
int64_t maxxy=getMaxArea(h,n,arr);
arr=h;
k=n;
build(k,arr);
maxxy=max(getMaxArea(l,n,arr),maxxy);
cout<<maxxy;
return 0;}
Compilation message
histogram.cpp: In function 'int64_t getMaxArea(std::vector<long int>, int, std::vector<long int>)':
histogram.cpp:51:14: warning: unused variable 'maxxy' [-Wunused-variable]
51 | int64_t maxxy=INT_MAX;
| ^~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
