Submission #1085453

#	Time	Username	Problem	Language	Result	Execution time	Memory
1085453		vjudge1	Global Warming (CEOI18_glo)	C++14	100 / 100	87 ms	7052 KiB

glo

#include <bits/stdc++.h>

using namespace std;
const long long MAX=2*1e5+10;
long long pr[MAX];
long long niza[MAX];
int main()
{
    long long n,x;
    cin>>n>>x;
    for(long long i=0; i<n; i++)cin>>niza[i];
    vector<long long> help(n);
    for(long long i=0; i<n; i++)help[i]=INT_MAX;
    long long res=0;
    for(long long i=0; i<n; i++)
    {
        long long nw=lower_bound(help.begin(),help.end(),niza[i])-help.begin();
        help[nw]=niza[i];
        pr[i]=nw+1;
        res=max(res,pr[i]);
    }

    for(long long i=0; i<n; i++)help[i]=INT_MAX;

    for (long long i=n-1; i>=0; i--) {
		long long nw=lower_bound(help.begin(),help.end(),-niza[i]+x)-help.begin();
		res=max(res,pr[i]+nw);
		long long tmp=lower_bound(help.begin(),help.end(),-niza[i])-help.begin();
		help[tmp]=-niza[i];
	}
	cout<<res<<endl;
    return 0;
}

• 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