제출 #99107

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
99107		thiago4532	Global Warming (CEOI18_glo)	C++17	0 / 100	997 ms	173132 KiB

glo

#include <bits/stdc++.h>
#define int int64_t

using namespace std;
const int maxv = 2e9 + 10;
const int maxn = 2e5 + 10;
const int inf = 0x3f3f3f3f3f3f3f3fll;
int n, x;
int dp[maxn], dp2[maxn], v[maxn];

struct node{
	int v;
	node *l, *r;
	node(int v=0): v(v), l(0), r(0) {}
};

void update(node* no, int p, int v, int ini=0, int fim=maxv){
	if(ini == fim){
		no->v = max(no->v, v);
		return;
	}

	int meio = (ini+fim)>>1;
	if(p <= meio){
		if(!no->l) no->l = new node;
		update(no->l, p, v, ini, meio);
	}else{
		if(!no->r) no->r = new node;
		update(no->r, p, v, meio+1, fim);
	}
	no->v = max((no->l?no->l->v:0), (no->r?no->r->v:0));
}

int query(node* no, int l, int r, int ini=0, int fim=maxv){
	if(!no || ini > r || fim < l) return 0;
	else if(l <= ini && fim <= r) return no->v;

	int meio = (ini+fim)>>1;
	int p1 = (no->l?query(no->l, l, r, ini, meio):0);
	int p2 = (no->r?query(no->r, l, r, meio+1, fim):0);
	return max(p1, p2);
}

int32_t main() {
	ios::sync_with_stdio(false), cin.tie(0);
	cin >> n >> x;
	for(int i=1;i<=n;i++)
		cin >> v[i];

	dp[1] = 1, dp2[1] = 1;
	node *n1 = new node, *n2 = new node;

	for(int i=2;i<=n;i++){
		dp[i] = dp2[i] = 1;

		dp[i] = 1 + query(n1, 0, v[i]);
		dp2[i] = 1 + max((v[i]+x==0?0:query(n1, 0, v[i]+x-1)), query(n2, 0, v[i]));
		// if(i==2) cout << "DEBUG: " << query(n1, -maxv, v[i]+x-1) << " " << v[i]+x-1 << "\n";
		// for(int j=1;j<i;j++){
		// 	if(v[j] - x >= v[i]) continue;
		// 	dp2[i] = max(dp2[i], 1 + dp[j]);
		// 	if(v[j] >= v[i]) continue;
		// 	dp[i] = max(dp[i], 1 + dp[j]);
		// 	dp2[i] = max(dp2[i], 1 + dp2[j]);
		// }
		update(n1, v[i], dp[i]);
		update(n2, v[i], dp2[i]);
	}

	int ans=0;
	for(int i=1;i<=n;i++)
		ans = max(ans, dp2[i]);

	cout << ans << "\n";
	return 0;
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 10
• Subtask 3: 0 / 13
• Subtask 4: 0 / 10
• Subtask 5: 0 / 20
• Subtask 6: 0 / 17
• Subtask 7: 0 / 25