Submission #1226695

#	Time	Username	Problem	Language	Result	Execution time	Memory
1226695		k12_khoi	Triple Jump (JOI19_jumps)	C++17	100 / 100	574 ms	41596 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 query
{
    int L,R,ID;
} Q[N];

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

int n,request,l,x,y,z,u,v,a[N],ori_t[4*N],lazy[4*N]; ll t[4*N],ans[N];
vector <pii> ve; deque <int> dq;

void down(int id)
{
    lazy[id*2]=max(lazy[id*2],lazy[id]);
    lazy[id*2+1]=max(lazy[id*2+1],lazy[id]);
    t[id*2]=max(t[id*2],(ll)ori_t[id*2]+lazy[id*2]);
    t[id*2+1]=max(t[id*2+1],(ll)ori_t[id*2+1]+lazy[id*2+1]);
}

void build(int id,int l,int r)
{
    if (l==r)
    {
        ori_t[id]=a[l];
        return;
    }
    int m=(l+r)/2;
    build(id*2,l,m);
    build(id*2+1,m+1,r);
    ori_t[id]=max(ori_t[id*2],ori_t[id*2+1]);
}

void update(int id,int l,int r)
{
    if (u>r or v<l) return;
    if (u<=l and v>=r)
    {
        lazy[id]=max(lazy[id],z);
        t[id]=max(t[id],(ll)ori_t[id]+lazy[id]);
        return;
    }
    down(id);
    int m=(l+r)/2;
    update(id*2,l,m);
    update(id*2+1,m+1,r);
    t[id]=max(t[id*2],t[id*2+1]);
}

ll get(int id,int l,int r)
{
    if (u>r or v<l) return 0;
    if (u<=l and v>=r) return t[id];
    down(id);
    int m=(l+r)/2;
    return max(get(id*2,l,m),get(id*2+1,m+1,r));
}

int main()
{
    ios_base::sync_with_stdio(NULL);
    cin.tie(NULL); cout.tie(NULL);
    cin >> n;
    for (int i=1;i<=n;i++)
    cin >> 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);

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

    sort(ve.begin(),ve.end());
    l=ve.size();
    l--;

    build(1,1,n);

    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];

            u=2*y-x;
            v=n;
            update(1,1,n);

            l--;
        }

        u=Q[i].L+2;
        v=Q[i].R;
        ans[Q[i].ID]=get(1,1,n);
    }

    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: 54 / 54