Submission #128144

#	Time	Username	Problem	Language	Result	Execution time	Memory
128144		TadijaSebez	Global Warming (CEOI18_glo)	C++11	100 / 100	451 ms	13572 KiB

glo

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
const int N=200050;
const int lim=2*N;
const int M=2*lim;
int hi[N],lo[N],l[N],r[N];
vector<int> id;
int ls[M],rs[M],mx[M],tsz,root;
void Set(int &c, int ss, int se, int qi, int x)
{
	if(!c) c=++tsz;
	mx[c]=max(mx[c],x);
	if(ss==se) return;
	int mid=ss+se>>1;
	if(qi<=mid) Set(ls[c],ss,mid,qi,x);
	else Set(rs[c],mid+1,se,qi,x);
}
int Get(int c, int ss, int se, int qs, int qe)
{
	if(qs>qe || qs>se || ss>qe) return 0;
	if(qs<=ss && qe>=se) return mx[c];
	int mid=ss+se>>1;
	return max(Get(ls[c],ss,mid,qs,qe),Get(rs[c],mid+1,se,qs,qe));
}
void Clear()
{
	for(int i=1;i<=tsz;i++) ls[i]=rs[i]=mx[i]=0;
	tsz=root=0;
}
int main()
{
	int n,x;
	scanf("%i %i",&n,&x);
	for(int i=1;i<=n;i++)
	{
		scanf("%i",&hi[i]);
		lo[i]=hi[i]-x;
		id.pb(hi[i]);
		id.pb(lo[i]);
	}
	sort(id.begin(),id.end());
	id.resize(unique(id.begin(),id.end())-id.begin());
	for(int i=1;i<=n;i++)
	{
		hi[i]=lower_bound(id.begin(),id.end(),hi[i])-id.begin()+1;
		lo[i]=lower_bound(id.begin(),id.end(),lo[i])-id.begin()+1;
	}
	for(int i=1;i<=n;i++)
	{
		l[i]=Get(root,1,lim,1,hi[i]-1)+1;
		Set(root,1,lim,lo[i],Get(root,1,lim,1,lo[i]-1)+1);
	}
	Clear();
	for(int i=n;i>=1;i--)
	{
		r[i]=Get(root,1,lim,hi[i]+1,lim)+1;
		Set(root,1,lim,hi[i],r[i]);
	}
	int ans=0;
	for(int i=1;i<=n;i++) ans=max(ans,l[i]+r[i]-1);
	printf("%i\n",ans);
	return 0;
}

Compilation message (stderr)

glo.cpp: In function 'void Set(int&, int, int, int, int)':
glo.cpp:15:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid=ss+se>>1;
          ~~^~~
glo.cpp: In function 'int Get(int, int, int, int, int)':
glo.cpp:23:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid=ss+se>>1;
          ~~^~~
glo.cpp: In function 'int main()':
glo.cpp:34:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%i %i",&n,&x);
  ~~~~~^~~~~~~~~~~~~~~
glo.cpp:37:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%i",&hi[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