Cerinta completa

Transforming data into some other data is typical of a programming job. This problem is about a particular kind of transformation which we’ll call the max transform.

Let be a zero-indexed array of integers. For , let denote the subarray of from index to index , inclusive.

Let’s define the max transform of as the array obtained by the following procedure:

  • Let be a list, initially empty.
  • For from to :
    • For from to :
      • Let .
      • Append to the end of .
  • Return .

The returned array is defined as the max transform of . We denote it by .

Complete the function solve that takes an integer array as input.

Given an array , find the sum of the elements of , i.e., the max transform of the max transform of . Since the answer may be very large, only find it modulo .

Input Format

The first line of input contains a single integer denoting the length of .

The second line contains space-separated integers denoting the elements of .

Constraints

Subtasks

  • For of the total score,

Output Format

Print a single line containing a single integer denoting the answer.

Sample Input 0

3
3 2 1

Sample Output 0

58

Explanation 0

In the sample case, we have:

Therefore, the sum of the elements of is .

Limbajul de programare folosit: cpp14

Cod:

#include <cstdio>
#include <iostream>
#include <sstream>
#include <deque>
#include <queue>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
#include <map>
#include <set>
#include <string>
#include <cstdlib>
#include <ctime>
using namespace std; 

#define P 1000000007
#define N 1100000

int used[N], fa[N], sum[N], f[N], now, ans, T, cc;
vector <int> V[N];
int n;
int a[N];

int gf(int x) {
    if (fa[x] != x)
        fa[x] = gf(fa[x]);
    return fa[x];
}

void merge(int x, int y) {
    x = gf(x);
    y = gf(y);
    sum[x] += sum[y];
    fa[y] = x;
}

void add(int x) {
    used[x] = 1;
    sum[x] = 1;
    if (used[x - 1]) {
        now = (now - f[sum[gf(x - 1)]] + P) % P;
        merge(x, x - 1);
    }
    if (used[x + 1]) {
        now = (now - f[sum[gf(x + 1)]] + P) % P;
        merge(x, x + 1);
    }
    now = (now + f[sum[gf(x)]]) % P;
    int L = sum[gf(1)], R = sum[gf(n)];
    // printf("?? %d %d %dn", x, L, R);
    x = min(R, L - 1);
    if (x <= 0) {
        cc = now;
        return ;
    }
    cc = now;
    // printf("?? %d %dn", cc, x);
    cc = (cc + 1LL * x * L * (R + 1)) % P;
    cc = (cc - 1LL * x * (x + 1) / 2 % P * (L + R + 1)) % P;
    cc = (cc + 1LL * x * (x + 1) * (2 * x + 1) / 6) % P;
    cc = (cc + P) % P;
    // printf("! %dn", cc);
    return ;
}

int main() {
    scanf("%d", &n);
    int ma = 0;
    for (int i = 1; i <= n; i++)
        scanf("%d", &a[i]), V[a[i]].push_back(i), ma = max(ma, a[i]);
    T = 1LL * n * (n + 1) / 2 % P;
    T = 1LL * T * (T + 1) / 2 % P;
    for (int i = 1; i <= n; i++)
        f[i] = (1LL * i * (i + 1) * (2 * i + 1) / 6 + 1LL * i * (i + 1) / 2) / 2 % P;
    for (int i = 1; i <= n; i++)
        fa[i] = i;
    now = 0;

    for (int i = 0; i < ma; i++) {
        for (int j = 0; j < (int) V[i].size(); j++)
            add(V[i][j]);
        ans = (ans + T - cc) % P;
    }
    ans = (ans + P) % P;
    printf("%d\n", ans);

}

Scor obtinut: 1.0

Submission ID: 464654117

Link challenge: https://www.hackerrank.com/challenges/max-transform/problem

Max Transform