Submission #981688

#	Time	Username	Problem	Language	Result	Execution time	Memory
981688		anton	Fish 3 (JOI24_fish3)	C++17	55 / 100	1093 ms	121256 KiB

Main

#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
• Subtask 2: 7 / 7
• Subtask 3: 28 / 28
• Subtask 4: 20 / 20
• Subtask 5: 0 / 36