Submission #147807

#	Time	Username	Problem	Language	Result	Execution time	Memory
147807		Bodo171	Triple Jump (JOI19_jumps)	C++14	100 / 100	1214 ms	101608 KiB

jumps

#include <bits/stdc++.h>

using namespace std;

const int nmax=500005;
vector< pair<int,int> > l[nmax],qr[nmax];
int v[nmax],st[nmax],an[nmax];
int n,i,j,u,q,L,R;
struct node
{
    int L,R,LR;
}arb[4*nmax],ans;
void add(int x,int y)
{
    if(2*y-x<=n)
     l[x].push_back({2*y-x,v[x]+v[y]});
}
void mrg(node &A,node B,node C)
{
    A.L=max(B.L,C.L);
    A.R=max(B.R,C.R);
    A.LR=max(B.LR,C.LR);
    A.LR=max(A.LR,B.L+C.R);
}
void update(int nod,int l,int r,int poz,int val,int tip)
{
    if(l==r)
    {
        if(tip) arb[nod].R=max(arb[nod].R,val);
        else arb[nod].L=max(arb[nod].L,val);
        arb[nod].LR=arb[nod].L+arb[nod].R;
        return;
    }
    int m=(l+r)/2;
    if(poz<=m) update(2*nod,l,m,poz,val,tip);
    else update(2*nod+1,m+1,r,poz,val,tip);
    mrg(arb[nod],arb[2*nod],arb[2*nod+1]);
}
void query(int nod,int l,int r,int st,int dr)
{
    if(st<=l&&r<=dr)
    {
        mrg(ans,ans,arb[nod]);
        return;
    }
    int m=(l+r)/2;
    if(st<=m) query(2*nod,l,m,st,dr);
    if(m<dr)  query(2*nod+1,m+1,r,st,dr);
}
int Q(int S,int D)
{
    ans={-(1<<29),-(1<<29),-(1<<29)};
    query(1,1,n,S,D);
    return ans.LR;
}
int main()
{
    //freopen("data.in","r",stdin);
    ios_base::sync_with_stdio(false);
    cin>>n;
    for(i=1;i<=n;i++)
    {
        cin>>v[i];
        while(u>0&&v[i]>v[st[u]])
        {
            add(st[u],i);
            u--;
        }
        if(u) add(st[u],i);
        st[++u]=i;
    }
    cin>>q;
    for(i=1;i<=q;i++)
    {
        cin>>L>>R;
        qr[L].push_back({R,i});
    }
    for(i=1;i<=4*n;i++)
    {
        arb[i].L=arb[i].R=arb[i].LR=-(1<<29);
    }
    for(i=n;i>=1;i--)
    {
        update(1,1,n,i,v[i],1);
        for(auto it: l[i])
            update(1,1,n,it.first,it.second,0);
        for(auto it: qr[i])
            an[it.second]=Q(i,it.first);
    }
    for(i=1;i<=q;i++)
        cout<<an[i]<<'\n';
    return 0;
}

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