Submission #905790

---

Source Code Expand

#include<bits/stdc++.h>

using namespace std;

typedef long long int64;

struct UnionFind
{
  vector< int > data;

  UnionFind(int sz)
  {
    data.assign(sz, -1);
  }

  void unite(int x, int y)
  {
    x = find(x), y = find(y);
    if(x != y) {
      if(data[x] > data[y]) swap(x, y);
      data[x] += data[y];
      data[y] = x;
    }
  }

  int find(int k)
  {
    if(data[k] < 0) return (k);
    return (data[k] = find(data[k]));
  }

  int size(int k)
  {
    return (-data[find(k)]);
  }
};

int main()
{
  int N, A[200000];

  cin >> N;
  for(int i = 0; i < N; ++i) {
    cin >> A[i];
  }

  vector< int > idx(N);
  iota(begin(idx), end(idx), 0);
  sort(begin(idx), end(idx), [&](int a, int b)
  {
    return (A[a] > A[b]);
  });

  int64 ret = 0;
  UnionFind tree(N);
  for(int& i : idx) {
    int Left = 1, Right = 1;
    if(i > 0 && A[i] < A[i - 1]) {
      Left += tree.size(i - 1);
      tree.unite(i - 1, i);
    }
    if(i + 1 < N && A[i] < A[i + 1]) {
      Right += tree.size(i + 1);
      tree.unite(i + 1, i);
    }
    ret += 1LL * A[i] * Left * Right;
  }
  cout << ret << endl;
}

Submission Info

Judge Result