Submission #1182191

#	Time	Username	Problem	Language	Result	Execution time	Memory
1182191		boclobanchat	Global Warming (CEOI18_glo)	C++20	100 / 100	76 ms	3400 KiB

glo

#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));
}

• 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