Cerinta completa

Coolguy gives you a simple problem. Given a -indexed array, , containing elements, what will be after this pseudocode is implemented and executed? Print .

//f(a, b) is a function that returns the minimum element in interval [a, b]

ans = 0

for a -> [1, n]
    for b -> [a, n]
        for c -> [b + 1, n]
            for d -> [c, n]
                ans = ans + min(f(a, b), f(c, d))

Input Format

The first line contains (the size of array ).
The second line contains space-separated integers describing .

Constraints

  • ≤ ≤
  • ≤ ≤

Note: is -indexed (i.e.: ).

Output Format

Print the integer result of .

Sample Input

3
3 2 1

Sample Output

6

Explanation





We then sum these numbers () and print , which is .

Limbajul de programare folosit: cpp14

Cod:

#include <cstdio>
#include <cstdlib>
#include <cassert>
#include <iostream>
#include <set>
#include <vector>
#include <cstring>
#include <string>
#include <algorithm>
#include <numeric>
#include <cmath>
#include <complex>
#include <map>
#include <queue>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<vi> vvi;
typedef vector<double> vd;
typedef pair<int, int> pii;
typedef pair<double, double> pdd;
typedef vector<pii> vii;
typedef vector<string> vs;
const int mod = 1000000007;

const int N = (1 << 17);
pii t[2*N];
const int INF = 2e9;

pii combine (const pii & a, const pii & b) {
  if (a.first < b.first)
    return a;
  if (b.first < a.first)
    return b;
  return make_pair (a.first, a.second + b.second);
}

void build (const vi & a, int v, int tl, int tr) {
  if (tl == tr) {
    t[v] = make_pair (a[tl], 1);
  } else {
    int tm = (tl + tr) / 2;
    build (a, v*2, tl, tm);
    build (a, v*2+1, tm+1, tr);
    t[v] = combine (t[v*2], t[v*2+1]);
  }
}

pii get_min (int v, int tl, int tr, int l, int r) {
  if (l > r)
    return make_pair (INF, 0);
  if (l == tl && r == tr)
    return t[v];
  int tm = (tl + tr) / 2;
  return combine (get_min (v*2, tl, tm, l, min(r,tm)),
                  get_min (v*2+1, tm+1, tr, max(l,tm+1), r));
}

void update (int v, int tl, int tr, int pos, int new_val) {
  if (tl == tr)
    t[v] = make_pair (new_val, 1);
  else {
    int tm = (tl + tr) / 2;
    if (pos <= tm)
      update (v*2, tl, tm, pos, new_val);
    else
      update (v*2+1, tm+1, tr, pos, new_val);
    t[v] = combine (t[v*2], t[v*2+1]);
  }
}

ll c2(ll x) {
  return x*(x-1)/2%mod;
}

int inv3 = (mod+1)/3;
ll c3(ll x) {
  return c2(x)*(x-2)%mod*inv3%mod;
}

int main() {
  int n;
  cin >> n;
  vi a(n);
  vii ts(n);
  for (int i = 0; i < n; ++i) {
    scanf("%d", &a[i]);
    ts[i] = pii(a[i], i);
  }
  sort(ts.begin(), ts.end());
/*  for (int i = 0; i < n; ++i) {
    a[ts[i].second] = i;
  }*/
  set<int> x;
  x.insert(-1);
  x.insert(n);
  ll sum = c2(n + 1), res = 0;
  for (int i = 0; i < n; ++i) {
    int pos = ts[i].second;
    auto it = x.lower_bound(pos);
    int r = *it; --it;
    int l = *it;
    sum = (sum - c2(r - l)) % mod;
    int l1 = pos - l, l2 = r - pos;
    ll cnt = (sum*l1%mod*l2 + l1*c3(l2+1) + l2*c3(l1+1)) % mod;
    res = (res + ts[i].first*cnt) % mod;
//    cerr << pos << ' ' << l1 << ' ' << l2 << ' ' << sum << ' ' << res << endl;
    x.insert(pos);
    sum = (sum + c2(l1) + c2(l2)) % mod;
  }
  cout << (res + mod) % mod << endl;
  return 0;
}

Scor obtinut: 1.0

Submission ID: 464653766

Link challenge: https://www.hackerrank.com/challenges/coolguy-and-two-subsequences/problem

Coolguy and Two Subsequences