Submission #1225697

#	Time	Username	Problem	Language	Result	Execution time	Memory
1225697		k12_khoi	Triple Jump (JOI19_jumps)	C++17	0 / 100	160 ms	6300 KiB

jumps

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int, int>
#define X first
#define Y second
const int N = 5e5 + 5;
const ll INF = 1e18;

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

int n, block_size;
int a[N], max_in_block[N / 1000 + 5];
ll f[N], lazy_block[N / 1000 + 5], best_in_block[N / 1000 + 5];
vector<pii> candidate_pairs;

void update_block(int pos, ll value) {
    int block = pos / block_size;
    int start = block * block_size;
    int end = min((block + 1) * block_size - 1, n);

    if (lazy_block[block] < value) {
        lazy_block[block] = value;
        best_in_block[block] = lazy_block[block] + max_in_block[block];
    }

    if (f[pos] < value) {
        f[pos] = value;
        best_in_block[block] = max(best_in_block[block], f[pos] + a[pos]);
    }

    for (int i = start; i <= end; i++) {
        if (f[i] < lazy_block[block]) {
            f[i] = lazy_block[block];
        }
        best_in_block[block] = max(best_in_block[block], f[i] + a[i]);
    }
}

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

    cin >> n;
    block_size = sqrt(n);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        int block_idx = i / block_size;
        if (a[i] > max_in_block[block_idx]) {
            max_in_block[block_idx] = a[i];
        }
    }

    deque<int> dq;
    for (int i = n; i >= 1; i--) {
        while (!dq.empty() && a[i] >= a[dq.back()]) {
            candidate_pairs.push_back({i, dq.back()});
            dq.pop_back();
        }
        if (!dq.empty()) {
            candidate_pairs.push_back({i, dq.front()});
        }
        dq.push_front(i);
    }

    int q;
    cin >> q;
    vector<Query> queries(q);
    vector<ll> ans(q, -INF);
    for (int i = 0; i < q; i++) {
        cin >> queries[i].L >> queries[i].R;
        queries[i].id = i;
    }

    sort(queries.begin(), queries.end(), [](const Query& a, const Query& b) {
        return a.L > b.L;
    });

    for (int i = 0; i <= n; i++) {
        f[i] = -INF;
    }

    int num_blocks = (n + block_size - 1) / block_size;
    for (int i = 0; i < num_blocks; i++) {
        lazy_block[i] = -INF;
        best_in_block[i] = -INF;
    }

    sort(candidate_pairs.begin(), candidate_pairs.end(), greater<pii>());
    int ptr = 0;

    for (const auto& query : queries) {
        int L = query.L, R = query.R, id = query.id;

        while (ptr < candidate_pairs.size() && candidate_pairs[ptr].X >= L) {
            int x = candidate_pairs[ptr].X;
            int y = candidate_pairs[ptr].Y;
            ll s = a[x] + a[y];
            int c_min = 2 * y - x;
            ptr++;

            if (c_min > n) continue;

            int start_block = c_min / block_size;
            int end_block = num_blocks - 1;

            for (int block = start_block; block <= end_block; block++) {
                int block_start = block * block_size;
                int block_end = min((block + 1) * block_size - 1, n);

                if (c_min <= block_start) {
                    if (s > lazy_block[block]) {
                        lazy_block[block] = s;
                        best_in_block[block] = max(best_in_block[block], lazy_block[block] + max_in_block[block]);
                    }
                } else {
                    for (int j = max(c_min, block_start); j <= block_end; j++) {
                        if (s > f[j]) {
                            f[j] = s;
                            best_in_block[block] = max(best_in_block[block], f[j] + a[j]);
                        }
                    }
                }
            }
        }

        ll best = -INF;
        int start_pos = L + 2;
        if (start_pos > R) {
            ans[id] = -INF;
            continue;
        }

        int start_block = start_pos / block_size;
        int end_block = R / block_size;

        for (int block = start_block; block <= end_block; block++) {
            int block_start = block * block_size;
            int block_end = min((block + 1) * block_size - 1, n);

            if (block_start >= start_pos && block_end <= R) {
                best = max(best, best_in_block[block]);
            } else {
                for (int j = max(start_pos, block_start); j <= min(R, block_end); j++) {
                    if (f[j] < lazy_block[block]) {
                        f[j] = lazy_block[block];
                    }
                    best = max(best, f[j] + a[j]);
                }
            }
        }

        ans[id] = best;
    }

    for (int i = 0; i < q; i++) {
        cout << ans[i] << '\n';
    }

    return 0;
}

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