HISTOGRA - Rectangles on a histogram

[bulda_e_bien_]

Hello,

I am getting a TLE for this problem while using an O(n) solution. It computes the maximum rectangle area as it reads the heights. żIs there anything better? Perhaps reading the data and later aplying an O(log n) algorithm, like binary search or some wacky O(1) would do it, but I can't figure them out.

Thank you,

[fpavetic]

i got accepted with not quite optimized O(n) solution.

[Zuza_sof]

If you have a O( n ) algorithm, probably the bottlenect of your program will be the input reading because it's much slower then simply iterating through the points. Even if you have an O( n lg n ) algorithm, the reading can easily be the slowest part of your program. You probably didn't calculate the complexity right

[bulda_e_bien_]

Hello,

Thank you all. Zuza, you are right, I didn't calculate the complexity right. My algorithm was really O(n^2). Fpavetic, now I know that there is in fact an O(n) algorithm to solve this problem, I'll try to figure it out.

Thank you all again.

[abdallah_elguindy]

I am using an O(n lg n) solution and still get TLE? Should a solution with such complexity exceed the time limit?

NOTE: I am using scanf/printf I/O which I think should be fast..

[tushar_sof]

Update: I edited the code, but it still gives WA, Plz. help

[leppyr64]

Have you tried the maximum case.

[tushar_sof]

Edit: Got AC

[leppyr64]

What are the possible locations for the smallest inp within the largest rectangle?

[tushar_sof]

s.top().first > inp[i]
The lowest inp in largest rectangle is at its left end, isnt it?

[leppyr64]

The lowest inp in largest rectangle is at its left end, isnt it?

Is it?
6 2 1 1 1 1 1

[devil_888]

I am getting WA .
Please tell me the mistakes in my code:
#include <bits/stdc++.h>
using namespace std;
int main(){
long long int n;
long long int a[100005];
while (cin>>n && n!=0){

    for(int j=0;j<n;j++){
        cin>>a[j];
    }
     long long int i,area,m=0;
    stack< long long int > s;
    for( i=0;i<n;){
        long long int t=a[i];
        if(s.empty() || t>=a[s.top()] ){
            s.push(i++);
        }
        else{
           long long  int p=s.top();
            s.pop();
            if(s.empty()){
                area=a[p]*i;
            }
            else{
                area=a[p]*(i-s.top()-1);
            }

        }
        m=max(m,area);
    }
    while (!(s.empty())){
        long long  int q=s.top();
        s.pop();
        if(s.empty()) {
            area = a[q] *i;
        }
        else{
            area=a[q]*(i-s.top()-1);
        }
        m=max(m,area);
    }
    cout<<m<<endl;
}

return 0;

}