Submission #1161665

#	Time	Username	Problem	Language	Result	Execution time	Memory
1161665		sofija6	Triple Jump (JOI19_jumps)	C++20	100 / 100	912 ms	96332 KiB

jumps

#include <bits/stdc++.h>
#define ll long long
#define MAXN 500010
using namespace std;
ll n,sz,a[MAXN],ans[MAXN];
vector<ll> p[MAXN];
vector<pair<ll,ll> > queries[MAXN];
struct element
{
    ll sum,maxx;
};
element neutral={0,0};
element Merge(element x,element y)
{
    return {max(x.sum,y.sum),max(x.maxx,y.maxx)};
}
struct seg_tree
{
    vector<element> st;
    vector<ll> lazy;
    void Init()
    {
        sz=1;
        while (sz<n)
            sz <<= 1;
        st.resize(2*sz+2,neutral);
        lazy.resize(2*sz+2);
    }
    void Build()
    {
        for (ll i=sz;i<sz+n;i++)
            st[i]={0,a[i-sz+1]};
        for (ll i=sz-1;i>0;i--)
            st[i]=Merge(st[2*i],st[2*i+1]);
    }
    void Propagate(ll x)
    {
        st[x].sum=max(st[x].sum,lazy[x]+st[x].maxx);
        if (x<sz)
        {
            lazy[2*x]=max(lazy[2*x],lazy[x]);
            lazy[2*x+1]=max(lazy[2*x+1],lazy[x]);
        }
        lazy[x]=0;
    }
    void Update(ll l,ll r,ll val,ll x,ll lx,ll rx)
    {
        Propagate(x);
        if (lx>r || rx<l)
            return;
        if (lx>=l && rx<=r)
        {
            lazy[x]=val;
            Propagate(x);
            return;
        }
        ll mid=(lx+rx)/2;
        Update(l,r,val,2*x,lx,mid);
        Update(l,r,val,2*x+1,mid+1,rx);
        st[x]=Merge(st[2*x],st[2*x+1]);
    }
    ll Calc(ll l,ll r,ll x,ll lx,ll rx)
    {
        Propagate(x);
        if (lx>r || rx<l)
            return 0;
        if (lx>=l && rx<=r)
            return st[x].sum;
        ll mid=(lx+rx)/2;
        return max(Calc(l,r,2*x,lx,mid),Calc(l,r,2*x+1,mid+1,rx));
    }
};
seg_tree S;
int main()
{
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    ll q,l,r;
    cin >> n;
    for (ll i=1;i<=n;i++)
        cin >> a[i];
    stack<ll> s;
    for (ll i=n;i>0;i--)
    {
        while (!s.empty() && a[s.top()]<=a[i])
        {
            p[i].push_back(s.top());
            s.pop();
        }
        if (!s.empty())
            p[i].push_back(s.top());
        s.push(i);
    }
    cin >> q;
    for (ll i=1;i<=q;i++)
    {
        cin >> l >> r;
        queries[l].push_back({r,i});
    }
    S.Init();
    S.Build();
    for (ll i=n;i>0;i--)
    {
        for (ll j : p[i])
        {
            if (2*j-i<=n)
                S.Update(2*j-i,n,a[i]+a[j],1,1,sz);
        }
        for (auto j : queries[i])
            ans[j.second]=S.Calc(i,j.first,1,1,sz);
    }
    for (ll i=1;i<=q;i++)
        cout << ans[i] << "\n";
    return 0;
}

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