Submission #968640

#	Time	Username	Problem	Language	Result	Execution time	Memory
968640		vyshniak_n	Triple Jump (JOI19_jumps)	C++17	100 / 100	850 ms	110544 KiB

jumps

//#pragma optimize("Ofast")
//#pragma optimize("unroll-loops")
//#pragma traget("avx,avx2")

#include <iostream>
#include <cmath>
#include <algorithm>
#include <stdio.h>
#include <cstdint>
#include <cstring>
#include <string>
#include <cstdlib>
#include <vector>
#include <bitset>
#include <map>
#include <queue>
#include <ctime>
#include <stack>
#include <set>
#include <list>
#include <random>
#include <deque>
#include <functional>
#include <iomanip>
#include <sstream>
#include <fstream>
#include <complex>
#include <numeric>
#include <cassert>
#include <array>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <thread>

typedef long long ll;
typedef long double ld;

#define el '\n'
#define ff first
#define ss second
#define pb push_back
#define pf push_front
#define popb pop_back
#define popf pop_front
#define point pair <ll, ll>
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()

using namespace std;

const ll INF = 2e18 + 10;
const ll inf = 2e9 + 10;
const ll N = 5e5 + 10;
const ll mod = 1e9 + 7;
const ll K = 200;
const ll LOG = 16;

ll a[N], t[4 * N], lazy[4 * N], mx[4 * N], ans[N];
vector <point> Q[N];
vector <ll> gr[N];

void build(ll v, ll tl, ll tr) {
    if (tl == tr) {
        t[v] = a[tl];
        mx[v] = -INF;
        return;
    }

    ll tm = (tl + tr) >> 1;

    build(v << 1, tl, tm);
    build(v << 1 | 1, tm + 1, tr);

    t[v] = max(t[v << 1], t[v << 1 | 1]);
    mx[v] = -INF;
}
void push(ll v) {
    mx[v << 1] = max(mx[v << 1], t[v << 1] + lazy[v]);
    mx[v << 1 | 1] = max(mx[v << 1 | 1], t[v << 1 | 1] + lazy[v]);

    lazy[v << 1] = max(lazy[v << 1], lazy[v]);
    lazy[v << 1 | 1] = max(lazy[v << 1 | 1], lazy[v]);

    lazy[v] = 0;
}
void upd(ll v, ll tl, ll tr, ll l, ll r, ll val) {
    if (l > tr || r < tl || r < l)
        return;
    if (l <= tl && r >= tr) {
        mx[v] = max(mx[v], t[v] + val);
        lazy[v] = max(lazy[v], val);
        return;
    }

    push(v);
    ll tm = (tl + tr) >> 1;

    upd(v << 1, tl, tm, l, r, val);
    upd(v << 1 | 1, tm + 1, tr, l, r, val);

    mx[v] = max(mx[v << 1], mx[v << 1 | 1]);
}
ll get(ll v, ll tl, ll tr, ll l, ll r) {
    if (l > tr || r < tl || r < l)
        return -INF;
    if (l <= tl && r >= tr)
        return mx[v];

    push(v);
    ll tm = (tl + tr) >> 1;

    return max(get(v << 1, tl, tm, l, r),
               get(v << 1 | 1, tm + 1, tr, l, r));
}

void solve() {
    ll n;
    cin >> n;

    for (ll i = 1; i <= n; i++)
        cin >> a[i];

    build(1, 1, n);

    ll q;
    cin >> q;

    for (ll i = 0; i < q; i++) {
        ll l, r;
        cin >> l >> r;

        if (r - l + 1 < 3)
            continue;

        Q[l].pb({r, i});
    }

    stack <ll> st;
    for (ll i = 1; i <= n; i++) {
        while (!st.empty() && a[st.top()] < a[i]) {
            gr[st.top()].pb(i);
            st.pop();
        }

        if (!st.empty())
            gr[st.top()].pb(i);

        st.push(i);
    }

    for (ll i = n; i >= 1; i--) {
        for (ll v : gr[i])
            upd(1, 1, n, v + v - i, n, a[i] + a[v]);

        for (point cur : Q[i])
            ans[cur.ss] = get(1, 1, n, i, cur.ff);
    }

    for (ll i = 0; i < q; i++)
        cout << ans[i] << el;
    return;
}
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int tests = 1;
    //cin >> tests;

    while (tests--) 
        solve();
    return 0;
}
/*
*/

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