Submission #893635

#	Time	Username	Problem	Language	Result	Execution time	Memory
893635		Alcabel	Triple Jump (JOI19_jumps)	C++17	32 / 100	4014 ms	8208 KiB

jumps

#include <bits/stdc++.h>
using namespace std;

void solve() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    vector<int> leftGreq(n, -1), rightGreq(n, n), stk;
    for (int i = 0; i < n; ++i) {
        while (!stk.empty() && a[stk.back()] < a[i]) {
            stk.pop_back();
        }
        if (!stk.empty()) {
            leftGreq[i] = stk.back();
        }
        stk.emplace_back(i);
    }
    stk.clear();
    for (int i = n - 1; i >= 0; --i) {
        while (!stk.empty() && a[stk.back()] < a[i]) {
            stk.pop_back();
        }
        if (!stk.empty()) {
            rightGreq[i] = stk.back();
        }
        stk.emplace_back(i);
    }
    stk.clear();
    vector<int> sufMax(n);
    int q;
    cin >> q;
    while (q--) {
        int l, r;
        cin >> l >> r;
        --l, --r;
        sufMax[r] = a[r];
        for (int i = r - 1; i >= l; --i) {
            sufMax[i] = max(sufMax[i + 1], a[i]);
        }
        int ans = 0;
        for (int i = l; i < r; ++i) {
            if (rightGreq[i] < r && rightGreq[i] - i <= r - rightGreq[i]) {
                ans = max(ans, a[i] + a[rightGreq[i]] + sufMax[rightGreq[i] + rightGreq[i] - i]);
            }
        }
        for (int j = r - 1; j > l; --j) {
            if (leftGreq[j] >= l && j - leftGreq[j] <= r - j) {
                ans = max(ans, a[j] + a[leftGreq[j]] + sufMax[j + j - leftGreq[j]]);
            }
        }
        cout << ans << '\n';
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

#ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    int T = 1;
    cin >> T;
    while (T--) {
        solve();
        cerr << "-----------\n";
        cout << "-----------\n";
    }
#else
    int T = 1;
    // cin >> T;
    while (T--) {
        solve();
    }
#endif

    return 0;
}

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