oj.uz

Submission #794699

# Submission time Handle Problem Language Result Execution time Memory
794699 2023-07-26T19:16:37 Z anton Triple Jump (JOI19_jumps) C++17
100 / 100
 1628 ms 89252 KB 
#include<bits/stdc++.h>

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


const int MAX_N = 5*1e5 +1;
const int INF = 1e10;
int n, q;
int A[MAX_N],tree[4*MAX_N], d[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_max(int l, int r, int lt, int rt, int t){
    if(l<=lt && rt<=r){
        return tree[t];
    }
    else if(r<lt|| rt <l){
        return -INF;
    }
    else{
        int mid = (lt+rt)/2;

        return max(get_max(l, r, lt, mid, t*2), get_max(l, r, mid+1,rt, t*2+1)) + d[t];
    }
}

void add(int l, int r, int v, int lt, int rt, int t){
    if(l<=lt && rt<=r){
        d[t]+=v;
        tree[t] +=v;
    }
    else if(r<lt|| rt <l){
        return;
    }
    else{
        int mid = (lt+rt)/2;

        add(l, r, v, lt, mid, t*2);
        add(l, r, v, mid+1,rt, t*2+1);

        tree[t] = max(tree[t*2], tree[t*2+1]) + d[t];
    }
}

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;

    for(int i = 0; i<n; i++){
        A[i]-=INF;
    }

    build(0, n-1, 1);

    for(int i = 0; i<n; i++){
        A[i]+=INF;
    }

    vector<pair<pii, int>> quers;
    vector<int> ans(q);

    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;*/
        quers.push_back(pair<pii, int>(pii(l, r), i));
    }

    sort(c.begin(), c.end());
    sort(quers.begin(), quers.end());

    map<int, int> inters;
    inters.insert(pii(n, INF));
    inters.insert(pii(-1, -INF));

    for(int i = n-1; i>=0; i--){
        while(c.size()>0 && c.back().first>=i){
            pii inter = c.back();
            c.pop_back();
            //cout<<"inter "<<inter.first<<" "<<inter.second<<endl;
            int effect= 2*inter.second - inter.first;
            int value = A[inter.first]+ A[inter.second];

            if(effect>n-1){
                continue;
            }

            auto it = inters.upper_bound(effect);
            if((--it)->second<value){
                ////cout<<"valid "<<value<<endl;
                int cur_val = value -it->second;
                inters[effect] = value;
                it = inters.find(effect);
                it++;
                while(it!=inters.end()){
                    //cout<<"adding "<<effect<<" "<<(it->first)-1<<" "<<cur_val<<endl;
                    add(effect, (it->first)-1, cur_val, 0, n-1, 1);

                    if(it->second<value){
                        cur_val=value- it->second;
                        effect = it->first;
                        inters.erase(it++);
                    }
                    else{
                        break;
                    }
                } 
            }
            else{
                //////cout<<"already have better"<<endl;
            }

            //cout<<"show set "<<endl;
        }

        while(quers.size()>0 && quers.back().first.first>=i){
            auto que = quers.back();
            quers.pop_back();
            ans[que.second] = get_max(que.first.first, que.first.second, 0, n-1, 1);
        }
    }
    for(auto e: ans){
        cout<<e<<endl;
    }
}

Subtask #1
5.0 / 5.0

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

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 304 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 892 ms 26252 KB Output is correct
12 Correct 820 ms 26260 KB Output is correct
13 Correct 820 ms 26308 KB Output is correct
14 Correct 836 ms 26340 KB Output is correct
15 Correct 869 ms 26260 KB Output is correct
16 Correct 868 ms 25524 KB Output is correct
17 Correct 829 ms 25568 KB Output is correct
18 Correct 823 ms 25592 KB Output is correct
19 Correct 827 ms 26156 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 215 ms 16972 KB Output is correct
2 Correct 171 ms 26480 KB Output is correct
3 Correct 132 ms 18212 KB Output is correct
4 Correct 257 ms 18308 KB Output is correct
5 Correct 217 ms 18136 KB Output is correct
6 Correct 228 ms 17520 KB Output is correct
7 Correct 204 ms 17444 KB Output is correct
8 Correct 200 ms 17460 KB Output is correct
9 Correct 210 ms 17800 KB Output is correct

Subtask #4
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 304 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 892 ms 26252 KB Output is correct
12 Correct 820 ms 26260 KB Output is correct
13 Correct 820 ms 26308 KB Output is correct
14 Correct 836 ms 26340 KB Output is correct
15 Correct 869 ms 26260 KB Output is correct
16 Correct 868 ms 25524 KB Output is correct
17 Correct 829 ms 25568 KB Output is correct
18 Correct 823 ms 25592 KB Output is correct
19 Correct 827 ms 26156 KB Output is correct
20 Correct 215 ms 16972 KB Output is correct
21 Correct 171 ms 26480 KB Output is correct
22 Correct 132 ms 18212 KB Output is correct
23 Correct 257 ms 18308 KB Output is correct
24 Correct 217 ms 18136 KB Output is correct
25 Correct 228 ms 17520 KB Output is correct
26 Correct 204 ms 17444 KB Output is correct
27 Correct 200 ms 17460 KB Output is correct
28 Correct 210 ms 17800 KB Output is correct
29 Correct 1519 ms 80280 KB Output is correct
30 Correct 1399 ms 89252 KB Output is correct
31 Correct 1343 ms 74096 KB Output is correct
32 Correct 1628 ms 80172 KB Output is correct
33 Correct 1573 ms 80260 KB Output is correct
34 Correct 1571 ms 77876 KB Output is correct
35 Correct 1501 ms 77688 KB Output is correct
36 Correct 1500 ms 77692 KB Output is correct
37 Correct 1523 ms 79052 KB Output is correct
38 Correct 1447 ms 80276 KB Output is correct
39 Correct 1432 ms 80292 KB Output is correct
40 Correct 1418 ms 77064 KB Output is correct
41 Correct 1434 ms 76532 KB Output is correct
42 Correct 1448 ms 76428 KB Output is correct
43 Correct 1475 ms 78288 KB Output is correct
44 Correct 1475 ms 80248 KB Output is correct
45 Correct 1487 ms 80308 KB Output is correct
46 Correct 1533 ms 77108 KB Output is correct
47 Correct 1470 ms 76816 KB Output is correct
48 Correct 1489 ms 76724 KB Output is correct
49 Correct 1478 ms 78736 KB Output is correct
50 Correct 1547 ms 80252 KB Output is correct
51 Correct 1531 ms 80344 KB Output is correct
52 Correct 1485 ms 77852 KB Output is correct
53 Correct 1564 ms 77500 KB Output is correct
54 Correct 1514 ms 77504 KB Output is correct
55 Correct 1559 ms 79232 KB Output is correct