1083 - Histogram

Problem Link : http://www.lightoj.com/volume_showproblem.php?problem=1083

Solution :

#include<bits/stdc++.h>

#define mx 100001

using namespace std;


int arr[mx];

struct Node
{
    int val;
    int index;
}  tree[mx*4];

vector<int>v;

void init(int node, int b,int e)
{
    int c,d;

    if(b==e)
    {
        c=tree[node].val=arr[b];
        d=tree[node].index=b;
        return;
    }

    int left=2*node;
    int right=(2*node )+1;

    int mid=(b+e)/2;

    init(left,b,mid);
    init(right,mid+1,e);


    if(tree[left].val<tree[right].val)
    {
        c=tree[node].val=tree[left].val;
        d=tree[node].index=tree[left].index;
    }
    else
    {
        c=tree[node].val=tree[right].val;
        d=tree[node].index=tree[right].index;
    }


}

Node query(int node,int b,int e,int i,int j)
{
    if(j<b || i>e)
    {

        Node temp;
        temp.val=9000000;
        temp.index=-1;
        return temp ;
    }

    if(b>=i && e<=j)
    {

        return tree[node];
    }

    int left=2*node;
    int right=(2*node)+1;
    int mid=(b+e)/2;

    Node p1=query(left,b,mid,i,j);
    Node p2=query(right,mid+1,e,i,j);

    if(p1.val<p2.val) return p1;
    else return p2;
}




int main()
{


    int t,n,q,l,r,ans,mn,L,R;
    scanf("%d",&t);
    Node temp;
    for(int ca=1; ca<=t; ca++)
    {


        scanf("%d",&n);

        for(int i=1; i<=n; i++) scanf("%d",&arr[i]);


        init(1,1,n);

        temp=query(1,1,n,1,n);
        ans=temp.val;
        mn=ans;
        ans=n*ans;

        int mid=temp.index;

        l=1;
        r=mid-1;
        L=mid+1;
        R=n;

        if(l<=r)
        {
            v.push_back(l);
            v.push_back(r);
        }
        if(L<=R)
        {
            v.push_back(L);
            v.push_back(R);
        }


        while(v.size())
        {

            temp=query(1,1,n,v[0],v[1]);
            mn=(v[1]-v[0]+1)*temp.val;
            ans=max(mn,ans);
            mid=temp.index;
            l=v[0];
            r=mid-1;
            L=mid+1;
            R=v[1];

            if(l<=r)
            {
                v.push_back(l);
                v.push_back(r);
            }
            if(L<=R)
            {
                v.push_back(L);
                v.push_back(R);
            }

            v.erase(v.begin()+0);
            v.erase(v.begin()+0);
        }




        printf("Case %d: %d\n",ca,ans);
        v.clear();

    }

}