제출 #825952

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
825952		sentheta	Global Warming (CEOI18_glo)	C++17	100 / 100	67 ms	6960 KiB

glo

// author : sentheta aka vanwij
#ifdef VANWIJ
	#include"/home/user/code/bits/stdc++.h"
	#define DBG 1
#else
	#include"bits/stdc++.h"
	#define DBG 0
#endif
using namespace std;

#define Int long long
#define V vector
#define pii pair<int,int>
#define ff first
#define ss second

static mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

#define pow2(x) (1LL<<(x))
#define msb(x) (63-__builtin_clzll(x))
#define bitcnt(x) (__builtin_popcountll(x))

#define nl '\n'
#define _ << ' ' <<
#define all(x) (x).begin(), (x).end()
#define rep(i,a,b) for(int i = (int)(a); i < (int)(b); i++)

#define cerr if(DBG) cout
#define dbg(x) {cerr << "?" << #x << " : " << (x) << endl << flush;}

#define int long long
// const Int MOD = 1e9+7;
const Int MOD = 998244353;
Int bpow(Int a,Int b){
	Int ret = 1;
	for(;b; a=a*a%MOD,b/=2) if(b&1) ret = ret*a%MOD;
	return ret;
}
Int inv(Int a){return bpow(a,MOD-2);}

void solve(); int TC, ALLTC;
signed main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cout << fixed << setprecision(7);
	// cin >> ALLTC; for(TC=1; TC<=ALLTC; TC++) solve(); return 0;
	solve();
}








const int N = 2e5+5;
const int LN = 18;
const int INF = 1e18;

int n, x;
int a[N];


int dp[N];

int suf[N];



void solve(){
	
	cin >> n >> x;
	
	rep(i,1,n+1){
		cin >> a[i];
	}
	
	int ans = 0;
	
	// dp[len] = max possible beginning of length len
	rep(i,0,N) dp[i] = -INF;
	dp[0] = INF;
	for(int i=n; i>=1; i--){
		// LIS
		int len = 0;
		for(int J=1<<LN; J; J/=2)
			if(len+J<n && a[i]<dp[len+J]) len+=J;
		len++;
		dp[len] = max(dp[len], a[i]);
		
		suf[i] = max(suf[i], len);
	}
	ans = suf[1];
	
	
	
	// dp[len] = min possible ending of length len
	rep(i,0,N) dp[i] = INF;
	dp[0] = -INF;
	for(int i=1; i<=n-1; i++){
		dbg(i);
		
		// LIS
		int len = 0;
		for(int J=1<<LN; J; J/=2)
			if(len+J<n && dp[len+J]<a[i]) len+=J;
		len++;
		dp[len] = min(dp[len], a[i]);
		dbg(len);
		
		// add X to suffix
		len = 0;
		for(int J=1<<LN; J; J/=2)
			if(len+J<n && dp[len+J] < a[i+1]+x) len+=J;
		ans = max(ans, len+suf[i+1]);
		dbg(len);
	}
	
	cout << ans << nl;
	
	

	
	
	
	
}

• 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