oj.uz

Submission #129203

# Submission time Handle Problem Language Result Execution time Memory
129203 2019-07-11T20:23:46 Z mraron Global Warming (CEOI18_glo) C++14
10 / 100
 190 ms 3184 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]);
        if(it2==lds.end()) pos=lds.size();
        else pos=it2-lds.begin()+1;

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

        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
*/

Subtask #1
0 / 5.0

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

Subtask #2
0 / 10.0

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

Subtask #3
0 / 13.0

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

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 190 ms 1948 KB Output is correct
2 Correct 186 ms 1912 KB Output is correct
3 Correct 186 ms 1956 KB Output is correct
4 Correct 188 ms 1912 KB Output is correct
5 Correct 121 ms 3184 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 760 KB Output is correct
2 Correct 47 ms 760 KB Output is correct
3 Correct 46 ms 760 KB Output is correct
4 Correct 32 ms 1144 KB Output is correct
5 Incorrect 2 ms 256 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

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

Subtask #7
0 / 25.0

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