제출 #667527

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
667527		Augustyn	Global Warming (CEOI18_glo)	C++14	100 / 100	297 ms	16308 KiB

glo

#include<bits/stdc++.h>
using namespace std;
unsigned n,x,b[200001],pod=1,a[524288];
unsigned drze[524288][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;
}

컴파일 시 표준 에러 (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: 10 / 10
• Subtask 5: 20 / 20
• Subtask 6: 17 / 17
• Subtask 7: 25 / 25