Submission #1253834

#	Time	Username	Problem	Language	Result	Execution time	Memory
1253834		ankite	Triple Jump (JOI19_jumps)	C++20	0 / 100	4094 ms	37160 KiB

jumps

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const long long INF = -1e18;

int N, Q;
vector<long long> A;
vector<pair<int, int>> queries;
vector<long long> answers;

// Sparse table for RMQ
vector<vector<long long>> rmq_table;
vector<int> log_table;

void build_rmq() {
    log_table.resize(N + 1);
    log_table[1] = 0;
    for (int i = 2; i <= N; ++i) {
        log_table[i] = log_table[i / 2] + 1;
    }

    int max_log = log_table[N];
    rmq_table.resize(max_log + 1, vector<long long>(N + 1, 0));

    for (int i = 1; i <= N; ++i) {
        rmq_table[0][i] = A[i - 1];
    }

    for (int j = 1; j <= max_log; ++j) {
        for (int i = 1; i + (1 << j) - 1 <= N; ++i) {
            rmq_table[j][i] = max(rmq_table[j - 1][i], rmq_table[j - 1][i + (1 << (j - 1))]);
        }
    }
}

long long query_rmq(int l, int r) {
    if (l > r) return -INF;
    int len = r - l + 1;
    int j = log_table[len];
    return max(rmq_table[j][l], rmq_table[j][r - (1 << j) + 1]);
}

// Fenwick tree (Binary Indexed Tree)
vector<long long> ft;

void update_ft(int idx, long long val) {
    for (; idx <= N; idx += idx & -idx) {
        ft[idx] = max(ft[idx], val);
    }
}

long long query_ft(int idx) {
    long long max_val = -INF;
    for (; idx > 0; idx -= idx & -idx) {
        max_val = max(max_val, ft[idx]);
    }
    return max_val;
}

struct Query {
    int id;
    int L, R;
    long long ans;
};

// Custom comparison for sorting queries
bool compareQueries(const Query& a, const Query& b) {
    return a.R < b.R;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> N;
    A.resize(N);
    for (int i = 0; i < N; ++i) {
        cin >> A[i];
    }
    
    // Convert to 1-based indexing for convenience
    vector<long long> A1(N + 1);
    for(int i = 0; i < N; ++i) {
        A1[i+1] = A[i];
    }
    A = A1;

    cin >> Q;
    vector<Query> sorted_queries(Q);
    for (int i = 0; i < Q; ++i) {
        sorted_queries[i].id = i;
        cin >> sorted_queries[i].L >> sorted_queries[i].R;
    }
    sort(sorted_queries.begin(), sorted_queries.end(), compareQueries);

    build_rmq();

    ft.assign(N + 1, -INF);

    vector<long long> max_prefix_A(N + 1, -INF);
    for(int i = 1; i <= N; ++i) {
        max_prefix_A[i] = max(max_prefix_A[i-1], A[i]);
    }

    // dp[b] stores max(A_a + A_b) for a fixed b, a<b
    vector<long long> dp_sum_ab(N + 1, -INF);
    for(int b = 2; b <= N; ++b) {
        dp_sum_ab[b] = max_prefix_A[b-1] + A[b];
    }

    answers.resize(Q);

    int query_idx = 0;
    for (int c = 1; c <= N; ++c) {
        for(int b=1; b<c; ++b){
            int a_min = 2*b - c;
            if(a_min < 1) a_min = 1;
            
            if(a_min < b){
                long long val = A[c] + A[b] + query_rmq(a_min, b-1);
                update_ft(b, val);
            }
        }
        
        while (query_idx < Q && sorted_queries[query_idx].R == c) {
            int L = sorted_queries[query_idx].L;
            long long max_val = query_ft(c);
            long long temp_max = -INF;
            for(int b = L+1; b < c; ++b){
                 int a_min = 2*b-c;
                 if(a_min < L) a_min = L;
                 if(a_min < b){
                    temp_max = max(temp_max, A[c] + A[b] + query_rmq(a_min, b-1));
                 }
            }
            sorted_queries[query_idx].ans = temp_max;
            query_idx++;
        }
    }
    
    // Sort back to original order
    vector<long long> final_answers(Q);
    for(int i = 0; i < Q; ++i) {
        final_answers[sorted_queries[i].id] = sorted_queries[i].ans;
    }

    for(int i = 0; i < Q; ++i) {
        cout << final_answers[i] << "\n";
    }

    return 0;
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 14
• Subtask 3: 0 / 27
• Subtask 4: 0 / 54