Submission #1190788

#	Time	Username	Problem	Language	Result	Execution time	Memory
1190788		alexdd	Triple Jump (JOI19_jumps)	C++20	32 / 100	4094 ms	29796 KiB

jumps

#include <bits/stdc++.h>
using namespace std;
int n;
int a[500005];
int tole[500005],tori[500005];
vector<pair<pair<int,int>,int>> intervals;
vector<pair<int,int>> withri[500005];

const int BUC = 500;
const int CNTB = 1005;
int prec[CNTB][CNTB];

int solve(int le, int ri)
{
    vector<int> maxsuff(500005,0);
    maxsuff[ri+1] = 0;
    for(int i=ri;i>=le;i--)
    {
        maxsuff[i] = max(maxsuff[i+1], a[i]);
    }
    int rez=0;
    for(auto [x,val]:intervals)
    {
        if(le <= x.first && x.second <= ri)
            rez = max(rez, val + maxsuff[x.second]);
    }
    rez = max(rez, prec[le/CNTB][ri/CNTB]);
    return rez;
}
void calc_toletori()
{
    deque<int> dq;
    for(int i=1;i<=n;i++)
    {
        while(!dq.empty() && a[i] > a[dq.back()])
            dq.pop_back();
        if(dq.empty())
            tole[i] = 0;
        else
            tole[i] = dq.back();
        dq.push_back(i);
    }
    dq.clear();
    for(int i=n;i>0;i--)
    {
        while(!dq.empty() && a[i] > a[dq.back()])
            dq.pop_back();
        if(dq.empty())
            tori[i] = n+1;
        else
            tori[i] = dq.back();
        dq.push_back(i);
    }
}
void get_intervals()
{
    for(int c=1;c<=n;c++)
    {
        int st = tole[c];
        if(st==0)
            continue;
        intervals.push_back({{st, c + (c-st)}, a[c]+a[st]});
    }
    for(int st=1;st<=n;st++)
    {
        int c = tori[st];
        if(c==n+1)
            continue;
        intervals.push_back({{st, c + (c-st)}, a[c]+a[st]});
    }
}


void precalc_sqrt()
{
    for(int ri=0;ri<=n/BUC;ri++)
    {
        int maxsuff=0;
        for(int u=ri*BUC-1;u>0;u--)
        {
            maxsuff = max(maxsuff, a[u]);
            for(auto [ile,ival]:withri[u])
                prec[ile/BUC + 1][ri] = max(prec[ile/BUC + 1][ri], maxsuff + ival);
        }
        for(int le=ri-1;le>=0;le--)
            prec[le][ri] = max(prec[le][ri], prec[le+1][ri]);
    }
}

signed main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    calc_toletori();
    get_intervals();
    for(auto [x,val]:intervals)
        withri[x.second].push_back({x.first,val});
    precalc_sqrt();
    int q;
    cin>>q;
    while(q--)
    {
        int le,ri;
        cin>>le>>ri;
        cout<<solve(le,ri)<<"\n";
    }
    return 0;
}
/*

5
5 2 1 5 3
3
1 4
2 5
1 5



tori[i] = prima pozitie x din dreapta lui i cu a[x] >= a[i]
tole[i] = prima pozitie x din stanga lui i cu a[x] >= a[i]

daca ne fixam capatu stanga in le, centru o sa fie in intervalu le+1..tori[le]

daca ne fixam centru in c, capatu stanga o sa fie in tole[c]..c-1

*/

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