Submission #868576

#	Time	Username	Problem	Language	Result	Execution time	Memory
868576		WLZ	Global Warming (CEOI18_glo)	C++17	5 / 100	36 ms	3156 KiB

glo

/**
 * Solution for beCP November 2023 Training Contest, problem 'globalwarming'/CEOI 2018 Global Warming
 * 
 * Please refer to the editorial for a detailed explanation.
 */

#include <bits/stdc++.h>
using namespace std;

constexpr int INF = 0x3f3f3f3f;

class sparse_segment_tree {
    private:
    int left_bound, right_bound;
    std::vector<int> st;
    std::vector<int> lc, rc;

    int query(int p, int cl, int cr, int l, int r) const {
        if (l > r || p == -1 || cl > r || cr < l) return -INF;
        if (l <= cl && cr <= r) return st[p];
        int cm = (long long) (cl + cr) / 2;
        return std::max(query(lc[p], cl, cm, l, r), query(rc[p], cm + 1, cr, l, r));
    }

    void update(int p, int cl, int cr, int idx, int new_val) {
        if (cl == cr) {
            st[p] = std::max(st[p], new_val);
            return;
        }
        int cm = (cl + cr) / 2;
        if (idx <= cm) {
            if (lc[p] == -1) {
                lc[p] = (int) st.size();
                st.push_back(-INF); lc.push_back(-1); rc.push_back(-1);
            }
            update(lc[p], cl, cm, idx, new_val);
        } else {
            if (rc[p] == -1) {
                rc[p] = (int) st.size();
                st.push_back(-INF); lc.push_back(-1); rc.push_back(-1);
            }
            update(rc[p], cm + 1, cr, idx, new_val);
        }
        st[p] = std::max(lc[p] != -1 ? st[lc[p]] : -INF, rc[p] != -1 ? st[rc[p]] : -INF);
    }

    public:
    sparse_segment_tree(int l, int r) : left_bound(l), right_bound(r) {
        st = {-INF};
        lc = rc = {-1};
    }

    int query(int l, int r) const { return query(0, left_bound, right_bound, l, r); }

    int query_all() const { return st[0]; }

    void update(int idx, int new_val) { update(0, left_bound, right_bound, idx, new_val); }
};

int main() {
    ios::sync_with_stdio(false); cin.tie(0);

    int n, x; cin >> n >> x;

    vector<int> t(n);
    for (int i = 0; i < n; i++) cin >> t[i];

    sparse_segment_tree dp_0(0, 50), dp_1(0, 50);
    dp_0.update(0, 0);

    for (int i = 0; i < n; i++) {
        dp_1.update(t[i] + x, dp_1.query(0, t[i] + x - 1) + 1); // Normal update
        dp_1.update(t[i] + x, dp_0.query(0, t[i] + x - 1) + 1); // Take the "jump" t[i] -> t[i] + x
        dp_0.update(t[i], dp_0.query(0, t[i] - 1) + 1); // Normal update

        // for (int j = 0; j <= 20; j++) {
        //     int tmp = dp_0.query(j, j);
        //     cerr << (tmp < 0 ? "-inf" : to_string(tmp)) << ' ';
        // }
        // cerr << endl;
        // for (int j = 0; j <= 20; j++) {
        //     int tmp = dp_1.query(j, j);
        //     cerr << (tmp < 0 ? "-inf" : to_string(tmp)) << ' ';
        // }
        // cerr << endl;
        // cerr << endl;
    }

    cout << max(dp_0.query_all(), dp_1.query_all()) << '\n';

    return 0;
}

• Subtask 1: 5 / 5
• Subtask 2: 0 / 10
• Subtask 3: 0 / 13
• Subtask 4: 0 / 10
• Subtask 5: 0 / 20
• Subtask 6: 0 / 17
• Subtask 7: 0 / 25