Submission #1190925

#	Time	Username	Problem	Language	Result	Execution time	Memory
1190925		alexdd	Triple Jump (JOI19_jumps)	C++20	100 / 100	680 ms	99208 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 max_init[1100000],max_now[1100000],max_justnow[1100000],lazy[1100000];
void build(int nod, int st, int dr)
{
    max_now[nod] = max_justnow[nod] = -INF;
    if(st==dr)
    {
        max_init[nod] = a[st];
        return;
    }
    int mij=(st+dr)/2;
    build(nod*2,st,mij);
    build(nod*2+1,mij+1,dr);
    max_init[nod] = max(max_init[nod*2], max_init[nod*2+1]);
}
void apply(int nod, int lazy_val)
{
    lazy[nod] = lazy_val;
    max_now[nod] = max_init[nod] + lazy_val;
    max_justnow[nod] = lazy_val;
}
void propagate(int nod)
{
    if(!lazy[nod])
        return;
    apply(nod*2,lazy[nod]);
    apply(nod*2+1,lazy[nod]);
    lazy[nod] = 0;
}
void upd_assign(int nod, int st, int dr, int le, int ri, int newv)
{
    if(le>ri)
        return;
    if(le==st && dr==ri)
    {
        apply(nod,newv);
        return;
    }
    propagate(nod);
    int mij=(st+dr)/2;
    upd_assign(nod*2,st,mij,le,min(mij,ri),newv);
    upd_assign(nod*2+1,mij+1,dr,max(mij+1,le),ri,newv);
    max_now[nod] = max(max_now[nod*2], max_now[nod*2+1]);
    max_justnow[nod] = max(max_justnow[nod*2], max_justnow[nod*2+1]);
}
int qry(int nod, int st, int dr, int le, int ri)
{
    if(le>ri)
        return -INF;
    if(le==st && dr==ri)
        return max_now[nod];
    propagate(nod);
    int mij=(st+dr)/2;
    return max(qry(nod*2,st,mij,le,min(mij,ri)), qry(nod*2+1,mij+1,dr,max(mij+1,le),ri));
}
int cautare_binara(int nod, int st, int dr, int newv)
{
    if(st==dr)
    {
        if(max_justnow[nod] < newv)
            return n+1;
        return st;
    }
    propagate(nod);
    int mij=(st+dr)/2;
    if(max_justnow[nod*2] < newv)
        return cautare_binara(nod*2+1,mij+1,dr,newv);
    else
        return cautare_binara(nod*2,st,mij,newv);
}

void update(int le, int newv)
{
    int ri = cautare_binara(1,1,n,newv);
    upd_assign(1,1,n,le,ri-1,newv);
}
int query(int ri)
{
    return qry(1,1,n,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)
        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});
    }
    build(1,1,n);
    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;
}

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