Submission #580495

#TimeUsernameProblemLanguageResultExecution timeMemory
580495amunduzbaevGlobal Warming (CEOI18_glo)C++17
100 / 100
424 ms16692 KiB
#include "bits/stdc++.h"
using namespace std;
 
#define ar array
typedef int64_t ll;
#define int ll

const int N = 4e5 + 5;
int a[N];

struct ST{
	int tree[N << 2];
	void sett(int i, int v, int lx = 0, int rx = N, int x = 1){
		if(lx == rx) { tree[x] = v; return; }
		int m = (lx + rx) >> 1;
		if(i <= m) sett(i, v, lx, m, x << 1);
		else sett(i, v, m + 1, rx, x << 1 | 1);
		tree[x] = max(tree[x << 1], tree[x << 1 | 1]);
	}
	
	int get(int l, int r, int lx = 0, int rx = N, int x = 1){
		if(lx > r || rx < l) return 0;
		if(lx >= l && rx <= r) return tree[x];
		int m = (lx + rx) >> 1;
		return max(get(l, r, lx, m, x << 1), get(l, r, m + 1, rx, x << 1 | 1));
	}
}tree;
int pref[N], suff[N];

signed main(){
	ios::sync_with_stdio(0); cin.tie(0);
	
	int n, x; cin>>n>>x;
	vector<int> t;
	for(int i=0;i<n;i++){
		cin>>a[i];
		t.push_back(a[i]);
		t.push_back(a[i] - x);
	}
	
	sort(t.begin(), t.end());
	t.erase(unique(t.begin(), t.end()), t.end());
	for(int i=0;i<n;i++){
		int p = lower_bound(t.begin(), t.end(), a[i]) - t.begin() + 1;
		pref[i] = tree.get(0, p - 1) + 1;
		tree.sett(p, pref[i]);
	}
	for(int i=0;i<N;i++) tree.sett(i, 0);
	
	for(int i=n-1;~i;i--){
		int p = upper_bound(t.begin(), t.end(), a[i]) - t.begin() + 1;
		int tmp = tree.get(p, N - 1);
		int p2 = upper_bound(t.begin(), t.end(), a[i] - x) - t.begin() + 1;
		suff[i] = tree.get(p2, N - 1);
		tree.sett(p - 1, tmp + 1);
	}
	
	int res = 0;
	for(int i=0;i<n;i++){
		res = max(res, pref[i] + suff[i]);
	}
	//~ for(int i=0;i<n;i++){
		//~ cout<<pref[i]<<" ";
	//~ } cout<<"\n";
	//~ for(int i=0;i<n;i++){
		//~ cout<<suff[i]<<" ";
	//~ } cout<<"\n";
	
	cout<<res<<"\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...