Submission #1325990

#	Time	Username	Problem	Language	Result	Execution time	Memory
1325990		Aviansh	Fish 3 (JOI24_fish3)	C++20	0 / 100	498 ms	122904 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];
    map<int,int>mp;
    mp[-1]=-1;
    int pref[n];
    ans[0][0]=0;
    pref[0]=c[0];
    lef[0][0]=-1;
    mp[c[0]]=0;
    for(int i = 1;i<n;i++){
        auto it = mp.upper_bound(c[i]);
        --it;
        lef[i][0]=(*it).second;
        pref[i]=c[i];
        if(i){
            pref[i]+=pref[i-1];
        }
        int sum = 0;
        if(i){
            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;
        mp[c[i]]=i;
    }
    for(int i = 0;i<n;i++){
        fill(lef[i]+1,lef[i]+lg,-1);
        fill(ans[i]+1,ans[i]+lg,inf);
        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){
                //valid
                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];
        if(curr>=inf){
            cout << -1 << "\n";
        }
        else{
            cout << curr << "\n";
        }
    }
    return 0;
}

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