Submission #482505

#	Time	Username	Problem	Language	Result	Execution time	Memory
482505		ArianKheirandish	Global Warming (CEOI18_glo)	C++14	100 / 100	326 ms	24388 KiB

glo

// in the name of God//

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define all(x)	x.begin(),x.end()
#define F		first
#define S		second
#define MP		make_pair

const int maxn = 4e5 + 20;
ll n, x, ans;
ll a[2][maxn], dp[maxn], pd[maxn];
ll seg[maxn << 2];

void Update(int idx, ll val, int id = 1, int l = 1, int r = maxn){
	if(l == r - 1){
		seg[id] = max(seg[id], val);
		return;
	}

	int mid = (l + r) >> 1;
	if(idx < mid)
		Update(idx, val, id << 1, l, mid);
	else
		Update(idx, val, id << 1 | 1, mid, r);

	seg[id] = max(seg[id << 1], seg[id << 1 | 1]);
}

ll Get(int l, int r, int id = 1, int L = 1, int R = maxn){
	if(R <= l || r <= L)
		return 0;

	if(l <= L && R <= r)
		return seg[id];

	int mid = (L + R) >> 1;
	return max(Get(l, r, id << 1, L, mid), 
				Get(l, r, id << 1 | 1, mid, R));
}

vector<ll> v;

int main(){
	ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);

	cin >> n >> x;
	for(int i = 1 ; i <= n ; i ++){
		cin >> a[0][i];
		v.push_back(a[0][i]);
		v.push_back(a[1][i] = a[0][i] + x);
	}

	sort(all(v));
	v.resize(unique(all(v)) - v.begin());

	for(int i = 1 ; i <= n ; i ++){
		a[0][i] = lower_bound(all(v), a[0][i]) - v.begin() + 1;
		a[1][i] = lower_bound(all(v), a[1][i]) - v.begin() + 1;
	}

	for(int i = n ; i >= 1 ; i --){
		dp[i] = Get(a[1][i] + 1, maxn - 1) + 1ll;
		ans = max(ans, dp[i]);
		Update(a[1][i], dp[i]);
	}
	
	ans = max(ans, seg[1]);
	
	for(int i = 0 ; i < (maxn << 2) ; i ++)
		seg[i] = 0;

	for(int i = 1 ; i <= n ; i ++){
		ll tmp = Get(1, a[1][i]) + dp[i];
		pd[i] = Get(1, a[0][i]) + 1;
		ans = max(ans, tmp);
		Update(a[0][i], pd[i]);
	}
	
	ans = max(ans, seg[1]);
	cout << ans << '\n';

	return 0;
}

/*
	Hasbi Allah	
*/

• 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