Submission #447861

#	Time	Username	Problem	Language	Result	Execution time	Memory
447861		Apiram	3D Histogram (COCI20_histogram)	C++14	0 / 110	2 ms	332 KiB

histogram

#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 (stderr)

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;
      |              ^~~~~

• Subtask 1: 0 / 20
• Subtask 2: 0 / 90