Submission #1096357

#	Time	Username	Problem	Language	Result	Execution time	Memory
1096357		DanITK13	Triple Jump (JOI19_jumps)	C++14	0 / 100	152 ms	26256 KiB

jumps

#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define FOR(i, a, n) for (int i = a; i <= n; i++)
#define fast ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
#define fi first
#define se second
#define run signed main()
#define pb push_back
const ll N = 500005;

ll st[N*4], a[N], n, q, l, r;

void build(ll i, ll l, ll r) {
    if (l == r) {
        st[i] = a[l];
        return;
    }

    ll mid = (l + r) / 2;
    build(i*2, l, mid);
    build(i*2+1, mid+1, r);
    st[i] = max(st[i*2], st[i*2+1]);
}

ll get(ll i, ll l, ll r, ll u, ll v) {
    if (l > v || r < u) return -1e16;
    if (l >= u && r <= v) return st[i];

    ll mid = (l + r) / 2;
    ll get1 = get(i*2, l, mid, u, v);
    ll get2 = get(i*2+1, mid+1, r, u, v);
    return max(get1, get2);
}

void solve(ll l, ll r) {
    ll res = 0;
    unordered_map<ll, vector<ll>> d;
    FOR(i, l, r) d[a[i]].pb(i);

    FOR(i, l, r - 2) {
        ll x = get(1, 1, n, i + 1, i + (r - i) / 2);
        vector<ll> p = d[x];
//        cout<<x<<' ';
//        for (int j : d[x]) cout<<j<<' ';
//        cout<<'\n';
        auto v = lower_bound(p.begin(), p.end(), i) - p.begin();
//        cout<<v<<'\n';
        ll y = get(1, 1, n, p[v] + 1, r);
//        cout<<a[i]+x+y<<'\n';
        res = max(res, a[i] + x + y);
    }
    cout<<res<<'\n';
}

run {
    fast
    cin>>n;
    FOR(i, 1, n) cin>>a[i];
    build(1, 1, n);
    cin>>q;
    while (q--) {
        cin>>l>>r;
        solve(l, r);
    }
}

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