제출 #1311945

#제출 시각아이디문제언어결과실행 시간메모리
1311945kevinsGlobal Warming (CEOI18_glo)C++20
100 / 100
163 ms11500 KiB
#include <bits/stdc++.h>
using namespace std;
#define ll long long
struct fen{
	vector <ll> bit;
	ll n;
	fen(ll _n){
		n = _n;
		bit.resize(n+1, 0);
	}
	void upd(ll f, ll v){
		while (f <= n){
			bit[f] = max(bit[f], v);
			f += (f&(-f));
		}
	}

	ll qry(ll f){
		ll rm = 0;
		while (f > 0){
			rm = max(rm, bit[f]);
			f -= (f&(-f));
		}
		return rm;
	}
};
int main(){
	//we can decrease a prefix of the array by d or increase a suffix by d optimimally
	//we will increase a suffix by d
	//let dp[i][j] denote maximum lis from 1 to i, with j being a boolean flag of whether we have started increasing or not
	//dp[i][1] = max( max((dp[k][1] + 1), where 1 <= k < i and a[k] < a[i]), max((dp[k][0] + 1), where 1 <= k < i and a[k] < a[i]+d) )
	//dp[i][0] = max(dp[k][0] + 1)

	ll n, x;
	cin >> n >> x;

	ll a[n+1];
	vector <ll> dis;
	for (ll i = 1; i <= n; ++i){
		cin >> a[i];
		dis.push_back(a[i]);
		dis.push_back(a[i] + x);
	}

	sort(dis.begin(), dis.end());
	dis.erase(unique(dis.begin(), dis.end()), dis.end());

	auto compress = [&](ll v){
		return lower_bound(dis.begin(), dis.end(), v) - dis.begin() + 1;
	};

	fen* fw0 = new fen(dis.size()+1); //bool flag = 0
	fen* fw1 = new fen(dis.size()+1); //bool flag = 1

	ll running = 0;
	
	ll com1 = compress(a[1]);
	fw0->upd(com1, 1);
	fw1->upd(com1, 1);

	for (ll i = 2; i <= n; ++i){
		ll disVal = compress(a[i]);
		ll dpOne1 = fw1->qry(disVal-1) + 1;
		ll dpOne2 = fw0->qry(compress(a[i] + x) - 1) + 1;
		ll dpZero = fw0->qry(disVal-1) + 1;

		fw1->upd(disVal, max(dpOne1, dpOne2));
		fw0->upd(disVal, dpZero);
		running = max(running, max(max(dpOne1, dpOne2), dpZero));
	}

	cout << running << "\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...