oj.uz

Submission #1010734

# Submission time Handle Problem Language Result Execution time Memory
1010734 2024-06-29T10:07:12 Z berr Fish 3 (JOI24_fish3) C++17
9 / 100
 98 ms 19484 KB 
#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

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

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 8 ms 344 KB Output is correct
5 Correct 8 ms 348 KB Output is correct
6 Correct 5 ms 348 KB Output is correct
7 Correct 5 ms 344 KB Output is correct
8 Correct 8 ms 600 KB Output is correct
9 Correct 7 ms 348 KB Output is correct
10 Correct 8 ms 568 KB Output is correct
11 Correct 7 ms 560 KB Output is correct
12 Correct 8 ms 348 KB Output is correct
13 Correct 8 ms 556 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Runtime error 25 ms 19484 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 28.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 98 ms 10088 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 8 ms 344 KB Output is correct
5 Correct 8 ms 348 KB Output is correct
6 Correct 5 ms 348 KB Output is correct
7 Correct 5 ms 344 KB Output is correct
8 Correct 8 ms 600 KB Output is correct
9 Correct 7 ms 348 KB Output is correct
10 Correct 8 ms 568 KB Output is correct
11 Correct 7 ms 560 KB Output is correct
12 Correct 8 ms 348 KB Output is correct
13 Correct 8 ms 556 KB Output is correct
14 Runtime error 25 ms 19484 KB Execution killed with signal 11
15 Halted 0 ms 0 KB -