Submission #1213532

#	Time	Username	Problem	Language	Result	Execution time	Memory
1213532		minhpk	Triple Jump (JOI19_jumps)	C++20	100 / 100	721 ms	119736 KiB

jumps

#include <bits/stdc++.h>
#define int long long
using namespace std;
int a;
int z[1000005];
vector<int> v[1000005];
struct node{
    int val,ab,c;
};
node f[4000005];
vector<pair<int,int>> q[1000005];
int res[1000005];

void push(int id,int val){
    if (f[id].ab<val){
        f[id].val=max(val+f[id].c,f[id].val);
        f[id].ab=val;
    }
}

void build(int id,int l,int r){
    if (l==r){
        f[id].c=z[l];
        return;
    }
    int mid=(l+r)/2;
    build(id*2,l,mid);
    build(id*2+1,mid+1,r);
    f[id].c=max(f[id*2].c,f[id*2+1].c);
}

void update(int id,int l,int r,int x,int y,int val){
    if (x>r || y<l){
         return;
    }
    if (l>=x && y>=r){
        push(id,val);
        return;
    }
    push(id*2,f[id].ab);
    push(id*2+1,f[id].ab);
    int mid=(l+r)/2;
    update(id*2,l,mid,x,y,val);
    update(id*2+1,mid+1,r,x,y,val);
    f[id].val=max(f[id*2].val,f[id*2+1].val);
}

int get(int id,int l,int r,int x,int y){
    if (x>r || y<l){
        return 0;
    }
    if (l>=x && y>=r){
        return f[id].val;
    }
    push(id*2,f[id].ab);
    push(id*2+1,f[id].ab);
    int mid=(l+r)/2;
    return max(get(id*2,l,mid,x,y),get(id*2+1,mid+1,r,x,y));
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> a;
    for (int i=1;i<=a;i++){
         cin >> z[i];
    }

    stack<int> st;
    for (int i=1;i<=a;i++){
         while (st.size() && z[st.top()]<=z[i]){
              v[st.top()].push_back(i);
              st.pop();
         }
         if (st.size()){
             v[st.top()].push_back(i);
         }
         st.push(i);
    }

    build(1,1,a);
    int t;
    cin >> t;
    for (int i=1;i<=t;i++){
         int l,r;
         cin >> l >> r;
         q[l].push_back({r,i});
    }

    for (int i=a;i>=1;i--){
         for (auto p:v[i]){
              int range=2*p-i;
              int val=z[i]+z[p];
              update(1,1,a,range,a,val);
         }
         for (auto p:q[i]){
              res[p.second]=get(1,1,a,i,p.first);
         }
    }
    for (int i=1;i<=t;i++){
         cout << res[i] << "\n";
    }


    return 0;
}

• Subtask 1: 5 / 5
• Subtask 2: 14 / 14
• Subtask 3: 27 / 27
• Subtask 4: 54 / 54