oj.uz

Submission #422579

# Submission time Handle Problem Language Result Execution time Memory
422579 2021-06-10T08:49:19 Z snasibov05 Global Warming (CEOI18_glo) C++14
0 / 100
 112 ms 5288 KB 
#include <bits/stdc++.h>

using namespace std;

#define oo 1000000000

int main() {
    int n, x; cin >> n >> x;
    vector<int> v(n);
    for (int i = 0; i < n; ++i) {
        cin >> v[i];
    }

    int sz = 1;
    vector<int> dp(n);
    vector<int> c(n+1, oo);
    c[0] = 0;
    c[1] = v[0];
    dp[0] = 1;

    for (int i = 1; i < n; ++i) {
        if (v[i] < c[1]) c[1] = v[i], dp[i] = 1;
        else if (v[i] > c[sz]) c[sz+1] = v[i], dp[i] = ++sz;
        else {
            int k = lower_bound(c.begin(), c.end(), v[i]) - c.begin();
            c[k] = v[i];
            dp[i] = k;
        }
    }

    vector<int> sufdp(n);
    c.assign(0, n+1);
    c[0] = oo;
    c[1] = v[n-1] + x;
    dp[n-1] = 1;
    sz = 1;

    int ans = dp[n-1];

    for (int i = n-2; i >= 0; --i){
        if (v[i] > c[1]) ans = max(ans, dp[i]);
        else if (v[i] < c[sz]) ans = max(ans, dp[i] + sz);
        else{
            int k = upper_bound(c.begin(), c.end(), v[i]) - c.begin() - 1;
            ans = max(ans, dp[i] + k - 1);
        }

        if (v[i] + x > c[1]) c[1] = v[i] + x, dp[i] = 1;
        else if (v[i] + x < c[sz]) c[sz+1] = v[i] + x, dp[i] = ++sz;
        else{
            int k = upper_bound(c.begin(), c.end(), v[i] + x) - c.begin() - 1;
            c[k] = v[i] + x;
            dp[i] = k;
        }
    }

    cout << ans << "\n";

    return 0;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 332 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 332 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 332 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 107 ms 5272 KB Output is correct
2 Correct 107 ms 5288 KB Output is correct
3 Correct 112 ms 5272 KB Output is correct
4 Correct 112 ms 5276 KB Output is correct
5 Runtime error 76 ms 4508 KB Execution killed with signal 11

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 1492 KB Output is correct
2 Correct 27 ms 1484 KB Output is correct
3 Correct 27 ms 1496 KB Output is correct
4 Incorrect 18 ms 1300 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

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

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 332 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -