oj.uz

Submission #468237

# Submission time Handle Problem Language Result Execution time Memory
468237 2021-08-27T10:14:23 Z wdjpng Global Warming (CEOI18_glo) C++17
17 / 100
 123 ms 7388 KB 
#include <bits/stdc++.h>

#define int long long
#define rep(i,n) for(int i = 0; i < n; i++)

using namespace std;

signed main()
{
    int n, x;
    cin >> n >> x;
    vector<int>t(n);
    rep(i,n) cin>>t[i];

    vector<int>c;
    vector<int>right(n);
    for(int i = n-1; i >=0; i--)
    {
        int r = 1e10 - t[i];
        if(!c.size()||r>c[c.size()-1]) c.push_back(r);
        else *(lower_bound(c.begin(), c.end(), r)) = r;
        right[i] = c.size();
    }
    c = vector<int>(n, 1e17);
    
    int maxx = 0;
    rep(i,n)
    {
        auto it  = lower_bound(c.begin(), c.end(), t[i] - x);
        int off = it - c.begin();
        maxx=max(maxx, right[i] + (lower_bound(c.begin(), c.end(), t[i]) - c.begin()));
        *(lower_bound(c.begin(), c.end(), t[i]-x)) = t[i] - x;
    }
    cout<<maxx<<"\n";
}

Compilation message

glo.cpp: In function 'int main()':
glo.cpp:30:13: warning: unused variable 'off' [-Wunused-variable]
   30 |         int off = it - c.begin();
      |             ^~~

Subtask #1
0 / 5.0

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

Subtask #2
0 / 10.0

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

Subtask #3
0 / 13.0

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

Subtask #4
0 / 10.0

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

Subtask #5
0 / 20.0

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

Subtask #6
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 2612 KB Output is correct
2 Correct 59 ms 3564 KB Output is correct
3 Correct 122 ms 6828 KB Output is correct
4 Correct 84 ms 6948 KB Output is correct
5 Correct 41 ms 3744 KB Output is correct
6 Correct 81 ms 6736 KB Output is correct
7 Correct 99 ms 7388 KB Output is correct
8 Correct 56 ms 3620 KB Output is correct

Subtask #7
0 / 25.0

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