제출 #1190757

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

jumps

#include <bits/stdc++.h>
using namespace std;
int n;
int a[500005];
int tole[500005],tori[500005],maxsuff[500005];
vector<pair<pair<int,int>,int>> intervals;
int solve(int le, int ri)
{
    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]);
    }
    return rez;
}
void calc_toletori()
{
    for(int i=1;i<=n;i++)
    {
        tole[i] = 0;
        for(int u=i-1;u>=1;u--)
        {
            if(a[u] >= a[i])
            {
                tole[i] = u;
                break;
            }
        }
        tori[i] = n+1;
        for(int u=i+1;u<=n;u++)
        {
            if(a[u] >= a[i])
            {
                tori[i] = u;
                break;
            }
        }
    }
}
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]});
    }
}
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();
    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: 0 / 27
• Subtask 4: 0 / 54