Submission #1253435

#	Time	Username	Problem	Language	Result	Execution time	Memory
1253435		ankite	Triple Jump (JOI19_jumps)	C++20	Compilation error	0 ms	0 KiB

jumps

#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>
#include <cmath>
#include <climits>

using namespace std;

class SegmentTree {
private:
    int n;
    vector<int> data;

public:
    SegmentTree(int size) {
        n = 1;
        while (n < size) n <<= 1;
        data.assign(2 * n, -1e9);
    }

    void update(int pos, int val) {
        pos += n;
        if (val > data[pos]) {
            data[pos] = val;
        }
        pos >>= 1;
        while (pos >= 1) {
            int new_val = max(data[2 * pos], data[2 * pos + 1]);
            if (new_val == data[pos]) break;
            data[pos] = new_val;
            pos >>= 1;
        }
    }

    int query(int l, int r) {
        l += n;
        r += n;
        int res = -1e9;
        while (l <= r) {
            if (l % 2 == 1) res = max(res, data[l++]);
            if (r % 2 == 0) res = max(res, data[r--]);
            l >>= 1;
            r >>= 1;
        }
        return res;
    }
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

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

    int Q;
    cin >> Q;
    vector<pair<int, int>> queries(Q);
    for (int i = 0; i < Q; ++i) {
        cin >> queries[i].first >> queries[i].second;
        queries[i].first--;
        queries[i].second--;
    }

    int LOG = log2(N) + 1;
    vector<vector<pair<int, int>>> st(LOG, vector<pair<int, int>>(N));
    for (int i = 0; i < N; ++i) {
        st[0][i] = {A[i], i};
    }
    for (int j = 1; j < LOG; ++j) {
        for (int i = 0; i + (1 << j) <= N; ++i) {
            st[j][i] = max(st[j - 1][i], st[j - 1][i + (1 << (j - 1))]);
        }
    }

    auto query_range_max = [&](int l, int r) {
        if (l > r) return make_pair(-1e9, -1);
        int k = log2(r - l + 1);
        return max(st[k][l], st[k][r - (1 << k) + 1]);
    };

    vector<vector<int>> next_greater(N);
    stack<int> s;
    for (int i = 0; i < N; ++i) {
        while (!s.empty() && A[s.top()] < A[i]) {
            next_greater[s.top()].push_back(i);
            s.pop();
        }
        if (!s.empty()) {
            next_greater[s.top()].push_back(i);
        }
        s.push(i);
    }

    vector<tuple<int, int, int>> events;
    for (int i = 0; i < N; ++i) {
        for (int j : next_greater[i]) {
            int k_low = 2 * j - i;
            if (k_low < N) {
                auto [max_val, max_idx] = query_range_max(k_low, N - 1);
                int total = A[i] + A[j] + max_val;
                events.emplace_back(max_idx, i, total);
            }
        }
    }

    sort(events.begin(), events.end());
    vector<tuple<int, int, int>> sorted_queries;
    for (int i = 0; i < Q; ++i) {
        sorted_queries.emplace_back(queries[i].second, queries[i].first, i);
    }
    sort(sorted_queries.begin(), sorted_queries.end());

    SegmentTree seg_tree(N);
    vector<int> ans(Q, -1e9);
    int event_ptr = 0;
    for (auto [R, L, idx] : sorted_queries) {
        while (event_ptr < events.size() && get<0>(events[event_ptr]) <= R) {
            auto [k, i, val] = events[event_ptr];
            seg_tree.update(i, val);
            event_ptr++;
        }
        ans[idx] = seg_tree.query(L, N - 1);
    }

    for (int i = 0; i < Q; ++i) {
        cout << ans[i] << '\n';
    }

    return 0;
}

Compilation message (stderr)

jumps.cpp: In lambda function:
jumps.cpp:84:19: error: inconsistent types 'std::pair<double, int>' and 'std::pair<int, int>' deduced for lambda return type
   84 |         return max(st[k][l], st[k][r - (1 << k) + 1]);
      |                ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~