oj.uz

Submission #970241

# Submission time Handle Problem Language Result Execution time Memory
970241 2024-04-26T09:10:21 Z efedmrlr Triple Jump (JOI19_jumps) C++17
19 / 100
 523 ms 524288 KB 
#include <bits/stdc++.h>

#define int long long int
#define pb push_back
#define MP make_pair
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define REP(i, n) for(int i = 0; (i) < (n); (i)++)
#define ld long double

using namespace std;

void fastio() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
}

const int N = 5e5 + 5;
const int INF = 1e9 + 500;
const int LGN = 20;
array<int, N> lg2;
struct RMQ {
    array<vector<int>, LGN> st;
    void reset(int s, vector<int> &arr) {
        REP(i, LGN) st[i].assign(s + 3, 0);
        for(int i = 1; i <= s; i++) {
            st[0][i] = arr[i];
        }
        for(int k = 1; k < LGN; k++) {
            for(int i = 1; i <= s; i++) {
                if(i + (1 << (k - 1)) > s) break;
                st[k][i] = max(st[k - 1][i], st[k - 1][i + (1 << (k - 1))]);
            }
        }
    }
    int query(int l, int r) {
        int k = lg2[r - l + 1];
        return max(st[k][l], st[k][r - (1 << k) + 1]);
    }
};

int n, q;
vector<int> a;
RMQ st;
vector<int> res;
vector<vector<int> > ans;
void solve() {
    cin >> n;
    a.resize(n + 1, 0);
    ans.assign(n + 1, vector<int>(n + 1, 0));
    for(int i = 1; i<=n; i++) {
        cin >> a[i];
    }
    st.reset(n, a);
    for(int i = 1; i <= n; i++) {
        for(int j = i + 2; j <= n; j++) {
            int tm = (i + j) >> 1;
            ans[i][j] = st.query(i + 1, tm) + a[i] + a[j];
        }
    }
    for(int len = 3; len <= n; len++) {
        for(int i = 1; i <= n; i++) {
            int j = i + len - 1;
            if(j > n) break;
            ans[i][j] = max(ans[i][j], ans[i + 1][j]);
            ans[i][j] = max(ans[i][j], ans[i][j - 1]);
        }
    }
    cin >> q;
    REP(i, q) {
        int l, r;
        cin >> l >> r;
        cout << ans[l][r] << "\n";
    }

}

signed main() {
    lg2[1] = 0;
    for(int i = 2; i < N; i++) {
        lg2[i] = lg2[i >> 1] + 1;
    }
    fastio();
    solve();
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4188 KB Output is correct
2 Correct 2 ms 4444 KB Output is correct
3 Correct 2 ms 4476 KB Output is correct
4 Correct 2 ms 4444 KB Output is correct
5 Correct 2 ms 4444 KB Output is correct
6 Correct 2 ms 4444 KB Output is correct
7 Correct 2 ms 4444 KB Output is correct
8 Correct 2 ms 4444 KB Output is correct
9 Correct 2 ms 4444 KB Output is correct
10 Correct 2 ms 4452 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4188 KB Output is correct
2 Correct 2 ms 4444 KB Output is correct
3 Correct 2 ms 4476 KB Output is correct
4 Correct 2 ms 4444 KB Output is correct
5 Correct 2 ms 4444 KB Output is correct
6 Correct 2 ms 4444 KB Output is correct
7 Correct 2 ms 4444 KB Output is correct
8 Correct 2 ms 4444 KB Output is correct
9 Correct 2 ms 4444 KB Output is correct
10 Correct 2 ms 4452 KB Output is correct
11 Correct 523 ms 210772 KB Output is correct
12 Correct 357 ms 210768 KB Output is correct
13 Correct 431 ms 210628 KB Output is correct
14 Correct 425 ms 210672 KB Output is correct
15 Correct 393 ms 210772 KB Output is correct
16 Correct 385 ms 210152 KB Output is correct
17 Correct 423 ms 210260 KB Output is correct
18 Correct 423 ms 210168 KB Output is correct
19 Correct 375 ms 210764 KB Output is correct

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Runtime error 215 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 2 ms 4188 KB Output is correct
2 Correct 2 ms 4444 KB Output is correct
3 Correct 2 ms 4476 KB Output is correct
4 Correct 2 ms 4444 KB Output is correct
5 Correct 2 ms 4444 KB Output is correct
6 Correct 2 ms 4444 KB Output is correct
7 Correct 2 ms 4444 KB Output is correct
8 Correct 2 ms 4444 KB Output is correct
9 Correct 2 ms 4444 KB Output is correct
10 Correct 2 ms 4452 KB Output is correct
11 Correct 523 ms 210772 KB Output is correct
12 Correct 357 ms 210768 KB Output is correct
13 Correct 431 ms 210628 KB Output is correct
14 Correct 425 ms 210672 KB Output is correct
15 Correct 393 ms 210772 KB Output is correct
16 Correct 385 ms 210152 KB Output is correct
17 Correct 423 ms 210260 KB Output is correct
18 Correct 423 ms 210168 KB Output is correct
19 Correct 375 ms 210764 KB Output is correct
20 Runtime error 215 ms 524288 KB Execution killed with signal 9
21 Halted 0 ms 0 KB -