Submission #1325972

#	Time	Username	Problem	Language	Result	Execution time	Memory
1325972		Aviansh	Fish 3 (JOI24_fish3)	C++20	0 / 100	2095 ms	100508 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;
    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 las = 0;
    int pref[n];
    ans[0][0]=0;
    pref[0]=c[0];
    lef[0][0]=-1;
    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];
        }
        if(las<=(*it).second+1){
            int sum = 0;
            if(i){
                sum=pref[i-1];
            }
            if((*it).second>=0)
                sum-=pref[(*it).second];
            int req = c[las]%d;
            if(req>c[i]){
                ans[i][0]=inf;
            }
            else{
                req=((c[i]-req)/d)*d+req;
                sum-=(i-(*it).second-1)*req;
                assert(sum%d==0);
                ans[i][0]=sum/d;
            }
        }
        else{
            ans[i][0]=inf;
        }
        if(c[las]%d!=c[i]%d){
            las=i;
        }
        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);
        int m = c[r-1]%d;
        for(int i = r-1;i>=l;i--){
            if(c[i]%d!=m){
                curr=inf;
                break;
            }
            if(m>c[r]){
                curr=inf;
                break;
            }
            int req=((c[r]-m)/d)*d+m;
            assert((c[i]-req)%d==0);
            if(c[i]-req<0){
                curr=inf;
                break;
            }
            curr+=(c[i]-req)/d;
        }
        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