제출 #182117

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
182117		Andrei_Cotor	3단 점프 (JOI19_jumps)	C++14	0 / 100	193 ms	28916 KiB

jumps

#include<iostream>
#include<algorithm>
#include<vector>
#include<deque>

using namespace std;

typedef struct qry
{
    int st,dr,ind;
} QRY;

int A[500005],St[500005],Dr[500005],Rez[500005],Max[2000005],AddMax[2000005],Ans[2000005];
QRY Q[500005];
vector<int> Per[500005];

bool cmp(QRY a, QRY b)
{
    return a.st>b.st;
}

void build(int nod, int st, int dr)
{
    if(st==dr)
    {
        Max[nod]=Ans[nod]=A[st];
        return;
    }

    int mij=(st+dr)/2;

    build(2*nod,st,mij);
    build(2*nod+1,mij+1,dr);

    Max[nod]=max(Max[2*nod],Max[2*nod+1]);
    Ans[nod]=max(Ans[2*nod],Ans[2*nod+1]);
}

void update(int nod, int st, int dr, int l, int val)
{
    if(l<=st)
    {
        AddMax[nod]=max(AddMax[nod],val);
        return;
    }

    Ans[nod]=max(Ans[nod],Max[nod]+AddMax[nod]);
    AddMax[2*nod]=max(AddMax[2*nod],AddMax[nod]);
    AddMax[2*nod+1]=max(AddMax[2*nod+1],AddMax[nod]);

    int mij=(st+dr)/2;

    if(l<=mij)
        update(2*nod,st,mij,l,val);
    update(2*nod+1,mij+1,dr,l,val);

    Ans[nod]=max(Max[2*nod]+AddMax[2*nod],Max[2*nod+1]+AddMax[2*nod+1]);
}

int query(int nod, int st, int dr, int l, int r)
{
    Ans[nod]=max(Ans[nod],Max[nod]+AddMax[nod]);
    AddMax[2*nod]=max(AddMax[2*nod],AddMax[nod]);
    AddMax[2*nod+1]=max(AddMax[2*nod+1],AddMax[nod]);

    if(l<=st && dr<=r)
        return Ans[nod];

    int mij=(st+dr)/2;

    int rez=0;
    if(l<=mij)
        rez=max(rez,query(2*nod,st,mij,l,r));
    if(mij<r)
        rez=max(rez,query(2*nod+1,mij+1,dr,l,r));

    return rez;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin>>n;

    for(int i=1; i<=n; i++)
        cin>>A[i];

    deque<int> S;
    for(int i=1; i<=n; i++)
    {
        while(!S.empty() && A[S.back()]<=A[i])
        {
            Dr[S.back()]=i;
            S.pop_back();
        }

        if(!S.empty())
            St[i]=S.back();

        S.push_back(i);
    }

    //max 2*n perechi relevante pt a si b
    for(int i=1; i<=n; i++)
    {
        if(St[i]!=0)
            Per[St[i]].push_back(i);
        if(Dr[i]!=0)
            Per[i].push_back(Dr[i]);
    }

    int q;
    cin>>q;
    for(int i=1; i<=q; i++)
    {
        cin>>Q[i].st>>Q[i].dr;
        Q[i].ind=i;
    }

    sort(Q+1,Q+q+1,cmp);

    build(1,1,n);

    int ind=n;
    for(int i=1; i<=q; i++)
    {
        while(ind>=Q[i].st)
        {
            for(auto y:Per[ind])
            {
                if(y+y-ind<=n)
                    update(1,1,n,y+y-ind,A[ind]+A[y]);
            }

            ind--;
        }

        Rez[Q[i].ind]=query(1,1,n,Q[i].st,Q[i].dr);
    }

    for(int i=1; i<=q; i++)
        cout<<Rez[i]<<"\n";
    return 0;
}

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