Submission #704631

#TimeUsernameProblemLanguageResultExecution timeMemory
704631CyanmondGlobal Warming (CEOI18_glo)C++17
62 / 100
168 ms14280 KiB
#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;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...