Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## Disjoint-Set Data Structure 266MS

Posted by __ea at 2016-10-31 05:20:59 on Problem 2559
```#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;

const double Pi=acos(-1.0);
typedef long long LL;

#define Set(a, s) memset(a, s, sizeof (a))
#define Rd(r) freopen(r, "r", stdin)
#define Wt(w) freopen(w, "w", stdout)

LL par[100001], s[100001];

int find(int x) { return x==par[x] ? x : par[x]=find(par[x]); }
void merge(int a, int b) { s[find(a)] += s[find(b)], par[find(b)] = find(a);}

LL N, h[100001], ref[100001];
bool comp(int a, int b) {
return h[a] > h[b];
}

int main ()
{
while(scanf("%lld", &N) && N) {
for (int i = 1; i <= N; i++)
scanf("%lld", &h[i]), ref[i]=i, s[i]=0;
sort(ref+1, ref+1+N, comp);

LL ans = 0;
for (int i = 1; i <= N; i++) {
s[ref[i]] = 1, par[ref[i]] = ref[i];
if (ref[i]<N && s[ref[i]+1]) merge(ref[i], ref[i]+1);
if (ref[i]>1 && s[ref[i]-1]) merge(ref[i], ref[i]-1);

ans = max(ans, s[par[ref[i]]] * h[ref[i]]);
}

printf("%lld\n", ans);
}
}

```

Followed by: