oj.uz

Submission #1096357

# Submission time Handle Problem Language Result Execution time Memory
1096357 2024-10-04T10:48:16 Z DanITK13 Triple Jump (JOI19_jumps) C++14
0 / 100
 152 ms 26256 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Incorrect 1 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Incorrect 1 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 125 ms 26256 KB Output is correct
2 Correct 134 ms 26236 KB Output is correct
3 Correct 152 ms 26240 KB Output is correct
4 Correct 130 ms 26204 KB Output is correct
5 Correct 111 ms 26240 KB Output is correct
6 Correct 88 ms 15332 KB Output is correct
7 Incorrect 94 ms 13920 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Incorrect 1 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -