Submission #1225690

#	Time	Username	Problem	Language	Result	Execution time	Memory
1225690		k12_khoi	Triple Jump (JOI19_jumps)	C++17	46 / 100	4094 ms	21332 KiB

jumps

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
#define X first
#define Y second
const int N=5e5+5;

struct queries
{
    int L,R,ID;
} Q[N];

bool cmp(queries a,queries b)
{
    return a.L<b.L;
}

int n,S,request,a[N],ma_S[N],l,x,y,z,u,v; ll ans[N],f[N],lazy_S[N],res_S[N]; deque <int> dq;
vector <pii> ve;

int main()
{
    ios_base::sync_with_stdio(NULL);
    cin.tie(NULL); cout.tie(NULL);
    cin >> n;
    S=trunc(sqrt(n));

    for (int i=1;i<=n;i++)
    {
        cin >> a[i];
        ma_S[i/S]=max(ma_S[i/S],a[i]);
    }

    cin >> request;
    for (int i=1;i<=request;i++)
    {
        cin >> Q[i].L >> Q[i].R;
        Q[i].ID=i;
    }

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

    for (int i=n;i>=1;i--)
    {
        while (!dq.empty() and a[i]>=a[dq.back()])
        {
            ve.push_back(make_pair(i,dq.back()));
            dq.pop_back();
        }
        if (!dq.empty()) ve.push_back(make_pair(i,dq.back()));
        dq.push_back(i);
    }

    sort(ve.begin(),ve.end());


    l=ve.size();
    l--;

    for (int i=request;i>=1;i--)
    {
        while (l>=0 and ve[l].X>=Q[i].L)
        {
            x=ve[l].X;
            y=ve[l].Y;
            z=a[x]+a[y];

            x=2*y-x;

            u=(x+S-1)/S;
            y=u*S-1;
            v=(n-S+1)/S;


            for (int j=x;j<=y;j++)
            {
                if (f[j]>=z) break;
                f[j]=z;
                res_S[j/S]=max(res_S[j/S],f[j]+a[j]);
            }

            for (int j=u;j<=v;j++)
            {
                if (lazy_S[j]>=z) break;
                lazy_S[j]=z;
                res_S[j]=max(res_S[j],lazy_S[j]+ma_S[j]);
            }


            x=max(2*ve[l].Y-ve[l].X,(v+1)*S);

            for (int j=x;j<=n;j++)
            {
                if (f[j]>=z) break;
                f[j]=z;
                res_S[j/S]=max(res_S[j/S],f[j]+a[j]);
            }


            l--;
        }

        x=Q[i].L+2;
        y=Q[i].R;
        u=(x+S-1)/S;
        v=(y/S+1)/S;

        y=min(u*S-1,Q[i].R);


        for (int j=x;j<=y;j++)
        ans[Q[i].ID]=max(ans[Q[i].ID],max(f[j],lazy_S[j/S])+a[j]);

        for (int j=u;j<=v;j++)
        ans[Q[i].ID]=max(ans[Q[i].ID],res_S[j]);

        x=max(Q[i].L+2,(v+1)*S);
        y=Q[i].R;

        for (int j=x;j<=y;j++)
        ans[Q[i].ID]=max(ans[Q[i].ID],max(f[j],lazy_S[j/S])+a[j]);
    }

    for (int i=1;i<=request;i++)
    cout << ans[i] << '\n';
}

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