oj.uz

Submission #617193

# Submission time Handle Problem Language Result Execution time Memory
617193 2022-08-01T09:30:48 Z AKaan37 Lottery (CEOI18_lot) C++17
0 / 100
 3 ms 388 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 388 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 388 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -