oj.uz

Submission #981688

# Submission time Handle Problem Language Result Execution time Memory
981688 2024-05-13T12:59:05 Z anton Fish 3 (JOI24_fish3) C++17
55 / 100
 1093 ms 121256 KB 
#include<bits/stdc++.h>

using namespace std;
#define int long long

int n, D;
vector<int> a;
vector<int> left_low;
vector<vector<pair<int, int>>> bl;

vector<int> cumul;
vector<int> d;
vector<int> cumul_d;
vector<int> cumul_cumul_d;

int take_mod(int v){
    if(v>=0){
        return v%D;
    }
    else{
        //cout<<v<<" "<<D+(v%D)<<endl;
        return (D+(v%D))%D;
    }
}
void precalc(){

    vector<pair<int, int>> st;
    a[0] = 0;

    d.resize(n+1);
    for(int i= 1; i<n; i++){
        d[i] = take_mod(a[i+1]-a[i]);
    }
    cumul_d.resize(n+1);
    for(int i = 1; i<=n; i++){
        cumul_d[i] =cumul_d[i-1] + d[i-1];
        //cout<<i<<" "<<cumul_d[i]<<endl;
    }
    cumul_cumul_d.resize(n+1);
    for(int i = 1; i<=n; i++){
        cumul_cumul_d[i] = cumul_cumul_d[i-1] + cumul_d[i]; 
    }
    left_low.resize(n+1);
    
    for(int i = n; i>=0; i--){
        int v=  a[i]+cumul_d[n]-cumul_d[i];
        while(st.size()>0 && st.back().second>=v){
            left_low[st.back().first] = i;
            st.pop_back();
        }
        st.push_back({i, v});
    }

    for(auto e: st){
        left_low[e.first] = -1;
    }

    left_low[0] = -1;


    bl.resize(20);
    for(int i = 0; i<20; i++){
        bl[i].resize(n+1);
    }

    for(int i = 0; i<=n; i++){
        bl[0][i] = {left_low[i], max(0LL, cumul_cumul_d[i]-cumul_cumul_d[left_low[i]+1]) + (a[i]-cumul_d[i]+cumul_d[left_low[i]]) * (i-left_low[i])- (max(0LL, i-left_low[i]-1)) * cumul_d[left_low[i]+1]};
        //cout<<i<<" "<<bl[0][i].first<<" "<<bl[0][i].second<<endl;
    }
    for(int step = 1; step<20; step++){
        for(int i = 0; i<=n; i++){
            if(bl[step-1][i].first ==-1){
                bl[step][i] = bl[step-1][i];
            }
            else{
                auto lh = bl[step-1][bl[step-1][i].first];
                bl[step][i]={lh.first, lh.second + bl[step-1][i].second};
            }
        }
    }
}

int Bs(int cur, int lim){
    int res = 0;
    for(int step = 19; step>=0; step--){
        if(bl[step][cur].first>=lim){
            res += bl[step][cur].second;
            cur = bl[step][cur].first;
        }
    }
    if(cur>lim){
        //cout<<"detail "<<cumul_cumul_d[cur]-cumul_cumul_d[lim+1]<<" "<<(a[cur]-cumul_d[cur]+cumul_d[lim+1]) * (cur-lim)<<endl;
        res += cumul_cumul_d[cur]-cumul_cumul_d[lim+1]+(a[cur]-cumul_d[cur]+cumul_d[lim+1]) * (cur-lim) - (cur-lim-1) * cumul_d[lim+1];
    }
    if(a[cur]-cumul_d[cur]+cumul_d[lim+1] < 0){
        return -1;
    }
    return res;
}

signed main(){
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);
    
    cin>>n>>D;
    a.resize(n+1);
    cumul.resize(n+1);
    cumul[0] = 0;
    for(int i = 1; i<=n; i++){
        cin>>a[i];
        cumul[i] = cumul[i-1] + a[i];
    }

    precalc();
    int q;
    cin>>q;
    for(int i =0; i<q; i++){
        int l, r;
        cin>>l>>r;
        int bs = Bs(r, l-1);
        if(bs == -1){
            cout<<-1<<endl;
        }
        else{
            cout<<(cumul[r]-cumul[l-1]-bs)/D<<endl;
        }
    }

}

Subtask #1
0 / 9.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1035 ms 110460 KB Output is correct
2 Correct 952 ms 109640 KB Output is correct
3 Correct 390 ms 2312 KB Output is correct
4 Correct 598 ms 109768 KB Output is correct
5 Correct 606 ms 109768 KB Output is correct
6 Correct 825 ms 113956 KB Output is correct
7 Correct 867 ms 113616 KB Output is correct

Subtask #3
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 409 ms 5976 KB Output is correct
2 Correct 622 ms 113592 KB Output is correct
3 Correct 624 ms 113780 KB Output is correct
4 Correct 622 ms 113860 KB Output is correct
5 Correct 613 ms 113592 KB Output is correct
6 Correct 902 ms 110572 KB Output is correct
7 Correct 906 ms 110676 KB Output is correct
8 Correct 916 ms 110532 KB Output is correct
9 Correct 930 ms 110460 KB Output is correct
10 Correct 1063 ms 109152 KB Output is correct
11 Correct 1024 ms 109348 KB Output is correct
12 Correct 1016 ms 112464 KB Output is correct
13 Correct 1093 ms 112160 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 681 ms 91740 KB Output is correct
2 Correct 653 ms 110344 KB Output is correct
3 Correct 532 ms 25932 KB Output is correct
4 Correct 652 ms 110164 KB Output is correct
5 Correct 607 ms 100652 KB Output is correct
6 Correct 635 ms 115168 KB Output is correct
7 Correct 619 ms 90752 KB Output is correct
8 Correct 630 ms 114368 KB Output is correct
9 Correct 661 ms 109456 KB Output is correct
10 Correct 645 ms 109512 KB Output is correct
11 Correct 697 ms 117844 KB Output is correct
12 Correct 659 ms 117324 KB Output is correct
13 Correct 632 ms 121168 KB Output is correct
14 Correct 597 ms 117696 KB Output is correct
15 Correct 641 ms 121256 KB Output is correct
16 Correct 594 ms 118464 KB Output is correct

Subtask #5
0 / 36.0

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