oj.uz

Submission #981512

# Submission time Handle Problem Language Result Execution time Memory
981512 2024-05-13T09:35:37 Z anton Fish 3 (JOI24_fish3) C++17
28 / 100
 1045 ms 114924 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;
void precalc(){

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

    left_low.resize(n+1);
    
    for(int i = n; i>=0; i--){
        while(st.size()>0 && a[st.back()]>=a[i]){
            left_low[st.back()] = i;
            st.pop_back();
        }
        st.push_back(i);
    }
    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], a[i] * (i-left_low[i])};
    }
    for(int step = 1; step<20; step++){
        for(int i = 0; i<=n; i++){
            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){
        res += (cur-lim) * a[cur];
    }
    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;
        cout<<cumul[r]-cumul[l-1]-Bs(r, l-1)<<endl;
    }
}

Subtask #1
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 Incorrect 0 ms 456 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 986 ms 107748 KB Output is correct
2 Correct 856 ms 107208 KB Output is correct
3 Incorrect 406 ms 5064 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 403 ms 8588 KB Output is correct
2 Correct 621 ms 114244 KB Output is correct
3 Correct 624 ms 114440 KB Output is correct
4 Correct 593 ms 114344 KB Output is correct
5 Correct 585 ms 114256 KB Output is correct
6 Correct 888 ms 107952 KB Output is correct
7 Correct 869 ms 108108 KB Output is correct
8 Correct 906 ms 111080 KB Output is correct
9 Correct 933 ms 111152 KB Output is correct
10 Correct 1045 ms 109684 KB Output is correct
11 Correct 991 ms 109704 KB Output is correct
12 Correct 1000 ms 112932 KB Output is correct
13 Correct 1014 ms 112880 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 636 ms 90284 KB Output is correct
2 Correct 607 ms 107600 KB Output is correct
3 Correct 499 ms 28488 KB Output is correct
4 Correct 690 ms 110928 KB Output is correct
5 Correct 627 ms 101512 KB Output is correct
6 Correct 595 ms 114380 KB Output is correct
7 Correct 610 ms 91928 KB Output is correct
8 Correct 586 ms 114924 KB Output is correct
9 Incorrect 640 ms 107612 KB Output isn't correct
10 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 Incorrect 0 ms 456 KB Output isn't correct
4 Halted 0 ms 0 KB -