Submission #807417

#	Time	Username	Problem	Language	Result	Execution time	Memory
807417		thimote75	Triple Jump (JOI19_jumps)	C++14	32 / 100	4070 ms	20252 KiB

jumps

#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 / 5
• Subtask 2: 0 / 14
• Subtask 3: 27 / 27
• Subtask 4: 0 / 54