Submission #470334

#TimeUsernameProblemLanguageResultExecution timeMemory
470334prvocisloGlobal Warming (CEOI18_glo)C++17
100 / 100
364 ms10588 KiB
#include <algorithm>
#include <iostream>
#include <vector>
#include <queue>
#include <map>
typedef long long ll;
using namespace std;

int n, x;
map<int, int> dp[2]; // dp[pridali sme uz x?][koniec] = dlzka
void update(int l, int len, int end)
{
    if (!dp[l].count(end)) dp[l][end] = len;
    else dp[l][end] = max(dp[l][end], len);
    auto it = dp[l].find(end);
    if (it != dp[l].begin() && prev(it)->second >= len) 
    {
        dp[l].erase(it);
        return;
    }
    while (next(it) != dp[l].end() && next(it)->second <= len)
    {
        dp[l].erase(next(it));
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> x;
    vector<int> t(n);
    for (int i = 0; i < n; i++) cin >> t[i];
    dp[0][0] = dp[1][0] = 0;
    for (int i = 0; i < n; i++)
    {
        // pouzijeme moznost zvysit sufix
        int len = prev(dp[0].lower_bound(t[i] + x))->second + 1;
        update(1, len, t[i]);
        for (int j = 0; j < 2; j++)
        {
            auto it = prev(dp[j].lower_bound(t[i]));
            update(j, it->second + 1, t[i]);
        }
        //cout << i << ", " << t[i] << ": "
        //     << prev(dp[0].end())->second << " " << prev(dp[1].end())->second << endl;
    }
    cout << prev(dp[1].end())->second << "\n";
    return 0;
}
#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...