Kyselyt

#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>
//#include "stdlib_printing.hh"

using namespace std;
typedef long long LL;

void solve(vector<LL>& v, vector<LL>& S, vector<LL>& C, LL l, LL r){
    LL k = max_element(v.begin() + l, v.begin()+r+1) - v.begin();
    cout << S[l] - S[k] + v[k] * (r-k+1) - (C[r+1] - C[l]) << "\n";
}

int main(int argc, char** argv){
    LL n,q; cin >> n >> q;
    vector<LL> v(n);
    for(LL i = 0; i < n; i++) cin >> v[i];
    vector<LL> C(n+1); // C[i] = sum A[0..)
    for(LL i = 0; i < n; i++) C[i+1] = C[i] + v[i];

    vector<LL> S(n);
    vector<pair<LL, LL> > suf; // Value, run length
    LL sum = 0;
    for(LL i = n-1; i >= 0; i--){
        LL deleted = 0;
        while(suf.size() > 0 && v[i] > suf.back().first){
            sum -= suf.back().first * suf.back().second;
            deleted += suf.back().second;
            suf.pop_back();
        }
        suf.push_back({v[i], deleted+1});
        sum += (deleted+1)*v[i];
        S[i] = sum;
    }

    while(q--){
        LL l,r; cin >> l >> r; l--; r--;
        solve(v,S,C,l,r);
    }

}

Test 1

Group: 1, 2, 3

Verdict: ACCEPTED

Test 2

Group: 2, 3

Verdict: TIME LIMIT EXCEEDED

Test 3

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 4

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 5

Group: 3

Verdict: TIME LIMIT EXCEEDED