제출 #1190912

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1190912		alexdd	Triple Jump (JOI19_jumps)	C++20	19 / 100	4093 ms	39016 KiB

jumps

#include <bits/stdc++.h>
using namespace std;
const int INF = 4e8;
int n;
int a[500005];
int tole[500005],tori[500005];
vector<pair<pair<int,int>,int>> intervals;
vector<pair<int,int>> withle[500005];
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]});
    }
}

vector<pair<int,int>> qrys[500005];
int rez[500005];

int v[500005];
void init()
{
    for(int i=1;i<=n;i++)
        v[i] = -INF;
}
void update(int le, int newv)
{
    for(int i=le;i<=n;i++)
        v[i] = max(v[i], newv);
}
int query(int ri)
{
    int aux=0;
    for(int i=1;i<=ri;i++)
        aux = max(aux, v[i] + a[i]);
    return aux;
}

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)
        withle[x.first].push_back({x.second,val});
    int q;
    cin>>q;
    for(int i=0;i<q;i++)
    {
        int le,ri;
        cin>>le>>ri;
        qrys[le].push_back({ri,i});
    }
    init();
    for(int le=n;le>=1;le--)
    {
        for(auto [ri,val]:withle[le])
        {
            update(ri,val);
        }
        for(auto [ri,id]:qrys[le])
        {
            rez[id] = query(ri);
        }
    }
    for(int i=0;i<q;i++)
        cout<<rez[i]<<"\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: 14 / 14
• Subtask 3: 0 / 27
• Subtask 4: 0 / 54