oj.uz

Submission #968640

# Submission time Handle Problem Language Result Execution time Memory
968640 2024-04-23T19:01:54 Z vyshniak_n Triple Jump (JOI19_jumps) C++17
100 / 100
 850 ms 110544 KB 
//#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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 31324 KB Output is correct
2 Correct 8 ms 31320 KB Output is correct
3 Correct 8 ms 31324 KB Output is correct
4 Correct 8 ms 31320 KB Output is correct
5 Correct 8 ms 31320 KB Output is correct
6 Correct 7 ms 31324 KB Output is correct
7 Correct 7 ms 31324 KB Output is correct
8 Correct 7 ms 31360 KB Output is correct
9 Correct 7 ms 31328 KB Output is correct
10 Correct 7 ms 31328 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 31324 KB Output is correct
2 Correct 8 ms 31320 KB Output is correct
3 Correct 8 ms 31324 KB Output is correct
4 Correct 8 ms 31320 KB Output is correct
5 Correct 8 ms 31320 KB Output is correct
6 Correct 7 ms 31324 KB Output is correct
7 Correct 7 ms 31324 KB Output is correct
8 Correct 7 ms 31360 KB Output is correct
9 Correct 7 ms 31328 KB Output is correct
10 Correct 7 ms 31328 KB Output is correct
11 Correct 274 ms 56492 KB Output is correct
12 Correct 257 ms 56664 KB Output is correct
13 Correct 225 ms 56596 KB Output is correct
14 Correct 264 ms 56608 KB Output is correct
15 Correct 279 ms 56604 KB Output is correct
16 Correct 232 ms 55888 KB Output is correct
17 Correct 307 ms 56008 KB Output is correct
18 Correct 260 ms 55968 KB Output is correct
19 Correct 221 ms 56616 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 129 ms 52116 KB Output is correct
2 Correct 83 ms 50948 KB Output is correct
3 Correct 76 ms 52484 KB Output is correct
4 Correct 126 ms 52220 KB Output is correct
5 Correct 120 ms 52056 KB Output is correct
6 Correct 131 ms 51900 KB Output is correct
7 Correct 120 ms 51780 KB Output is correct
8 Correct 133 ms 51744 KB Output is correct
9 Correct 140 ms 52016 KB Output is correct

Subtask #4
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 31324 KB Output is correct
2 Correct 8 ms 31320 KB Output is correct
3 Correct 8 ms 31324 KB Output is correct
4 Correct 8 ms 31320 KB Output is correct
5 Correct 8 ms 31320 KB Output is correct
6 Correct 7 ms 31324 KB Output is correct
7 Correct 7 ms 31324 KB Output is correct
8 Correct 7 ms 31360 KB Output is correct
9 Correct 7 ms 31328 KB Output is correct
10 Correct 7 ms 31328 KB Output is correct
11 Correct 274 ms 56492 KB Output is correct
12 Correct 257 ms 56664 KB Output is correct
13 Correct 225 ms 56596 KB Output is correct
14 Correct 264 ms 56608 KB Output is correct
15 Correct 279 ms 56604 KB Output is correct
16 Correct 232 ms 55888 KB Output is correct
17 Correct 307 ms 56008 KB Output is correct
18 Correct 260 ms 55968 KB Output is correct
19 Correct 221 ms 56616 KB Output is correct
20 Correct 129 ms 52116 KB Output is correct
21 Correct 83 ms 50948 KB Output is correct
22 Correct 76 ms 52484 KB Output is correct
23 Correct 126 ms 52220 KB Output is correct
24 Correct 120 ms 52056 KB Output is correct
25 Correct 131 ms 51900 KB Output is correct
26 Correct 120 ms 51780 KB Output is correct
27 Correct 133 ms 51744 KB Output is correct
28 Correct 140 ms 52016 KB Output is correct
29 Correct 848 ms 108016 KB Output is correct
30 Correct 673 ms 104896 KB Output is correct
31 Correct 700 ms 108884 KB Output is correct
32 Correct 812 ms 108076 KB Output is correct
33 Correct 826 ms 108484 KB Output is correct
34 Correct 848 ms 105880 KB Output is correct
35 Correct 835 ms 105472 KB Output is correct
36 Correct 850 ms 105512 KB Output is correct
37 Correct 822 ms 106812 KB Output is correct
38 Correct 556 ms 110544 KB Output is correct
39 Correct 548 ms 110352 KB Output is correct
40 Correct 538 ms 107560 KB Output is correct
41 Correct 533 ms 106660 KB Output is correct
42 Correct 528 ms 106580 KB Output is correct
43 Correct 593 ms 108476 KB Output is correct
44 Correct 595 ms 110164 KB Output is correct
45 Correct 651 ms 110160 KB Output is correct
46 Correct 578 ms 107348 KB Output is correct
47 Correct 571 ms 106580 KB Output is correct
48 Correct 589 ms 106556 KB Output is correct
49 Correct 584 ms 108664 KB Output is correct
50 Correct 654 ms 109392 KB Output is correct
51 Correct 639 ms 109396 KB Output is correct
52 Correct 721 ms 107024 KB Output is correct
53 Correct 652 ms 106580 KB Output is correct
54 Correct 659 ms 106576 KB Output is correct
55 Correct 673 ms 108372 KB Output is correct