oj.uz

Submission #470333

# Submission time Handle Problem Language Result Execution time Memory
470333 2021-09-03T13:59:40 Z prvocislo Global Warming (CEOI18_glo) C++17
0 / 100
 660 ms 6436 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 660 ms 6436 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 158 ms 1844 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 309 ms 3508 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -