Skip to content

Instantly share code, notes, and snippets.

@aalexand
Created January 16, 2014 07:43
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
Star You must be signed in to star a gist
Save aalexand/8451159 to your computer and use it in GitHub Desktop.
#include <cstdio>
#include <cassert>
#include <vector>
#include <utility>
#include <algorithm>
#include <climits>
using namespace std;
class Node {
public:
Node() : parent(this), rank(1), size(1) {
}
Node* Find() {
Node* ret = this;
while (ret->parent != ret) {
ret = ret->parent;
}
return ret;
}
int Size() const { return size; }
Node* Union(Node* rhs) {
Node* x = Find();
Node* y = rhs->Find();
if (x == y) return x;
Node* ret = 0;
if (x->rank < y->rank) {
x->parent = y;
y->size += x->size;
ret = y;
} else {
y->parent = x;
x->size += y->size;
ret = x;
}
if (x->rank == y->rank) {
x->rank++;
}
return ret;
}
private:
Node* parent;
int rank;
int size;
};
long long solve(const vector<long long>& in) {
int n = in.size();
vector<pair<long long, size_t> > data;
for (int i = 0; i < n; ++i) {
data.push_back(make_pair(in[i], i));
}
sort(data.begin(), data.end());
vector<bool> flag(n, false);
vector<Node> nodes(n);
long long max_area = 0;
for (int i = n-1; i >= 0; --i) {
long long h = data[i].first;
size_t pos = data[i].second;
if (pos > 0 && flag[pos-1]) {
nodes[pos].Union(&nodes[pos-1]);
}
if (pos < n-1 && flag[pos+1]) {
nodes[pos].Union(&nodes[pos+1]);
}
max_area = max(max_area, h * nodes[pos].Find()->Size());
flag[pos] = true;
}
return max_area;
}
long long solve_ref(const vector<long long>& in) {
int n = in.size();
long long max_area = 0;
for (int i = 0; i < n; ++i) {
long long min_h = INT_MAX;
for (int j = i; j < n; ++j) {
min_h = min(min_h, in[j]);
max_area = max(max_area, min_h * (j-i+1));
}
}
return max_area;
}
int main() {
for (;;) {
int n;
scanf("%d", &n);
if (n == 0) break;
vector<long long> input;
for (int i = 0; i < n; ++i) {
int h;
scanf("%d", &h);
input.push_back(h);
}
long long max_area = solve(input);
//long long max_area_ref = solve_ref(input);
//assert(max_area == max_area_ref);
printf("%lld\n", max_area);
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment