Submission #746513

#	Time	Username	Problem	Language	Result	Execution time	Memory
746513		GrindMachine	Triple Jump (JOI19_jumps)	C++17	100 / 100	670 ms	111028 KiB

jumps

// Om Namah Shivaya

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

template<typename T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long int ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL)
#define pb push_back
#define endl '\n'
#define sz(a) a.size()
#define setbits(x) __builtin_popcountll(x)
#define ff first
#define ss second
#define conts continue
#define ceil2(x, y) ((x + y - 1) / (y))
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define yes cout << "Yes" << endl
#define no cout << "No" << endl

#define rep(i, n) for(int i = 0; i < n; ++i)
#define rep1(i, n) for(int i = 1; i <= n; ++i)
#define rev(i, s, e) for(int i = s; i >= e; --i)
#define trav(i, a) for(auto &i : a)

template<typename T>
void amin(T &a, T b) {
    a = min(a, b);
}

template<typename T>
void amax(T &a, T b) {
    a = max(a, b);
}

#ifdef LOCAL
#include "debug.h"
#else
#define debug(x) 42
#endif

/*

refs:
https://codeforces.com/blog/entry/68269?#comment-527139
edi


choose l <= a < b < c <= r s.t:
b-a <= c-b
arr[a]+arr[b]+arr[c] is max

let's say we fix (a,b)
when can we consider (a,b) as an option
if there is a guy in between with a higher val, then we dont have to consider pair (a,b)

if there exists k s.t a < k < b with arr[k] >= arr[a] or arr[k] >= arr[b], then we can do this:
arr[k] >= arr[a]: set a = k
arr[k] >= arr[b]: set b = k

by doing this, we reduce the jump distance from a to b
so we have more options for c

in short, consider pair (a,b) only if there is nobody in between with a higher or equal value

how many such pairs are there?

iterate over b from 1 to n and find all valid a

maintain all valid a values when increasing b
once some a becomes bad (some >= guy appears in between), he never becomes good for bigger b

we want to find all a for whom nobody >= them has appeared in [a,b] so far

indices of active set = i1 < i2 < ... < ik
values of active set = arr[i1] > arr[i2] > ... > arr[ik]

(active set is like montonic stack)

what happens to the active set and the good pairs when we move from b-1 to b?

for all guys in the active set with arr[a] <= arr[b], (a,b) is a good pair
but because arr[a] <= arr[b], a can no longer belong to a good pair for bigger values of b
so a is removed from the active set

what about values of a for which arr[a] > arr[b]?
we have removed all values of a for which arr[a] <= arr[b] from the active set
so all guys in the active set have arr[a] > arr[b]

lets look at the largest a (last guy of the active set with the smallest arr[a] val)
he will obviously form a good pair (a,b)

lets look at the 2nd largest a (prev last guy of the active set)
the 2nd largest a does not form a good pair because a comes in between and arr[a] > arr[b] (violates one of our conditions)
same goes for 3rd largest, 4th largest etc

so the only good pair a will be the largest a (or no good pair if active set is empty)

how many good pairs do we have?
+1 every time we pop a guy from active set
+1 for arr[a] > arr[b] 

so the #of good pairs is bounded by 2n = O(n)

so we have O(n) good pairs to consider for each query

how to ans queries

we can answer queries offline using sweepline

sweep by decreasing l value

when we are at a given l val, consider all pairs with a = l
for this pair, c must be >= b+(b-a) 
for a given value of c >= 2b-a, if we use pair (a,b), we get value (arr[a] + arr[b]) + arr[c]

in a segtree, we put the value arr[a] + arr[b] at pos 2b-a
we do this for all pairs

then if we pick c, max val = arr[c] + max(arr[a] + arr[b]) on pref

this can be computed quickly with segtree 

*/

const int MOD = 1e9 + 7;
const int N = 1e5 + 5;
const int inf1 = int(1e9) + 5;
const ll inf2 = ll(1e18) + 5;

template<typename T>
struct segtree {
    // https://codeforces.com/blog/entry/18051

    /*=======================================================*/

    struct data {
        ll mx1, mx2, res;
    };

    data neutral = {-inf2, -inf2, -inf2};

    data merge(data &left, data &right) {
        data curr;
        
        curr.mx1 = max(left.mx1,right.mx1);
        curr.mx2 = max(left.mx2,right.mx2);
        curr.res = max({left.res, right.res, left.mx2 + right.mx1});
        
        return curr;
    }

    void create(int i, T v) {
        tr[i].mx1 = v;
    }

    void modify(int i, T v) {
        amax(tr[i].mx2, v);
        tr[i].res = tr[i].mx1 + tr[i].mx2;
    }

    /*=======================================================*/

    int n;
    vector<data> tr;

    segtree() {

    }

    segtree(int siz) {
        init(siz);
    }

    void init(int siz) {
        n = siz;
        tr.assign(2 * n, neutral);
    }

    void build(vector<T> &a, int siz) {
        rep(i, siz) create(i + n, a[i]);
        rev(i, n - 1, 1) tr[i] = merge(tr[i << 1], tr[i << 1 | 1]);
    }

    void pupd(int i, T v) {
        modify(i + n, v);
        for (i = (i + n) >> 1; i; i >>= 1) tr[i] = merge(tr[i << 1], tr[i << 1 | 1]);
    }

    data query(int l, int r) {
        data resl = neutral, resr = neutral;

        for (l += n, r += n; l <= r; l >>= 1, r >>= 1) {
            if (l & 1) resl = merge(resl, tr[l++]);
            if (!(r & 1)) resr = merge(tr[r--], resr);
        }

        return merge(resl, resr);
    }
};

void solve(int test_case)
{
    ll n; cin >> n;
    vector<ll> arr(n+5);
    rep1(i,n) cin >> arr[i];

    vector<ll> good;
    vector<pll> pairs;

    rep1(b,n){
        while(!good.empty() and arr[b] >= arr[good.back()]){
            pairs.pb({good.back(), b});
            good.pop_back();
        }

        if(!good.empty()){
            pairs.pb({good.back(), b});
        }

        good.pb(b);
    }

    vector<ll> enter[n+5];
    for(auto [a,b] : pairs){
        enter[a].pb(b);
    }

    ll q; cin >> q;
    vector<pll> queries[n+5];

    rep1(i,q){
        ll l,r; cin >> l >> r;
        queries[l].pb({r, i});
    }

    vector<ll> ans(q+5);
    segtree<ll> st(n+5);
    st.build(arr,n+1);

    rev(l,n,1){
        trav(b,enter[l]){
            ll dis = b - l;
            ll c = b + dis;
            if(c <= n){
                st.pupd(c, arr[l] + arr[b]);
            }
        }

        for(auto [r, id] : queries[l]){
            ans[id] = st.query(l,r).res;
        }
    }

    rep1(i,q) cout << ans[i] << endl;
}

int main()
{
    fastio;

    int t = 1;
    // cin >> t;

    rep1(i, t) {
        solve(i);
    }

    return 0;
}

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