Submission #1010722

#	Time	Username	Problem	Language	Result	Execution time	Memory
1010722		berr	Fish 3 (JOI24_fish3)	C++17	0 / 100	76 ms	20560 KiB

Main

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

int sum(int x, int y){
    x+=y;
    if(x>=mod2) x-=mod2;
    return x;
}

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;
    }   

    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--;
            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) cout<<-1<<"\n";
            else cout<<sum<<"\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==l-r+1||p[r]-p[l-val]==val){
                    cout<<0<<"\n";
                }
                else cout<<"-1\n";
            }
        }
    
    }

}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:64:17: warning: unused variable 'ans' [-Wunused-variable]
   64 |             int ans=0;
      |                 ^~~

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