Submission #308021

#	Time	Username	Problem	Language	Result	Execution time	Memory
308021		adrianbudau	Triple Jump (JOI19_jumps)	C++17	100 / 100	1085 ms	99192 KiB

jumps

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

class SegmentTree {
  public:
    SegmentTree(const vector<int> &A): m_size(A.size()), m_data(m_size * 4) {
        build(1, 1, m_size, A);
    }

    void update(int from, int to, int add) {
        update(1, 1, m_size, from, to, add);
    }

    int query(int from, int to) {
        return query(1, 1, m_size, from, to, 0);
    }

  private:
    struct Node {
        int max = 0;
        int maxadd = 0;
        int best = 0;
    };

    void build(int node, int begin, int end, const vector<int> &A) {
        if (end - begin == 1) {
            m_data[node] = Node{A[begin], 0, A[begin]};
            return;
        }
        int mid = (begin + end) / 2;
        build(node * 2, begin, mid, A);
        build(node * 2 + 1, mid, end, A);
        m_data[node] = Node{max(m_data[node * 2].max, m_data[node * 2 + 1].max), 0, max(m_data[node * 2].best, m_data[node * 2 + 1].best)};
    }

    void update(int node, int begin, int end, int from, int to, int add) {
        if (from <= begin && end <= to) {
            m_data[node].maxadd = max(m_data[node].maxadd, add);
            m_data[node].best = max(m_data[node].best, m_data[node].maxadd + m_data[node].max);
            return;
        }

        int mid = (begin + end) / 2;
        if (from < mid)
            update(node * 2, begin, mid, from, to, add);
        if (mid < to)
            update(node * 2 + 1, mid, end, from, to, add);
        m_data[node].best = max({m_data[node].best, m_data[node * 2].best, m_data[node * 2 + 1].best});
    }

    int query(int node, int begin, int end, int from, int to, int maxadd) {
        maxadd = max(maxadd, m_data[node].maxadd);
        if (from <= begin && end <= to)
            return max(m_data[node].best, m_data[node].max + maxadd);

        int mid = (begin + end) / 2;
        int answer = 0;
        if (from < mid)
            answer = max(answer, query(node * 2, begin, mid, from, to, maxadd));
        if (mid < to)
            answer = max(answer, query(node * 2 + 1, mid, end, from, to, maxadd));
        return answer;
    }

    int m_size;
    vector<Node> m_data;
};

int main() {
    ios::sync_with_stdio(false);

    int N; cin >> N;
    vector<int> A(N);
    for (int i = 0; i < N; ++i) {
        cin >> A[i];
    }

    vector< vector<int> > mids(N);
    vector<int> stack;
    for (int i = 0; i < N; ++i) {
        while (!stack.empty() && A[stack.back()] <= A[i]) {
            mids[stack.back()].push_back(i);
            stack.pop_back();
        }
        if (!stack.empty())
            mids[stack.back()].push_back(i);
        stack.push_back(i);
    }

    int Q; cin >> Q;
    vector< vector< pair<int, int> > > queries(N);

    for (int i = 0; i < Q; ++i) {
        int l, r; cin >> l >> r;
        queries[l - 1].emplace_back(r, i);
    }

    SegmentTree S(A);
    vector<int> answer(Q, 0);
    for (int  i = N - 1; i >= 0; --i) {
        for (auto &mid : mids[i]) {
            int from = 2 * mid - i;
            if (from < N)
                S.update(from, N, A[i] + A[mid]);
        }
        for (auto &[r, index] : queries[i])
            answer[index] = S.query(i, r);
    }

    for (int i = 0; i < Q; ++i)
        cout << answer[i] << "\n";
}

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