oj.uz

Submission #746513

# Submission time Handle Problem Language Result Execution time Memory
746513 2023-05-22T15:42:45 Z GrindMachine Triple Jump (JOI19_jumps) C++17
100 / 100
 670 ms 111028 KB 
// 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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 320 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 0 ms 316 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 324 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 1 ms 320 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 320 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 0 ms 316 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 324 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 1 ms 320 KB Output is correct
11 Correct 242 ms 23952 KB Output is correct
12 Correct 166 ms 23752 KB Output is correct
13 Correct 177 ms 23952 KB Output is correct
14 Correct 183 ms 23940 KB Output is correct
15 Correct 175 ms 24144 KB Output is correct
16 Correct 205 ms 23384 KB Output is correct
17 Correct 230 ms 23380 KB Output is correct
18 Correct 178 ms 23196 KB Output is correct
19 Correct 190 ms 23876 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 35056 KB Output is correct
2 Correct 76 ms 30604 KB Output is correct
3 Correct 68 ms 32292 KB Output is correct
4 Correct 138 ms 35064 KB Output is correct
5 Correct 114 ms 35044 KB Output is correct
6 Correct 97 ms 35064 KB Output is correct
7 Correct 104 ms 35040 KB Output is correct
8 Correct 100 ms 35188 KB Output is correct
9 Correct 99 ms 35072 KB Output is correct

Subtask #4
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 320 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 0 ms 316 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 324 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 1 ms 320 KB Output is correct
11 Correct 242 ms 23952 KB Output is correct
12 Correct 166 ms 23752 KB Output is correct
13 Correct 177 ms 23952 KB Output is correct
14 Correct 183 ms 23940 KB Output is correct
15 Correct 175 ms 24144 KB Output is correct
16 Correct 205 ms 23384 KB Output is correct
17 Correct 230 ms 23380 KB Output is correct
18 Correct 178 ms 23196 KB Output is correct
19 Correct 190 ms 23876 KB Output is correct
20 Correct 99 ms 35056 KB Output is correct
21 Correct 76 ms 30604 KB Output is correct
22 Correct 68 ms 32292 KB Output is correct
23 Correct 138 ms 35064 KB Output is correct
24 Correct 114 ms 35044 KB Output is correct
25 Correct 97 ms 35064 KB Output is correct
26 Correct 104 ms 35040 KB Output is correct
27 Correct 100 ms 35188 KB Output is correct
28 Correct 99 ms 35072 KB Output is correct
29 Correct 606 ms 107968 KB Output is correct
30 Correct 563 ms 96964 KB Output is correct
31 Correct 604 ms 100884 KB Output is correct
32 Correct 608 ms 107960 KB Output is correct
33 Correct 670 ms 107964 KB Output is correct
34 Correct 573 ms 107336 KB Output is correct
35 Correct 639 ms 107204 KB Output is correct
36 Correct 629 ms 107276 KB Output is correct
37 Correct 642 ms 107920 KB Output is correct
38 Correct 408 ms 110656 KB Output is correct
39 Correct 408 ms 110648 KB Output is correct
40 Correct 415 ms 108932 KB Output is correct
41 Correct 392 ms 108572 KB Output is correct
42 Correct 424 ms 108632 KB Output is correct
43 Correct 412 ms 109536 KB Output is correct
44 Correct 454 ms 110816 KB Output is correct
45 Correct 424 ms 110884 KB Output is correct
46 Correct 443 ms 109244 KB Output is correct
47 Correct 410 ms 109072 KB Output is correct
48 Correct 431 ms 109160 KB Output is correct
49 Correct 448 ms 110320 KB Output is correct
50 Correct 497 ms 111012 KB Output is correct
51 Correct 491 ms 111028 KB Output is correct
52 Correct 489 ms 110120 KB Output is correct
53 Correct 487 ms 110124 KB Output is correct
54 Correct 488 ms 110060 KB Output is correct
55 Correct 463 ms 110876 KB Output is correct