Submission #704631

#	Time	Username	Problem	Language	Result	Execution time	Memory
704631		Cyanmond	Global Warming (CEOI18_glo)	C++17	62 / 100	168 ms	14280 KiB

glo

#include <bits/stdc++.h>

using i64 = long long;
constexpr i64 inf = 1ll << 50;

int main() {
    int N;
    i64 X;
    std::cin >> N >> X;
    std::vector<i64> T(N);
    for (auto &e : T) {
        std::cin >> e;
    }

    std::set<std::pair<i64, int>> dp1, dp2;
    dp1.insert({0, 0});
    dp2.insert({0, 0});
    for (int i = 0; i < N; ++i) {
        // normal
        auto itr = dp2.lower_bound({T[i], 0});
        if (itr == dp2.end()) {
            --itr;
            dp2.insert({T[i], itr->second + 1});
        } else {
            const int l = itr->second;
            dp2.erase(itr);
            dp2.insert({T[i], l});
        }

        // special
        itr = dp1.lower_bound({T[i] + X, 0});
        std::pair<i64, int> p = {-1, -1};
        if (itr == dp1.end()) {
            --itr;
            p = std::make_pair(T[i], itr->second + 1);
        } else {
            p = std::make_pair(T[i], itr->second);
        }
        itr = dp2.lower_bound({T[i], N + 1});
        --itr;
        if (itr->second < p.second) {
            dp2.insert(p);
            itr = dp2.lower_bound(p);
            --itr;
            if (itr->first == T[i]) {
                dp2.erase(itr);
            }
            itr = dp2.upper_bound(p);
            while (itr != dp2.end() and itr->second <= p.second) {
                itr = dp2.erase(itr);
            }
        }

        // normal
        itr = dp1.lower_bound(std::make_pair(T[i], 0));
        if (itr == dp1.end()) {
            --itr;
            dp1.insert({T[i], itr->second + 1});
        } else {
            const int l = itr->second;
            dp1.erase(itr);
            dp1.insert({T[i], l});
        }
    }
    std::cout << std::max(dp1.rbegin()->second, dp2.rbegin()->second) << std::endl;
}

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