Submission #678799

#	Time	Username	Problem	Language	Result	Execution time	Memory
678799		bebra	Global Warming (CEOI18_glo)	C++17	100 / 100	1141 ms	37468 KiB

glo

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

#define dbg(x) cerr << #x << ": " << x << endl;

struct FenwickTree {
    vector<int> tree;
    int size;

    FenwickTree(int n) {
        size = n;
        tree.resize(size);
    }

    void update(int pos, int value) {
        for (int i = pos; i < size; i |= i + 1) {
            tree[i] = max(tree[i], value);
        }
    }

    int query(int pos) {
        if (pos >= size) return 0;
        if (pos < 0) return 0;
        int res = 0;
        for (int i = pos; i >= 0; i = (i & (i + 1)) - 1) {
            res = max(res, tree[i]);
        }
        return res;
    }

    void clear() {
        tree.assign(size, 0);
    }
};


int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, k;
    cin >> n >> k;
    vector<int> a(n);
    vector<int> b;
    b.reserve(n * 3);
    for (auto& x : a) {
        cin >> x;
        b.push_back(x);
        b.push_back(x + k);
        b.push_back(x - k);
    }
    sort(b.begin(), b.end());
    b.resize(unique(b.begin(), b.end()) - b.begin());
    int m = b.size();
    map<int, int> compress;
    for (int i = 0; i < m; ++i) {
        compress[b[i]] = i;
    }
    int ans = 0;
    FenwickTree tree(m);
    vector<int> pref_dp(n);
    for (int i = 0; i < n; ++i) {
        pref_dp[i] = tree.query(compress[a[i]] - 1) + 1;
        tree.update(compress[a[i]], pref_dp[i]);
        ans = max(ans, pref_dp[i]);
    }
    tree.clear();
    vector<int> suf_dp(n);
    for (int i = n - 1; i >= 0; --i) {
        suf_dp[i] = tree.query(m - compress[a[i]] - 2) + 1;
        tree.update(m - compress[a[i]] - 1, suf_dp[i]);
    }
    tree.clear();
    for (int i = 0; i < n; ++i) {
        ans = max(ans, suf_dp[i] + tree.query(compress[a[i] + k] - 1));
        tree.update(compress[a[i]], pref_dp[i]);
    }
    tree.clear();
    for (int i = n - 1; i >= 0; --i) {
        ans = max(ans, pref_dp[i] + tree.query(m - compress[a[i] - k] - 2));
        tree.update(m - compress[a[i]] - 1, suf_dp[i]);
    }
    cout << ans << '\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