Submission #807439

#	Time	Username	Problem	Language	Result	Execution time	Memory
807439		thimote75	Triple Jump (JOI19_jumps)	C++14	100 / 100	761 ms	107932 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>>;

using di = pair<int, int>; using vd = vector<di>;
using ti = pair<di, int> ; using vt = vector<ti>;

igrid opt;

struct Monoid {
    int p = 0, q = 0, ppq = 0;
    Monoid () = default;
    Monoid (int p, int q, int ppq) : p(p), q(q), ppq(ppq) {}

    static Monoid merge (Monoid &left, Monoid &right) {
        return Monoid( max(left.p, right.p), max(left.q, right.q), max(left.p + right.q, max(left.ppq, right.ppq)) );
    }
};

struct SegTree {
    vector<Monoid> tree;

    int start, height, size;
    SegTree (int _size) {
        size   = _size;
        height = ceil(log2(size));
        start  = 1 << height;

        tree.resize(start << 1);
    }
    void update (int i) {
        i += start;
        i >>= 1;
        while (i != 0) {
            tree[i] = Monoid::merge(tree[2 * i], tree[2 * i + 1]);
            i >>= 1;
        }
    }
    void modify_p (int i, int p) {
        tree[i + start].p   = max(tree[i + start].p, p);
        tree[i + start].ppq = max(tree[i + start].ppq, tree[i + start].p + tree[i + start].q);
        update(i);
    }
    void modify_q (int i, int q) {
        tree[i + start].q   = max(tree[i + start].q, q);
        tree[i + start].ppq = max(tree[i + start].ppq, tree[i + start].p + tree[i + start].q);
        update(i);
    }
    int query (int l, int r) {
        l += start; r += start;

        Monoid resL;
        Monoid resR;

        idata qL, qR;
        while (l < r) {
            if ((l & 1) == 1) resL = Monoid::merge(resL, tree[l]);
            if ((r & 1) == 0) resR = Monoid::merge(tree[r], resR);

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

        if (l == r) resL = Monoid::merge(resL, tree[l]);

        return Monoid::merge(resL, resR).ppq;
    }
};

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);
    }

    vd opt_q;

    for (int i = 0; i < N; i ++) {
        for (int a : opt[i]) {
            opt_q.push_back({ a, i });
        }
    }

    sort(opt_q.begin(), opt_q.end());
    reverse(opt_q.begin(), opt_q.end());

    int Q;
    cin >> Q;
    idata answer(Q);

    vt queries;

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

        queries.push_back({ { l, r }, q });
    }

    sort(queries.begin(), queries.end());
    reverse(queries.begin(), queries.end());

    int opt_q_id = 0;
    int query_id = 0;
    SegTree tree(N);
    for (int i = 0; i < N; i ++)
        tree.modify_q(i, A[i]);

    for (int i = N - 1; i >= 0; i --) {
        while (opt_q_id != opt_q.size() && opt_q[opt_q_id].first == i) {
            int optA = opt_q[opt_q_id].first;
            int optB = opt_q[opt_q_id].second;
            opt_q_id ++;

            int optC = 2 * optB - optA;
            if (optC > N) continue ;

            tree.modify_p(optC, A[optA] + A[optB]);
        }

        while (query_id != queries.size() && queries[query_id].first.first == i) {
            int l = queries[query_id].first.first;
            int r = queries[query_id].first.second;
            int i = queries[query_id].second;
            query_id ++;

            answer[i] = tree.query(l, r);
        }
    }

    for (int u : answer) cout << u << "\n";
}

Compilation message (stderr)

jumps.cpp: In function 'int main()':
jumps.cpp:163:25: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  163 |         while (opt_q_id != opt_q.size() && opt_q[opt_q_id].first == i) {
      |                ~~~~~~~~~^~~~~~~~~~~~~~~
jumps.cpp:174:25: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<std::pair<long long int, long long int>, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  174 |         while (query_id != queries.size() && queries[query_id].first.first == i) {
      |                ~~~~~~~~~^~~~~~~~~~~~~~~~~

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