oj.uz

Submission #945177

# Submission time Handle Problem Language Result Execution time Memory
945177 2024-03-13T13:36:12 Z hmm789 Triple Jump (JOI19_jumps) C++14
19 / 100
 2220 ms 524288 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 1000000000000000000
//#define INF 1000000000
#define MOD 998244353

struct node {
    int s, e, m, v;
    node *l, *r;
    node(int _s, int _e) {
        s = _s, e = _e, m = (s+e)/2, v = 0;
        if(s != e) {
            l = new node(s, m);
            r = new node(m+1, e);
        }
    }
    void update(int x, int val) {
        if(s == e) {v = max(v, val); return;}
        else if(x > m) r->update(x, val);
        else l->update(x, val);
        v = max(l->v, r->v);
    }
    int rmax(int x, int y) {
        if(x <= s && e <= y) return v;
        else if(x > m) return r->rmax(x, y);
        else if(y <= m) return l->rmax(x, y);
        else return max(l->rmax(x, y), r->rmax(x, y));
    }
} *root;

int32_t main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int n, q, x, y;
    cin >> n;
    int a[n], mx[n+1][n+1], ans[n][n];
    for(int i = 0; i < n; i++) cin >> a[i];
    for(int j = 0; j < n; j++) {
        mx[j][j] = a[j];
        for(int i = j-1; i >= 0; i--) {
            mx[i][j] = max(mx[i+1][j], a[i]);
        }
        for(int i = j+1; i <= n; i++) mx[i][j] = 0;
    }
    root = new node(0, n-1);
    for(int i = 2; i < n; i++) {
        for(int j = i-2; j >= 0; j--) {
            root->update(j, a[j] + mx[j+1][(i+j)/2] + a[i]);
            ans[j][i] = root->rmax(j, i);
        }
    }
    cin >> q;
    while(q--) {
        cin >> x >> y;
        x--; y--;
        cout << ans[x][y] << '\n';
    }
}

Subtask #1
5.0 / 5.0

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

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 600 KB Output is correct
2 Correct 1 ms 600 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 1 ms 600 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 1 ms 452 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 2214 ms 402676 KB Output is correct
12 Correct 2220 ms 402148 KB Output is correct
13 Correct 2185 ms 402548 KB Output is correct
14 Correct 2177 ms 402196 KB Output is correct
15 Correct 2207 ms 402144 KB Output is correct
16 Correct 2180 ms 401380 KB Output is correct
17 Correct 2218 ms 401492 KB Output is correct
18 Correct 2195 ms 401372 KB Output is correct
19 Correct 2215 ms 402156 KB Output is correct

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Runtime error 267 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 0 ms 600 KB Output is correct
2 Correct 1 ms 600 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 1 ms 600 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 1 ms 452 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 2214 ms 402676 KB Output is correct
12 Correct 2220 ms 402148 KB Output is correct
13 Correct 2185 ms 402548 KB Output is correct
14 Correct 2177 ms 402196 KB Output is correct
15 Correct 2207 ms 402144 KB Output is correct
16 Correct 2180 ms 401380 KB Output is correct
17 Correct 2218 ms 401492 KB Output is correct
18 Correct 2195 ms 401372 KB Output is correct
19 Correct 2215 ms 402156 KB Output is correct
20 Runtime error 267 ms 524288 KB Execution killed with signal 9
21 Halted 0 ms 0 KB -