Submission #1326008

#	Time	Username	Problem	Language	Result	Execution time	Memory
1326008		Aviansh	Fish 3 (JOI24_fish3)	C++20	28 / 100	518 ms	104384 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#define int long long

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n,d;
    cin >> n >> d;
    assert(d==1);
    int c[n];
    for(int &i : c){
        cin >> i;
    }
    const int lg = 20;
    const int inf = 1e18;
    int lef[n][lg];
    int ans[n][lg];
    int pref[n];
    ans[0][0]=0;
    pref[0]=c[0];
    lef[0][0]=-1;
    vector<int>v;
    v.push_back(-1);
    v.push_back(0);
    for(int i = 1;i<n;i++){
        while(v.size()>1&&c[v.back()]>c[i]){
            v.pop_back();
        }
        lef[i][0]=v.back();
        v.push_back(i);
        pref[i]=c[i];
        if(i){
            pref[i]+=pref[i-1];
        }
        int sum=pref[i-1];
        if(lef[i][0]>=0)
            sum-=pref[lef[i][0]];
        sum-=(i-lef[i][0]-1)*c[i];
        ans[i][0]=sum;
    }
    for(int i = 0;i<n;i++){
        fill(lef[i]+1,lef[i]+lg,-1);
        fill(ans[i]+1,ans[i]+lg,0);
        for(int j = 1;j<lg;j++){
            if(lef[i][j-1]<0)
                break;
            lef[i][j]=lef[lef[i][j-1]][j-1];
            ans[i][j]=ans[i][j-1]+ans[lef[i][j-1]][j-1];
        }
    }
    int q;
    cin >> q;
    while(q--){
        int l,r;
        cin >> l >> r;
        l--;r--;
        int curr = 0;
        for(int i = lg-1;i>=0;i--){
            if(lef[r][i]>=l){
                curr+=ans[r][i];
                r=lef[r][i];
            }
        }
        assert(lef[r][0]<l);
        curr+=pref[r];
        if(l){
            curr-=pref[l-1];
        }
        curr-=(r-l+1)*c[r];
        cout << curr << "\n";
    }
    return 0;
}

• Subtask 1: 0 / 9
• Subtask 2: 0 / 7
• Subtask 3: 28 / 28
• Subtask 4: 0 / 20
• Subtask 5: 0 / 36