Submission #1108923

#	Time	Username	Problem	Language	Result	Execution time	Memory
1108923		csibe_csavo	Global Warming (CEOI18_glo)	C++14	55 / 100	2058 ms	6860 KiB

glo

#include <algorithm>
#include <bits/stdc++.h>
using namespace std;
int n,d;
int lis(vector<int> &v)
{
	vector<int> s{v[1]};
	for(int i=2; i<=n; i++)
	{
		int ind=lower_bound(s.begin(),s.end(),v[i])-s.begin();
		if(ind>=s.size()) s.push_back(v[i]);
		else s[ind]=v[i];
	}
	int p=s.size();
	return p;
}
void brute()
{
	vector<int> v(n+1);
	for(int i=1; i<=n; i++)
		cin>>v[i];
	int ans=lis(v);
	for(int i=1; i<n; i++)
	{
		v[i]-=d;
		if(d!=0) ans=max(ans,lis(v));
	}
	cout<<ans<<"\n";
}
void nagyd()
{
	vector<int> v(n+2);
	for(int i=1; i<=n; i++)
		cin>>v[i];
	vector<int> dpel(n+2),dphat(n+2);
	vector<pair<int, int>> lis;
	dpel[1]=1;
	lis.push_back({0,0});
	v[n+1]=2e9+3;
	for(int i=1; i<=n; i++)
	{
		if(v[i]>lis.back().first)
		{
			dpel[i]=dpel[lis.back().second]+1;
			lis.push_back({v[i],i});
		}
		else
		{
			int lo=0,hi=lis.size();
			while(lo<hi-1)
			{
				int mid=(lo+hi)/2;
				if(lis[mid].first<v[i]) lo=mid;
				else hi=mid;
			}
			dpel[i]=dpel[lis[lo].second]+1;
			lis[hi]={v[i],i};
		}
	}
	lis.clear();
	for(int i=1; i<=n+1; i++)
		v[i]=-v[i];
	lis.push_back({v[n+1],n+1});
	for(int i=n; i>0; i--)
	{
		if(v[i]>lis.back().first)
		{
			dphat[i]=dphat[lis.back().second]+1;
			lis.push_back({v[i],i});
		}
		else
		{
			int lo=0,hi=lis.size();
			while(lo<hi-1)
			{
				int mid=(lo+hi)/2;
				if(lis[mid].first<v[i]) lo=mid;
				else hi=mid;
			}
			dphat[i]=dphat[lis[lo].second]+1;
			lis[hi]={v[i],i};
		}
	}
	vector<int> prefmax(n+1),sufmax(n+2);
	for(int i=1; i<=n; i++)
		prefmax[i]=max(prefmax[i-1],dpel[i]);
	for(int i=n; i>0; i--)
		sufmax[i]=max(sufmax[i+1],dphat[i]);
	int ans=1;
	for(int i=0; i<=n; i++)
		ans=max(ans,prefmax[i]+sufmax[i+1]);
	cout<<ans<<"\n";
}
int p=1e9;
int main() {
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>n>>d;
	if(p==d) nagyd();
	else brute();
}

Compilation message (stderr)

glo.cpp: In function 'int lis(std::vector<int>&)':
glo.cpp:11:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   11 |   if(ind>=s.size()) s.push_back(v[i]);
      |      ~~~^~~~~~~~~~

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