oj.uz

Submission #893635

# Submission time Handle Problem Language Result Execution time Memory
893635 2023-12-27T08:06:34 Z Alcabel Triple Jump (JOI19_jumps) C++17
32 / 100
 4000 ms 8208 KB 
#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.0 / 5.0

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

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 452 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 356 KB Output is correct
11 Execution timed out 4014 ms 8208 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 5200 KB Output is correct
2 Correct 18 ms 6356 KB Output is correct
3 Correct 19 ms 6100 KB Output is correct
4 Correct 24 ms 5204 KB Output is correct
5 Correct 22 ms 5208 KB Output is correct
6 Correct 18 ms 4436 KB Output is correct
7 Correct 17 ms 4444 KB Output is correct
8 Correct 17 ms 4560 KB Output is correct
9 Correct 19 ms 4700 KB Output is correct

Subtask #4
0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 452 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 356 KB Output is correct
11 Execution timed out 4014 ms 8208 KB Time limit exceeded
12 Halted 0 ms 0 KB -