oj.uz

Submission #129205

# Submission time Handle Problem Language Result Execution time Memory
129205 2019-07-11T20:26:26 Z mraron Global Warming (CEOI18_glo) C++14
17 / 100
 184 ms 4872 KB 
#include<bits/stdc++.h>
using namespace std;
int main() {
    int n,x;
    cin>>n>>x;
    vector<int> t(n);
    for(int i=0;i<n;++i) {
        cin>>t[i];
    }

    vector<int> len(n);
    vector<int> lis;
    for(int i=0;i<n;++i) {
        auto it=lower_bound(lis.begin(), lis.end(), t[i]);
        if(it==lis.end()) {
            lis.push_back(t[i]);
            len[i]=lis.size();
        }else {
            *it=t[i];
            len[i]=it-lis.begin()+1;
        }

    }

    /*for(auto i:len) {
        cerr<<i<<" ";
    }cerr<<"\n";*/

    vector<int> lds;
    int ans=lis.size();
    for(int i=n-1;i>=0;i--) {
        int pos;
        auto it2=lower_bound(lds.begin(), lds.end(), -t[i]-1);

        if(it2==lds.end()) pos=lds.size();
        else pos=it2-lds.begin()+1;

        ans=max(ans, pos+len[i]);

        auto it=lower_bound(lds.begin(), lds.end(), -t[i]-x);

        if(it==lds.end()) {
            lds.push_back(-t[i]-x);
        }else {
            *it=-t[i]-x;
        }
    }

    cout<<ans<<"\n";


    return 0;
}
/*
8 10
7 3 5 12 2 7 3 4

3 1
1 2 2
*/

Subtask #1
0 / 5.0

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

Subtask #2
0 / 10.0

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

Subtask #3
0 / 13.0

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

Subtask #4
0 / 10.0

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

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 46 ms 660 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 88 ms 1244 KB Output is correct
2 Correct 90 ms 2020 KB Output is correct
3 Correct 176 ms 3824 KB Output is correct
4 Correct 120 ms 4204 KB Output is correct
5 Correct 61 ms 2292 KB Output is correct
6 Correct 115 ms 4152 KB Output is correct
7 Correct 157 ms 4872 KB Output is correct
8 Correct 85 ms 2272 KB Output is correct

Subtask #7
0 / 25.0

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