oj.uz

Submission #807417

# Submission time Handle Problem Language Result Execution time Memory
807417 2023-08-04T17:07:27 Z thimote75 Triple Jump (JOI19_jumps) C++14
32 / 100
 4000 ms 20252 KB 
#include <bits/stdc++.h>
#define int long long

using namespace std;

template <typename T>
string to_string (T x) {
    string S = "[";
    bool first = true;
    for (const auto v : x) {
        if (!first) S += ", ";
        first = false;
        S += to_string(v);
    }
    S += "]";
    return S;
}
string to_string (string S) { return S; }
template <typename A, typename B>
string to_string (pair<A, B> p) {
    return "(" + to_string(p.first )+ ", " + to_string(p.second) + ")";
}

void dbg_out () { cout << endl; }
template <typename Head, typename... Tail>
void dbg_out (Head H, Tail... T) {
    cout << to_string(H) << " ";
    dbg_out(T...);
}

#ifdef DEBUG
#  define dbg(...) { cout << "(" << #__VA_ARGS__ << "): "; dbg_out(__VA_ARGS__); }
#else
#  define dbg(...)
#endif

using idata = vector<int>;
using igrid = vector<idata>;
template<typename T>
using grid = vector<vector<T>>;

igrid opt;

struct SegTree {
    vector<int> tree;

    int start, height, size;
    SegTree (vector<int> values) {
        size   = values.size();
        height = ceil(log2(size));
        start  = 1 << height;

        tree.resize(start << 1);
        for (int i = 0; i < size; i ++)
            tree[start + i] = values[i];
    
        for (int i = start - 1; i >= 0; i --)
            tree[i] = max(tree[i * 2], tree[i * 2 + 1]);
    }
    int query (int l, int r) {
        l += start; r += start;

        int res = 0;
        while (l < r) {
            if ((l & 1) == 1) res = max(res, tree[l]);
            if ((r & 1) == 0) res = max(res, tree[r]);

            l = (l + 1) >> 1;
            r = (r - 1) >> 1;
        }

        if (l == r) res = max(res, tree[l]);
        return res;
    }
};

signed main () {
    int N;
    cin >> N;

    idata A(N);
    for (int i = 0; i < N; i ++)
        cin >> A[i];
    
    opt.resize(N);
    deque<int> local;
    for (int i = 0; i < N; i ++) {
        while (local.size() != 0 && A[local.front()] < A[i]) {
            int curr = local.front(); local.pop_front();
            opt[i].push_back(curr);
        }

        if (local.size() != 0) opt[i].push_back(local.front());
        local.push_front(i);
    }

    SegTree tree(A);

    int Q; cin >> Q;
    for (int q = 0; q < Q; q ++) {
        int l, r;
        cin >> l >> r;
        l --; r --;

        int result = 0;
        for (int optB = l + 1; optB < r; optB ++) {
            for (int optA : opt[optB]) {
                if (optA < l) break ;
                int del  = optB - optA;
                int optC = optB + del;
                if (optC > r) break ;

                result = max(
                    result,
                    A[optA] + A[optB] + tree.query(optC, r)
                );
            }
        }

        cout << result << "\n";
    }
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 300 KB Output is correct
3 Correct 1 ms 300 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 304 KB Output is correct
10 Correct 1 ms 212 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 300 KB Output is correct
3 Correct 1 ms 300 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 304 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Execution timed out 4070 ms 1332 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 19688 KB Output is correct
2 Correct 87 ms 18504 KB Output is correct
3 Correct 89 ms 20252 KB Output is correct
4 Correct 98 ms 19788 KB Output is correct
5 Correct 97 ms 19788 KB Output is correct
6 Correct 84 ms 19772 KB Output is correct
7 Correct 81 ms 19776 KB Output is correct
8 Correct 82 ms 19792 KB Output is correct
9 Correct 94 ms 19764 KB Output is correct

Subtask #4
0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 300 KB Output is correct
3 Correct 1 ms 300 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 304 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Execution timed out 4070 ms 1332 KB Time limit exceeded
12 Halted 0 ms 0 KB -