Submission #704640

#	Time	Username	Problem	Language	Result	Execution time	Memory
704640		Cyanmond	Global Warming (CEOI18_glo)	C++17	0 / 100	377 ms	28352 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});
        --itr;
        dp2.insert({v, itr->second + 1});

        // special
        itr = dp1.lower_bound({v + X, 0});
        std::pair<i64, int> p = {-1, -1};
        --itr;
        p = std::make_pair(v, itr->second + 1);
        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));
        --itr;
        dp1.insert({v, itr->second + 1});
    }
    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 << solve(T, X) << std::endl;
    /*
    std::mt19937 mt(100);
    std::uniform_int_distribution<i64> dist(1, 10);
    int cases = 100;
    while (cases--) {
        int N = 1000;
        std::vector<i64> T(N);
        for (auto &e : T) e = dist(mt);
        i64 X = dist(mt);
        if (solve(T, X) != solveNaive(T, X)) {
            std::cout << N << " " << X << std::endl;
            for (const auto e : T) std::cout << e << ' ';
            std::cout << std::endl;
        }
    }
    */
}

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