제출 #1010735

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1010735		berr	Fish 3 (JOI24_fish3)	C++17	9 / 100	70 ms	19544 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{
                    if(d==1){
                        int j=val-p[r]-p[l-val];
                        cout<<j<<"\n";  
                    }
                    else{
                        cout<<-1<<"\n";
                    }
                }
            }
        }

    }

}

컴파일 시 표준 에러 (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