제출 #161657

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
161657		amoo_safar	Global Warming (CEOI18_glo)	C++14	100 / 100	91 ms	10132 KiB

glo

#include <bits/stdc++.h>

#define pb push_back
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define debug(x) cerr << #x << " = " << x << endl
using namespace std;

typedef long long ll;
typedef long double ld;
typedef string str;
typedef pair<ll, ll> pll;

const ld PI = 3.14159265359;

ll MOD = (ll) 1e9 + 7;
const ll MAXN = (ll) 2e5 + 10;
const ll INF = (ll) (LONG_LONG_MAX - 3ll) / 2ll;
//const ll P = 104107;


ll dp1[MAXN], a[MAXN];
ll mn[MAXN];

void upd1(ll i){
	ll l = 1, r = MAXN;
	ll mid;
	while(l + 1 < r){
		mid = (l + r) >> 1;
		if(mn[mid - 1] < a[i]) l = mid;
		else r = mid;
	}
	dp1[i] = l;
	mn[l] = min(a[i], mn[l]);
}

ll dp2[MAXN], mx[MAXN];
void upd2(ll i){
	ll l = 1, r = MAXN;
	ll mid;
	while(l + 1 < r){
		mid = (l + r) >> 1;
		if(mx[mid - 1] > a[i]) l = mid;
		else r = mid;
	}
	dp2[i] = l;
	mx[l] = max(a[i], mx[l]);
}

int main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	memset(mn, 31, sizeof mn);
	fill(mx, mx + MAXN, -INF);
	ll n, x;
	cin >> n >> x;
	for(int i = 1; i <= n; i++) cin >> a[i];
	for(int i = 1; i <= n; i++) upd1(i);
	
	ll ans = *max_element(dp1 + 1, dp1 + n + 1);
	
	for(int i = n; i > 1; i--){
		upd2(i);
		ll l = 0, r = MAXN;
		ll mid;
		while(l + 1 < r){
			mid = (l + r) >> 1;
			if(mx[mid] > a[i - 1] - x) l = mid;
			else r = mid;
		}
		
		ans = max(ans, dp1[i - 1] + l);
	}
	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