Submission #1169527

#	Time	Username	Problem	Language	Result	Execution time	Memory
1169527		mousebeaver	Triple Jump (JOI19_jumps)	C++20	100 / 100	1025 ms	69100 KiB

jumps

#define ll long long
#define subINF numeric_limits<ll>::min()/2
#define pll pair<ll, ll>
#define ppl pair<pll, ll>
#include <bits/stdc++.h>
using namespace std;

ll left(ll i)
    {return 2*i;}

ll right(ll i)
    {return 2*i+1;}

void push(vector<pll>& s, ll i, vector<ll>& topush)
{
    if(left(i) >= (ll) s.size())
        return;
    
    topush[left(i)] = max(topush[left(i)], topush[i]);
    topush[right(i)] = max(topush[right(i)], topush[i]);
}

void update(vector<pll>& s, ll i, vector<ll>& topush)
{
    s[i].second = max(s[i].second, s[i].first+topush[i]);

    if(left(i) >= (ll) s.size())
        return;
    
    s[i].second = max(s[i].second, max(s[left(i)].second, s[right(i)].second));
}

ll query(vector<pll>& s, ll i, ll a, ll b, ll l, ll r, vector<ll>& topush)
{
    push(s, i, topush);
    update(s, i, topush);

    if(l <= a && b <= r)
        return s[i].second;
    if(r < a || b < l)
        return 0;
    
    ll mid = (a+b)/2;
    return max(query(s, left(i), a, mid, l, r, topush), query(s, right(i), mid+1, b, l, r, topush));
}

void apply(vector<pll>& s, ll i, ll a, ll b, ll l, ll r, ll val, vector<ll>& topush)
{
    if(l <= a && b <= r)
    {
        topush[i] = max(topush[i], val);
        push(s, i, topush);
        update(s, i, topush);
        return;
    }
    if(r < a || b < l)
        return;
    
    ll mid = (a+b)/2;
    apply(s, left(i), a, mid, l, r, val, topush);
    apply(s, right(i), mid+1, b, l, r, val, topush);
    push(s, i, topush);
    update(s, i, topush);
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    ll n;
    cin>>n;
    vector<ll> a(n);
    for(ll& i : a)
        cin>>i;

    //Compute candidate pairs for a and b (All values in between are smaller than them):
    vector<pll> candidates(0);
    vector<ll> pre = {0}; //Greater than everything after that (index)  
    vector<ll> dp(n, 0); //Greatest usable pair of a, b if dp[i] is c
    for(ll j = 1; j < n; j++)
    {
        ll p = pre.size();
        for(ll i = 0; i < p; i++)
        {
            ll ind = pre[p-i-1];
            ll minc = 2*(j+1) - (ind+1);
            if(minc > n)
                continue;
            candidates.push_back({ind+1, j+1});

            if(a[ind] >= a[j])
                break;
        }

        while(pre.size() && a[pre.back()] <= a[j])
            pre.pop_back();
        pre.push_back(j);
    }

    //Segment tree of pairs: Value of c, best sum of a and b before that    
    ll segnodes = 1;
    while(2*n > segnodes)
        segnodes *= 2;

    vector<pll> s(segnodes, {0, subINF}); //Value c, best value a+b+c.
    vector<ll> topush(segnodes, subINF);
    for(ll i = 0; i < n; i++)
        s[segnodes/2 + i].first = a[i];
    for(ll i = segnodes/2 - 1; i > 0; i--)
    {
        s[i].first = max(s[left(i)].first, s[right(i)].first);
        update(s, i, topush);
    }

    //Read queries
    ll q;
    cin>>q;
    vector<ppl> r(q);
    for(ll i = 0; i < q; i++)
    {
        cin>>r[i].first.first>>r[i].first.second;
        r[i].second = i;
    }

    sort(r.begin(), r.end());
    sort(candidates.begin(), candidates.end());
    vector<ll> output(q);

    for(ll i = n; i >= 1; i--)
    {
        while(candidates.size() && candidates.back().first == i)
        {
            ll first = candidates.back().first;
            ll second = candidates.back().second;
            if(2*second-first <= n)
            {
                apply(s, 1, 1, segnodes/2, 2*second-first, segnodes/2, a[first-1]+a[second-1], topush);
            }
            candidates.pop_back();
        }

        while(r.size() && r.back().first.first == i)
        {
            output[r.back().second] = query(s, 1, 1, segnodes/2, r.back().first.first, r.back().first.second, topush);
            r.pop_back();
        }
    }

    for(ll i : output)
        cout<<i<<"\n";
}

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