Submission #1010763

#	Time	Username	Problem	Language	Result	Execution time	Memory
1010763		berr	Fish 3 (JOI24_fish3)	C++17	36 / 100	107 ms	24916 KiB

Main

#include <bits/stdc++.h>
using namespace std;
 
#define int long long
 
const int mod = 998244353, mod2=998244353ll*998244353;



signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int n, d; cin >> n >> d;

    vector<int> a(n);

    for(auto &i: a) cin >> i;

    vector<int> dp(n+1, 0), v(n, 0), p(n, 0), pref(n, 0);
    int val=0;
    for(int i=n-2; i>=0; i--){
        if(a[i]%d > a[i+1]%d){
            val--;
        }
        v[i]=val;
        dp[i]=dp[i+1]+val;
    }   
    auto query=[&](int l, int r){
        int val1=a[r]/d, val2=a[r]%d;
        int ans=0;
        int sum=0;
        for(int i=r-1; i>=l; i--){
            if(a[i]%d>val2){
                val1--;
            }
            val2=a[i]%d;

            val1=min(val1, a[i]/d);
            sum+=a[i]/d-val1;
        }

        if(val1<0) return -1LL;
        else return sum;
    };

    p[0]=a[0]-a[0]%d;

    for(int i=1; i<n; i++){
        p[i]+=p[i-1]+a[i]-a[i]%d;
    }
    pref=a;
    for(int i=1; i<n; i++) pref[i]+=pref[i-1];
    int q; cin >> q;
    int f=1;
    for(int i=1; i<n; i++){
        if(a[i-1]<a[i]) f=0;
    }
    if(f){
        while(q--){
            int l, r; cin >> l >> r;
            l--; r--;
            int val=-(v[l]-v[r]);
            if(l==r) cout<<0<<"\n";
            else if(val*d >a[r]) cout<<-1<<"\n";
            else{

                int mi=(dp[l]-dp[r+1])-v[r]*(r-l+1);
                int sum=p[r-1]-(l==0?0:p[l-1]);
                sum-=(mi+(a[r]/d)*((r-l)))*d;
                cout<<sum/d<<"\n";
            }
        }
    }
    else if(n<=3000&&q<=3000){
        while(q--){
            int l, r; cin >> l >> r;
            l--; r--;
            cout<<query(l, r)<<"\n";
        }
    }
    else{
        int f=1;
        for(int i=0; i<n; i++){
            if(a[i]>1) f=0;
        }
        if(f){
            vector<int> c(n);
            c[0]=1;

            for(int i=1; i<n; i++){
                if(a[i]!=a[i-1]) c[i]=1;
                else c[i]=c[i-1]+1;
            }

            while(q--){
                int l, r; cin >> l >> r;
                l--; r--;
                int val=pref[r]-(l==0?0:pref[l-1]);
                if(val==r-l+1||(pref[r]-pref[r-val])==val){
                    cout<<0<<"\n";
                }
                else{
                    if(d==1){
                        if(a[r]==0) cout<<val<<"\n";
                        else cout<<val-c[r]<<"\n";
                    }
                    else{
                        cout<<-1<<"\n";
                    }
                }
            }
        }

    }

}

Compilation message (stderr)

Main.cpp: In lambda function:
Main.cpp:31:13: warning: unused variable 'ans' [-Wunused-variable]
   31 |         int ans=0;
      |             ^~~

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