Submission #129209

#	Time	Username	Problem	Language	Result	Execution time	Memory
129209		mraron	Global Warming (CEOI18_glo)	C++14	100 / 100	187 ms	4976 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--) {
        //for(auto j:lds) cerr<<j<<" ";cerr<<"\n";

        int pos;
        auto it2=lower_bound(lds.begin(), lds.end(), -t[i]);

        if(it2==lds.end()) pos=lds.size();
        else pos=it2-lds.begin();
        //cerr<<len[i]<<" "<<pos<<"\n";
        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

3 0
1 2 2
*/

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 13 / 13
• Subtask 4: 10 / 10
• Subtask 5: 20 / 20
• Subtask 6: 17 / 17
• Subtask 7: 25 / 25