제출 #470333

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
470333		prvocislo	Global Warming (CEOI18_glo)	C++17	0 / 100	660 ms	6436 KiB

glo

#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;
}

• 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