Submission #617193

#	Time	Username	Problem	Language	Result	Execution time	Memory
617193		AKaan37	Lottery (CEOI18_lot)	C++17	0 / 100	3 ms	388 KiB

lot

#include <bits/stdc++.h>
using namespace std;




typedef pair <int,int> ii;



int n;
int k;

vector <int> s;

set <ii> st;


int ans;


vector <int> fr;


int main()
{
	scanf("%d %d",&n,&k);

	s.resize(n);
	fr.resize(n);

	for(int i=0;i<n;i++)
	{
		scanf(" %d",&s[i]);
	}

	reverse(s.begin(),s.end());

	for(int i=0;i<n;i++)
	{
		s[i]=-s[i];
	}

	for(int i=0;i<n;i++)
	{
		int a=s[i];

		auto it=st.upper_bound(ii(-a,n+5));

		ii res;

		if(it==st.end())
		{
			res=ii(-a,1);
		}

		else
		{
			res=ii(-a,it->second+1);
		}

		if(i==7)
		{
			//printf("\n%d %d\n\n",res.first,res.second);
		}

		st.insert(res);

		it=st.find(res);

		while(it!=st.begin())
		{
			it--;

			if(it->second<=res.second)
			{
				st.erase(it);
			}

			else
			{
				break;
			}

			it=st.find(res);
		}

		ans=max(ans,res.second);
		fr[i]=res.second;
	}

	reverse(s.begin(),s.end());
	reverse(fr.begin(),fr.end());
	
	for(int i=0;i<n;i++)
	{
		s[i]=-s[i];
	}

	st.clear();

	for(int i=0;i<n;i++)
	{
		int a=s[i];

		auto it=st.upper_bound(ii(-(a+k),n+5));

		if(it!=st.end())
		{
			ans=max(ans,it->second+fr[i]);

			//printf("\n%d %d %d %d\n\n",-it->first,it->second,i,fr[i]);
		}

		ii res;

		it=st.upper_bound(ii(-a,n+5));

		if(it==st.end())
		{
			res=ii(-a,1);
		}

		else
		{
			res=ii(-a,it->second+1);
		}

		if(i==7)
		{
			//printf("\n%d %d\n\n",res.first,res.second);
		}

		st.insert(res);

		it=st.find(res);

		while(it!=st.begin())
		{
			it--;

			if(it->second<=res.second)
			{
				st.erase(it);
			}

			else
			{
				break;
			}

			it=st.find(res);
		}

		ans=max(ans,res.second);
	}

	/*for(auto it=st.begin();it!=st.end();it++)
	{
		printf("%d %d\n",it->first,it->second);
	}*/

	printf("%d\n",ans);
}

Compilation message (stderr)

lot.cpp: In function 'int main()':
lot.cpp:27:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   27 |  scanf("%d %d",&n,&k);
      |  ~~~~~^~~~~~~~~~~~~~~
lot.cpp:34:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   34 |   scanf(" %d",&s[i]);
      |   ~~~~~^~~~~~~~~~~~~

• Subtask 1: 0 / 25
• Subtask 2: 0 / 20
• Subtask 3: 0 / 20
• Subtask 4: 0 / 15
• Subtask 5: 0 / 20