Submission #917701

#	Time	Username	Problem	Language	Result	Execution time	Memory
917701		PM1	Global Warming (CEOI18_glo)	C++17	100 / 100	43 ms	5852 KiB

glo

#include <bits/stdc++.h>
using namespace std;
#define ll long long 
const int mxn=2e5+5;
ll n,a[mxn],lis[mxn],k,ans=0;
vector<int>v;
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>k;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		int x=lower_bound(v.begin(),v.end(),a[i])-v.begin();
		if(x==v.size())
			v.push_back(a[i]);
		else
			v[x]=a[i];
		lis[i]=x+1;
	}
	ans=v.size();
	v.clear();
	v.push_back(2e9);
	for(int i=n;i>0;i--){
		int l=0,r=v.size();
		while(r-l>1){
			int mid=(l+r)/2;
			if(v[mid]>a[i]-k)l=mid;
			else r=mid;
		}
		ans=max(ans,l+lis[i]);
		//cout<<l<<" "<<lis[i]<<endl;
		l=0;r=v.size();
		while(r-l>1){
			int mid=(l+r)/2;
			if(v[mid]>a[i])l=mid;
			else r=mid;
		}
		if(r==v.size())
			v.push_back(a[i]);
		else 
			v[r]=a[i];
		

	}
	cout<<ans<<'\n';
}

Compilation message (stderr)

glo.cpp: In function 'int main()':
glo.cpp:15:7: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   15 |   if(x==v.size())
      |      ~^~~~~~~~~~
glo.cpp:39:7: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |   if(r==v.size())
      |      ~^~~~~~~~~~

• 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