Submission #129203

#	Time	Username	Problem	Language	Result	Execution time	Memory
129203		mraron	Global Warming (CEOI18_glo)	C++14	10 / 100	190 ms	3184 KiB

glo

#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
• Subtask 2: 0 / 10
• Subtask 3: 0 / 13
• Subtask 4: 10 / 10
• Subtask 5: 0 / 20
• Subtask 6: 0 / 17
• Subtask 7: 0 / 25