oj.uz

Submission #794428

# Submission time Handle Problem Language Result Execution time Memory
794428 2023-07-26T14:16:14 Z anton Triple Jump (JOI19_jumps) C++17
32 / 100
 4000 ms 14204 KB 
#include<bits/stdc++.h>

using namespace std;
#define int long long
#define pii pair<int, int>


const int MAX_N = 5*1e5;
const int INF = 1e18;
int n, q;
int A[MAX_N], tree[4*MAX_N];

void build(int lt, int rt, int t){
    if(lt == rt){
        tree[t] = A[lt];
    }
    else{
        int mid = (lt+rt)/2;

        build(lt, mid, t*2);
        build(mid+1, rt, t*2+1);
        tree[t] = max(tree[t*2], tree[t*2+1]);
    }
}

int get(int l, int r, int lt, int rt, int t){
    if(l<=lt && rt<=r){
        return tree[t];
    }
    else if(rt<l || r<lt){
        return -INF;
    }
    else{
        int mid = (lt + rt)/2;

        return max(get(l, r, lt, mid, t*2), get(l, r, mid+1, rt, t*2+1));
    }
}

int get(int l, int r){
    if(l>r){
        return -INF;
    }
    else{
        l = max(l, 0LL);
        r = min(r, n-1);

        //cout<<"getting "<<l<<" "<<r<<" "<<get(l, r, 0, n-1, 1)<<endl;
        return get(l, r, 0, n-1, 1);
    }
}

signed main(){
    cin>>n;
    for(int i = 0; i<n; i++){
        cin>>A[i];
    }

    vector<pii> st;
    vector<pii> c;

    for(int i= 0; i<n; i++){
        while(st.size()>0 && st.back().second<A[i]){
            c.push_back(pii(st.back().first, i));
            st.pop_back();
        }

        if(st.size()>=1){
            c.push_back(pii(st[st.size()-1].first, i));
        }

        st.push_back(pii(i, A[i]));
    }

    cin>>q;

    build(0, n-1, 1);

    for(int i = 0; i<q; i++){
        int l, r;
        cin>>l>>r;
        l--;
        r--;
        int res= 0;

        for(auto [a, b]: c){
            if(a>=l){
                //cout<<a<<" "<<b<<endl;
                int d = b-a;
                res = max(res, A[a]+A[b]+get(b+d, r));
            }
        }

        cout<<res<<endl;
    }
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 308 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 308 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Execution timed out 4062 ms 1200 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 106 ms 14036 KB Output is correct
2 Correct 79 ms 10912 KB Output is correct
3 Correct 82 ms 14204 KB Output is correct
4 Correct 106 ms 14008 KB Output is correct
5 Correct 106 ms 14112 KB Output is correct
6 Correct 96 ms 13416 KB Output is correct
7 Correct 93 ms 13332 KB Output is correct
8 Correct 90 ms 13364 KB Output is correct
9 Correct 95 ms 13620 KB Output is correct

Subtask #4
0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 308 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Execution timed out 4062 ms 1200 KB Time limit exceeded
12 Halted 0 ms 0 KB -