Kyselyt

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

ll x[202020], r[606060], s[202020], p[202020], t[202020][20][3];

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    //Älä käytä, jos tehtävä on interaktiivinen!
    int n, q;
    cin >> n >> q;
    ll M=1;
    while (M<=(n+2)) M*=2;
    for (int i=1; i<=n; ++i){
        ll a;
        cin >> a;
        x[i]=a;
        r[i+M-1]=a;
        s[i] = s[i-1] + x[i];
    }
    x[n+1]=1e9+1;
    r[n+M]=1e9+1;
    for (int i=M; i>=1; --i){
        r[i]=max(r[i*2], r[i*2+1]);
    }
    ll a=n, b=1e9;
    for (int i=n; i>=1; --i){
        if (x[i]>b){
            a=i;
        }
        b=x[i];
        p[i]=a;
    }
    t[n+1][0][1]=n+2;
    t[n+1][0][2]=0;
    for (int i=n; i>=1; --i){
        if (x[i]>x[i+1]){
            ll a=i+M-1;
            while (r[a]<=x[i]){
                if (a%2==1) a++;
                a/=2;
            }
            while (a<=M){
                if (r[a*2]>x[i]){
                    a*=2;
                }
                else a = a*2+1;
            }
            a = a-M+1;
            t[i][0][1]=a;
            t[i][0][2]=(a-i)*x[i] - (s[a-1] - s[i-1]);
        }
        else{
            t[i][0][1]=t[i+1][0][1];
            t[i][0][2]=t[i+1][0][2];
        }
        for (int j=1; j<=19; ++j){
            ll b=t[i][j-1][1];
            if (b==(n+2)){
                t[i][j][1]=n+2;
                t[i][j][2]=t[i][j-1][2];
            }
            else{
                t[i][j][1]=t[b][j-1][1];
                t[i][j][2]=t[i][j-1][2] + t[b][j-1][2];
            }
        }
    }
    /*
    for (int i=1; i<=n; ++i){
        for (int j=0; j<=4; ++j){
            cout << t[i][j][1] << " " << t[i][j][2] << "  ";
        }
        cout << "\n";
    }
    */
    for (int i=1; i<=q; ++i){
        ll a, b;
        cin >> a >> b;
        ll ans=0;
        ll c=0;
        while (t[a][c][1]<=b) c++;
        while (c>=0){
            if (t[a][c][1]<=b){
                ans+=t[a][c][2];
                a = t[a][c][1];
            }
            c--;
        }
        if (p[a]<b){
            ans+=(b-p[a])*x[p[a]] - (s[b] - s[p[a]]);
        }
        cout << ans << "\n";
    }
}

Test 1

Group: 1, 2, 3

Verdict: WRONG ANSWER

Test 2

Group: 2, 3

Verdict: WRONG ANSWER

Test 3

Group: 3

Verdict: WRONG ANSWER

Test 4

Group: 3

Verdict: ACCEPTED

Test 5

Group: 3

Verdict: ACCEPTED