oj.uz

Submission #944884

# Submission time Handle Problem Language Result Execution time Memory
944884 2024-03-13T07:20:23 Z gelastropod Triple Jump (JOI19_jumps) C++14
19 / 100
 1325 ms 524288 KB 
#include <bits/stdc++.h>
using namespace std;

struct node
{
    int s, e, m, v;
    node *l, *r;

    node(int _s, int _e) : s(_s), e(_e), m((_s + _e) / 2), v(-1)
    {
        if (s != e)
            l = new node(s, m),
            r = new node(m + 1, e);
    }

    void upd(int n, int x)
    {
        if (s == e)
        {
            v = x;
            return;
        }
        if (n <= m)
            l->upd(n, x);
        else
            r->upd(n, x);
        v = max(l->v, r->v);
    }

    int qry(int a, int b)
    {
        if (b < s || a > e)
            return -1;
        if (a <= s && b >= e)
            return v;
        return max(l->qry(a, b), r->qry(a, b));
    }
} *root;

signed main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int N, x, Q, l, r;
    cin >> N;
    vector<int> stiff(N + 5, -1);
    root = new node(0, N + 5);
    for (int i = 0; i < N; i++)
    {
        cin >> x;
        root->upd(i, x);
        stiff[i] = x;
    }
    vector<vector<int>> precomp(N + 5, vector<int>(N + 5, -1)), prefix(N + 5, vector<int>(N + 5, -1)), ans(N, vector<int>(N + 5, -1));
    for (int i = 0; i < N; i++)
    {
        for (int j = i + 2; j < N; j++)
        {
            precomp[i][j] = stiff[i] + stiff[j] + root->qry(i + 1, (i + j) / 2);
        }
    }
    for (int i = N - 1; i >= 0; i--)
    {
        for (int j = i + 2; j < N; j++)
        {
            prefix[i][j] = max(prefix[i + 1][j], precomp[i][j]);
        }
    }
    for (int i = 0; i < N; i++)
    {
        for (int j = i + 2; j < N; j++)
        {
            ans[i][j] = max(ans[i][j - 1], prefix[i][j]);
        }
    }
    cin >> Q;
    for (int i = 0; i < Q; i++)
    {
        cin >> l >> r;
        l--, r--;
        cout << ans[l][r] << '\n';
    }
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1291 ms 304976 KB Output is correct
12 Correct 1293 ms 304980 KB Output is correct
13 Correct 1286 ms 305096 KB Output is correct
14 Correct 1313 ms 305340 KB Output is correct
15 Correct 1278 ms 305152 KB Output is correct
16 Correct 1306 ms 304396 KB Output is correct
17 Correct 1292 ms 304312 KB Output is correct
18 Correct 1325 ms 304316 KB Output is correct
19 Correct 1274 ms 305084 KB Output is correct

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Runtime error 248 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1291 ms 304976 KB Output is correct
12 Correct 1293 ms 304980 KB Output is correct
13 Correct 1286 ms 305096 KB Output is correct
14 Correct 1313 ms 305340 KB Output is correct
15 Correct 1278 ms 305152 KB Output is correct
16 Correct 1306 ms 304396 KB Output is correct
17 Correct 1292 ms 304312 KB Output is correct
18 Correct 1325 ms 304316 KB Output is correct
19 Correct 1274 ms 305084 KB Output is correct
20 Runtime error 248 ms 524288 KB Execution killed with signal 9
21 Halted 0 ms 0 KB -