oj.uz

답안 #981641

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
981641 2024-05-13T12:06:26 Z anton Fish 3 (JOI24_fish3) C++17
28 / 100
 1084 ms 114752 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;
const int INF = 1e9;
void precalc(){

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

    d.resize(n+1);
    for(int i= 1; i<n; i++){
        d[i] = (a[i+1]-a[i]+INF*D)%D;
    }
    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] = 0;


    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

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Incorrect 0 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1071 ms 110164 KB Output is correct
2 Correct 1004 ms 109696 KB Output is correct
3 Correct 393 ms 1960 KB Output is correct
4 Correct 610 ms 114076 KB Output is correct
5 Incorrect 1054 ms 113844 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
28.0 / 28.0

# 결과 실행 시간 메모리 Grader output
1 Correct 403 ms 5840 KB Output is correct
2 Correct 670 ms 114004 KB Output is correct
3 Correct 630 ms 113744 KB Output is correct
4 Correct 612 ms 113744 KB Output is correct
5 Correct 657 ms 113980 KB Output is correct
6 Correct 910 ms 110540 KB Output is correct
7 Correct 907 ms 110596 KB Output is correct
8 Correct 960 ms 110356 KB Output is correct
9 Correct 923 ms 110668 KB Output is correct
10 Correct 1059 ms 109032 KB Output is correct
11 Correct 1084 ms 109220 KB Output is correct
12 Correct 1042 ms 112100 KB Output is correct
13 Correct 1051 ms 112216 KB Output is correct

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 614 ms 91732 KB Output is correct
2 Correct 685 ms 110116 KB Output is correct
3 Correct 496 ms 25692 KB Output is correct
4 Correct 665 ms 110416 KB Output is correct
5 Correct 654 ms 100788 KB Output is correct
6 Correct 616 ms 113824 KB Output is correct
7 Correct 587 ms 90628 KB Output is correct
8 Correct 629 ms 113856 KB Output is correct
9 Correct 637 ms 109368 KB Output is correct
10 Incorrect 560 ms 114752 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Incorrect 0 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -