제출 #72890

#제출 시각아이디문제언어결과실행 시간메모리
72890zscoderGlobal Warming (CEOI18_glo)C++17
100 / 100
181 ms6372 KiB
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
 
using namespace std;
using namespace __gnu_pbds;
 
#define fi first
#define se second
#define mp make_pair
#define pb push_back
 
typedef long long ll;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef long double ld; 
typedef tree<ii, null_type, less<ii>, rb_tree_tag, tree_order_statistics_node_update> pbds;

int a[222222];
int P[222222];
int S[222222];

struct Fenwick
{
	vi fen;
	int n;
	void init(int _n)
	{
		n=_n; fen.clear();
		fen.resize(n+1,0);
	}
	void update(int pos, int v)
	{
		pos++;
		for(;pos<=n;pos+=(pos&(-pos)))
		{
			fen[pos]=max(fen[pos],v);
		}
	}
	int get(int pos)
	{
		if(pos<0) return 0;
		pos++;
		int ans=0;
		for(;pos;pos-=(pos&(-pos)))
		{
			ans=max(ans,fen[pos]);
		}
		return ans;
	}
};

vi coord;
int id[222222];

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	int n, x; cin>>n>>x;
	for(int i=0;i<n;i++)
	{
		cin>>a[i]; coord.pb(a[i]);
	}
	sort(coord.begin(),coord.end()); coord.erase(unique(coord.begin(),coord.end()),coord.end());
	for(int i=0;i<n;i++)
	{
		id[i] = lower_bound(coord.begin(),coord.end(),a[i])-coord.begin();
	}
	Fenwick fen; fen.init(n+1);
	for(int i=0;i<n;i++)
	{
		P[i] = fen.get(id[i]-1)+1;
		fen.update(id[i],P[i]);
	}
	fen.init(n+1);
	for(int i=n-1;i>=0;i--)
	{
		S[i] = fen.get(n-id[i]-1)+1;
		fen.update(n-id[i],S[i]);
	}
	int ans=P[n-1];
	Fenwick fen2; fen2.init(n+1);
	for(int j=0;j<n;j++)
	{
		int lb = lower_bound(coord.begin(),coord.end(),a[j]+x)-coord.begin();
		ans=max(ans, S[j]+fen2.get(lb-1));
		fen2.update(id[j],P[j]);
	}
	cout<<ans<<'\n';
}
#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...