제출 #1268207

#제출 시각아이디문제언어결과실행 시간메모리
1268207WH8Global Warming (CEOI18_glo)C++20
100 / 100
165 ms25276 KiB
#include <bits/stdc++.h>
using namespace std;

#define int long long 
#define pll pair<int, int>
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define endl '\n'

const int maxn=500005;
int fw[2][500005];

int qry(int st, int x){
	int ret=0;
	while(x){
		ret=max(ret, fw[st][x]);
		x-=(x&(-x));
	}
	return ret;
}
void upd(int st, int x, int v){
	while(x <= maxn){
		fw[st][x]=max(fw[st][x],v);
		x+=(x&(-x));
	}
}

signed main(){
	int n,d;cin>>n>>d;
	vector<pair<int,int>> v(n);
	vector<int> t(n), disc;
	
	for(int i=0;i<n;i++){
		cin>>t[i];
		//~ cout<<t[i]<<" ";
		disc.pb(t[i]);
		disc.pb(t[i]+d);
	}
	//~ cout<<endl;
	sort(disc.begin(),disc.end());
	disc.erase(unique(disc.begin(),disc.end()),disc.end());
	for(int i=0;i<n;i++){
		v[i].f=lower_bound(disc.begin(),disc.end(),t[i])-disc.begin()+1;
		v[i].s=lower_bound(disc.begin(),disc.end(),t[i]+d)-disc.begin()+1;
		//~ cout<<v[i].f<<" "<<v[i].s<<endl;
	}
	vector<vector<int>> dp(n, vector<int>(2, 0));
	int ans=0;
	for(int i=0;i<n;i++){
		dp[i][0]=qry(0,v[i].f-1)+1;
		dp[i][1]=max(qry(0, v[i].s-1), qry(1, v[i].f-1))+1;
		upd(0, v[i].f, dp[i][0]);
		upd(1, v[i].f, dp[i][1]);
		ans=max({ans, dp[i][0],dp[i][1]});
		//~ printf("zero %lld one %lld\n",dp[i][0],dp[i][1]);
	}
	cout<<ans;
	
}
#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...