Submission #868585

#	Time	Username	Problem	Language	Result	Execution time	Memory
868585		WLZ	Global Warming (CEOI18_glo)	C++17	100 / 100	490 ms	26452 KiB

glo

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

constexpr int INF = 0x3f3f3f3f;

// https://codeforces.com/blog/entry/18051
class segment_tree {
    private:
    int n;
    std::vector<int> st;
    
    public:
    segment_tree(int _n) : n(_n), st(n << 1, -INF) {}

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

    int query(int l, int r) const {        
        int ans = -INF;
        for (l += n, r += n + 1; l < r; l >>= 1, r >>= 1) {
            if (l & 1) ans = std::max(ans, st[l++]);
            if (r & 1) ans = std::max(ans, st[--r]);
        }
        return ans;
    }

    void update(int idx, const int &new_val) {
        idx += n;
        st[idx] = std::max(st[idx], new_val);
        for (; idx >>= 1; ) st[idx] = std::max(st[idx << 1], st[idx << 1 | 1]);
    }
};

class coordinate_compression : std::map<int, int> {
    public:
    using std::map<int, int>::operator[];
    using std::map<int, int>::size;

    coordinate_compression() {}

    void add(const int &x) { operator[](x) = 0; }

    void process(int idx = 0) {
        for (auto it = begin(); it != end(); ++it) it->second = idx++;
    }
};

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];

    coordinate_compression cc;
    cc.add(-INF);
    for (int i = 0; i < n; i++) {
        cc.add(t[i]);
        cc.add(t[i] + x);
    }
    cc.process();

    segment_tree dp_0((int) cc.size()), dp_1((int) cc.size());
    dp_0.update(0, 0);

    for (int i = 0; i < n; i++) {
        dp_1.update(cc[t[i] + x], dp_1.query(0, cc[t[i] + x] - 1) + 1);
        dp_1.update(cc[t[i] + x], dp_0.query(0, cc[t[i] + x] - 1) + 1);
        dp_0.update(cc[t[i]], dp_0.query(0, cc[t[i]] - 1) + 1);
    }

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

    return 0;
}

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