Submission #704637

#	Time	Username	Problem	Language	Result	Execution time	Memory
704637		Cyanmond	Global Warming (CEOI18_glo)	C++17	28 / 100	2079 ms	8612 KiB

glo

#include <bits/stdc++.h>

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

int calcLIS(std::vector<i64> T) {
    std::vector<i64> dp(T.size() + 1, inf);
    for (const auto e : T) {
        auto itr = std::lower_bound(dp.begin(), dp.end(), e);
        *itr = e;
    }
    return (int)(std::lower_bound(dp.begin(), dp.end(), inf) - dp.begin());
}

int solveNaive(std::vector<i64> T, i64 X) {
    int ans = 0;
    for (int i = (int)T.size() - 1; i >= 0; --i) {
        T[i] += X;
        ans = std::max(ans, calcLIS(T));
    }
    return ans;
}

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

        // special
        itr = dp1.lower_bound({v + X, 0});
        std::pair<i64, int> p = {-1, -1};
        if (itr == dp1.end()) {
            --itr;
            p = std::make_pair(v, itr->second + 1);
        } else {
            p = std::make_pair(v, itr->second);
        }
        itr = dp2.lower_bound({v, 1 << 30});
        --itr;
        if (itr->second < p.second) {
            dp2.insert(p);
            itr = dp2.lower_bound(p);
            --itr;
            if (itr->first == v) {
                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(v, 0));
        if (itr == dp1.end()) {
            --itr;
            dp1.insert({v, itr->second + 1});
        } else {
            const int l = itr->second;
            dp1.erase(itr);
            dp1.insert({v, l});
        }
    }
    return dp2.rbegin()->second;
}

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

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