Submission #1016409

#	Time	Username	Problem	Language	Result	Execution time	Memory
1016409		vjudge1	Global Warming (CEOI18_glo)	C++17	100 / 100	213 ms	11856 KiB

glo

#include <bits/stdc++.h>
using namespace std;
 
#define ll long long
#define ld long double
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pld pair<ld, ld>
#define pb push_back
#define fi first
#define se second
#define debug(x) cout << #x << " => " << x << endl
#define all(x) x.begin(),x.end()

int dp[2][200010];
int tree[2][800010];

void update1(int idx,int l,int r,int x,int v)
{
	if(l==r)
	{
		tree[0][idx]=v;
		return;
	}

	int mid=(l+r)/2;
	if(x<=mid) update1(idx*2,l,mid,x,v);
	else update1(idx*2+1,mid+1,r,x,v);
	tree[0][idx]=max(tree[0][idx*2],tree[0][idx*2+1]);
}

void update2(int idx,int l,int r,int x,int v)
{
	if(l==r)
	{
		tree[1][idx]=v;
		return;
	}

	int mid=(l+r)/2;
	if(x<=mid) update2(idx*2,l,mid,x,v);
	else update2(idx*2+1,mid+1,r,x,v);
	tree[1][idx]=max(tree[1][idx*2],tree[1][idx*2+1]);
}

int query1(int idx,int l,int r,int x,int y)
{
	if(x<=l && r<=y) return tree[0][idx];
	if(r<x || y<l) return 0;

	int mid=(l+r)/2;
	return max(query1(idx*2,l,mid,x,y),query1(idx*2+1,mid+1,r,x,y));
}

int query2(int idx,int l,int r,int x,int y)
{
	if(x<=l && r<=y) return tree[1][idx];
	if(r<x || y<l) return 0;

	int mid=(l+r)/2;
	return max(query2(idx*2,l,mid,x,y),query2(idx*2+1,mid+1,r,x,y));
}

int main()
{
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int n,x;cin>>n>>x;
	vector<int> a(n+1),b;
	for(int i=1;i<=n;i++) cin>>a[i];
	a[0]=-1;
	b=a;
	sort(all(b));
	b.erase(unique(all(b)),b.end());
	int m=b.size();
	m--;

	int ans=0;
	for(int i=1;i<=n;i++)
	{
		int pos=lower_bound(all(b),a[i])-b.begin();
		int pos2=lower_bound(all(b),a[i]+x)-b.begin();
		if(i==1) dp[0][i]=dp[1][i]=1;
		else
		{
			dp[0][i]=query1(1,1,m,1,pos-1)+1;
			dp[1][i]=max(query1(1,1,m,1,pos2-1),query2(1,1,m,1,pos-1))+1;
		}
		update1(1,1,m,pos,dp[0][i]);
		update2(1,1,m,pos,dp[1][i]);
		ans=max(ans,max(dp[0][i],dp[1][i]));
		// for(int j=1;j<=n;j++) debug(query1(1,1,m,j,j));
		// for(int j=1;j<=n;j++) debug(query2(1,1,m,j,j));
	}
	cout<<ans;
	return 0;
}

• 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