Submission #1010734

#	Time	Username	Problem	Language	Result	Execution time	Memory
1010734		berr	Fish 3 (JOI24_fish3)	C++17	9 / 100	98 ms	19484 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);
    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;
    }
    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]);
                int sum=p[r]-(l==0?0:p[l-1]);
                sum+=mi*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]>=2) f=0;  
        }
        if(f){
            while(q--){
                int l, r; cin >> l >> r;
                int val=p[r]-(l==0?0:p[l-1]);
                if(val==r-l+1||p[r]-p[l-val]==val){
                    cout<<0<<"\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: 0 / 7
• Subtask 3: 0 / 28
• Subtask 4: 0 / 20
• Subtask 5: 0 / 36