Submission #1182191

#TimeUsernameProblemLanguageResultExecution timeMemory
1182191boclobanchatGlobal Warming (CEOI18_glo)C++20
100 / 100
76 ms3400 KiB
#include<bits/stdc++.h>
using namespace std;
const int MAXN=2e5+5;
int val[MAXN],fen[MAXN][2],A[MAXN];
void update(int i,int c,int n,int val) { for(;i<=n;i+=i&-i) fen[i][c]=max(fen[i][c],val); }
int get(int i,int c) { int ans=0;for(;i;i-=i&-i) ans=max(ans,fen[i][c]);return ans; }
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n,d;
	cin>>n>>d;
	for(int i=1;i<=n;i++)
	{
		cin>>A[i];
		val[i]=A[i];
	}
	sort(val+1,val+n+1);
	for(int i=1;i<=n;i++)
	{
		int v=A[i];
		A[i]=lower_bound(val+1,val+n+1,v)-val;
		int dp0=get(A[i]-1,0);
		int dp1=max(get(A[i]-1,1),get(lower_bound(val+1,val+n+1,v+d)-val-1,0));
		update(A[i],0,n,dp0+1);
		update(A[i],1,n,dp1+1);
	}
	cout<<max(get(n,0),get(n,1));
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...