Subsegments of an array 2

[Kalcor]

I succeeded in coding such thing in a basic way but it runs into a time limit error because the time limit is only 2 seconds on the system, I tried it in 2 ways and both of them gave me TLE, I'll list one of my ways which I find the most efficient between the 2 ways but it still gave a TLE, and idk how to solve that problem in <= 2seconds, anyway here it is:

int a[1000000], l[1000000], r[1000000];
int main(void) {
    int i, j, n;
    scanf("%d",&n);
    for(i = 0; i < n; i++) scanf("%d",&a[i]);
    ll ans = 0;
    for(j = 0; j < 2; j++) {
        vector<pair<int,int>> v;
        v.push_back({-1,INF});
        for(i = 0; i < n; i++)  {
            while (v.back().second <= a[i]) v.pop_back();
            l[i] = v.back().first;
            v.push_back({i,a[i]});
        }
        v.clear();
        v.push_back({n,INF});
        for(i = n-1; i >= 0; i--)  {
            while (v.back().second < a[i]) v.pop_back();
            r[i] = v.back().first;
            v.push_back({i,a[i]});
        }
        for(i = 0; i < n; i++)  ans += (ll) a[i] * (i-l[i]) * (r[i]-i);
        for(i = 0; i < n; i++)  a[i] *= -1;
    }
    cout << ans;
}

Thanks

[lastchance]

Very roughly, I think that what is happening in the model answer is the following.

Imbalance =   SUM(over all segments) ( alargest - asmallest )

          =   SUM(over i) ai x (number of segments for which ai is largest)
            - SUM(over i) ai x (number of segments for which ai is smallest)

          =   SUM(over i) ai x (number of segments for which ai is largest)
            + SUM(over i) (-ai) x (number of segments for which (-ai) is largest)

You will notice that there are precisely two passes (line 7) and that on the second pass a_i becomes -a_i (line 23).
So, I think that each pass is doing one of those last two sums.

v is used as a stack. It is used to establish l[i] (the index of the nearest element to the left which is strictly bigger than a_i) and then r[i] (the index of the nearest element to the right which is greater than or equal). So, in the sums, a_i will the largest for all the segments which lie within
l[i]+1 ... i ... r[i]-1
and include i. This quite neatly includes the two special cases at the ends of the domain (lines 9 and 16), which always remain on the stack. To do the sums you simply need to count the segments satisfying this condition. Segments ending at i are
l[i]+1 to i, l[i]+2 to i, ... , i to i - there are i - l[i] of these;
Segments ending at i+1 (and including i) are
l[i]+1 to i, l[i]+2 to i, ... , i to i+1 - there are also i - l[i] of these;
All the way up to segments ending at r[i] - 1:
l[i]+1 to i, l[i]+2 to i, ... , i to r[i]-1 - there are still i - l[i] of these;
In total, there are r[i] - i groups of i - l[i], so a total of
(i-l[i]) * (r[i]-i)
segments. Once multiplied by a_i this tally can be accumulated as in line 22 to form the sums that I have highlighted.

There is one subtle nuance that I haven't addressed (and I really don't want to slog through it). If there are repeated values then the segments for which "a[i] is the largest value" aren't well defined, and you would have to agree to take either the leftmost or rightmost as highest value. I'm afraid that I will have to leave you to follow this through the conditions of < or <= on lines 11 and 18.

[Kalcor]

Thanks alot buddy ! <3