Submission #1227340

#	Time	Username	Problem	Language	Result	Execution time	Memory
1227340		trinhvtuan	Triple Jump (JOI19_jumps)	C++17	100 / 100	1330 ms	93368 KiB

jumps

#include <bits/stdc++.h>
using namespace std;
const int N=5e5+5;
typedef pair<int,int>i2;
long long c,d,x,y,z,n,q;
int i,j,k;
long long ans[N],a[N];
vector<i2>b[N];
vector<int>g[N];
deque<int>dq;
struct gv
{
    long long l,r,val;
};
gv st[4*N];
gv combine(gv x,gv y)
{
    gv c={0,0,0};
    c.l=max(x.l,y.l);
    c.r=max(x.r,y.r);
    c.val=max({x.val,y.val,x.l+y.r});
    return c;
}
void buildtree(int id,int l,int r)
{
    if (l==r)
    {
        st[id].l=0;
        st[id].r=a[l];
        st[id].val=a[l];
        return;
    }
    int mid=(l+r)/2;
    buildtree(id*2,l,mid);
    buildtree(id*2+1,mid+1,r);
    st[id]=combine(st[id*2],st[id*2+1]);
}
void update(int id,int l,int r,int i,long long val)
{
    if (i<l || r<i) return;
    if (l==r)
    {
        st[id].l=max(st[id].l,val);
        st[id].val=max({st[id].val,st[id].l+st[id].r});
        return;
    }
    int mid=(l+r)/2;
    update(id*2,l,mid,i,val);
    update(id*2+1,mid+1,r,i,val);
    st[id]=combine(st[id*2],st[id*2+1]);
}
gv get(int id,int l,int r,int u,int v)
{
    if (v<l || r<u) return {0,0,0};
    if (u<=l && r<=v) return st[id];
    int mid=(l+r)/2;
    return combine(get(id*2,l,mid,u,v),get(id*2+1,mid+1,r,u,v));
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin>>n;
    for (int i=1;i<=n;i++)
    cin>>a[i];
    for (int i=n;i>=1;i--)
    {
        while (dq.size() && a[dq.back()]<a[i])
        {
            g[i].push_back(dq.back());
            dq.pop_back();
        }
        if (dq.size()) g[i].push_back(dq.back());
        dq.push_back(i);
    }
    buildtree(1,1,n);
    cin>>q;
    for (int i=1;i<=q;i++)
    {
        cin>>x>>y;
        b[x].push_back({i,y});
    }
    for (int i=n;i>=1;i--)
    {
        for (int j=0;j<g[i].size();j++)
        {
            y=g[i][j]; x=i;
            update(1,1,n,2*y-x,a[x]+a[y]);
        }
        for (int j=0;j<b[i].size();j++)
        {
            z=b[i][j].first; x=i; y=b[i][j].second;
            gv c=get(1,1,n,x,y);
            ans[z]=c.val;
        }
    }
    for (int i=1;i<=q;i++)
    cout<<ans[i]<<"\n";
}

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