Submission #667524

#	Time	Username	Problem	Language	Result	Execution time	Memory
667524		Augustyn	Global Warming (CEOI18_glo)	C++14	48 / 100	205 ms	14040 KiB

glo

#include<bits/stdc++.h>
using namespace std;
unsigned n,x,b[200001],pod=1,a[200001];
unsigned drze[1000001][2];
unordered_map<unsigned,unsigned>skal;
void aktu(unsigned gdzie,unsigned kd,unsigned naile)
{
	while(gdzie)
	{
		drze[gdzie][kd]=max(drze[gdzie][kd],naile);
		gdzie>>=1;
	}
}
unsigned maxnapref(unsigned ter,unsigned pocz,unsigned kon,unsigned dokad,unsigned kd)
{
	if(a[kon]<=dokad)
	{
		return drze[ter][kd];
	}
	if(a[(pocz+kon)/2+1]<=dokad)
		return max(drze[ter<<1][kd],maxnapref((ter<<1)^1,(pocz+kon)/2+1,kon,dokad,kd));
	else if(a[pocz]<=dokad)
		return maxnapref(ter<<1,pocz,(pocz+kon)>>1,dokad,kd);
	return 0;
}
int main()
{
	scanf("%u%u",&n,&x);
	while(pod<n)
		pod<<=1;
	for(unsigned i=0;i<n;++i)
	{
		scanf("%u",&a[i]);
		b[i]=a[i];
	}
	sort(a,a+n);
	for(unsigned i=0;i<n;++i)
		skal[a[i]]=i;
	for(unsigned i=n;i<pod;++i)
		a[i]=4294967295;
	unsigned w1,w2;
	for(unsigned i=0;i<n;++i)
	{
		w1=maxnapref(1,0,pod-1,b[i]-1,0)+1;
		w2=max(maxnapref(1,0,pod-1,b[i]-1,1),maxnapref(1,0,pod-1,b[i]+x-1,0))+1;
		aktu(skal[b[i]]+pod,0,w1);
		aktu(skal[b[i]]+pod,1,w2);
	}
	printf("%u",max(drze[1][0],drze[1][1]));
	return 0;
}

Compilation message (stderr)

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

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