Submission #836455

#	Time	Username	Problem	Language	Result	Execution time	Memory
836455		dshfjka	Global Warming (CEOI18_glo)	C++14	100 / 100	189 ms	14772 KiB

glo

#include <bits/stdc++.h>
#define LL long long
#define mp make_pair
#define fi first
#define se second
using namespace std;
int main()
{
	LL n,x;
	scanf("%lld %lld",&n,&x);
	LL arr[n+5];
	for(LL a=1;a<=n;a++)
	{
		scanf("%lld",&arr[a]);
	}
	vector<LL>lis,lds;
	LL pref[n+5],suff[n+5];
	for(LL a=1;a<=n;a++)
	{
	//	printf("a=%lld\n",a);
		if(lower_bound(lis.begin(),lis.end(),arr[a])!=lis.end())
		{
			lis[lower_bound(lis.begin(),lis.end(),arr[a])-lis.begin()]=arr[a];
		}
		else
		{
			lis.push_back(arr[a]);
		}
		pref[a]=lower_bound(lis.begin(),lis.end(),arr[a])-lis.begin()+1;
//		printf("pref[%lld]=%lld\n",a,pref[a]);
	}
//	printf("DOR\n");
	for(LL a=n;a>=1;a--)
	{
	//	printf("a=%lld\n",a);
		if(lower_bound(lds.begin(),lds.end(),-arr[a])!=lds.end())
		{
			lds[lower_bound(lds.begin(),lds.end(),-arr[a])-lds.begin()]=-arr[a];
		}
		else
		{
			lds.push_back(-arr[a]);
		}
		suff[a]=lower_bound(lds.begin(),lds.end(),-arr[a])-lds.begin()+1;
		//printf("suff[%lld]=%lld\n",a,suff[a]);
	}
//	for(LL a=1;a<=n;a++)printf("%lld ",pref[a]);
//	printf("\n");
//	for(LL a=n;a>=1;a--)printf("%lld ",suff[a]);
//	printf("\n");
	LL maks=pref[n];
	set<pair<LL,LL>>s;
	// t dan lds nya
	s.insert(mp(arr[n],suff[n]));
	for(LL a=n-1;a>=1;a--)
	{
		// jika t nya lebih besar maka hasilnya semakin kecil
		auto ambil = s.lower_bound(mp(arr[a]-x+1,0));
		if(ambil==s.end())maks=max(maks,pref[a]);
		else
		{
			pair<LL,LL>x=*ambil;
			maks=max(maks,pref[a]+x.se);
		}
		while(s.lower_bound(mp(arr[a],1e9))!=s.begin())
		{
			auto koko=--s.lower_bound(mp(arr[a],1e9));
			pair<LL,LL>jeje=*koko;
			if(jeje.second<=suff[a])
			{
				s.erase(jeje);
			}else break;
		}
		auto jeje=*s.lower_bound(mp(arr[a]-1,1e9));
		if(!s.empty() && s.lower_bound(mp(arr[a]-1,1e9))!=s.end() && jeje.second>=suff[a])
		{
			
		}else s.insert(mp(arr[a],suff[a]));
	}
	printf("%lld\n",maks);
}

Compilation message (stderr)

glo.cpp: In function 'int main()':
glo.cpp:10:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   10 |  scanf("%lld %lld",&n,&x);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~
glo.cpp:14:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   14 |   scanf("%lld",&arr[a]);
      |   ~~~~~^~~~~~~~~~~~~~~~

• 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