Submission #653855

#TimeUsernameProblemLanguageResultExecution timeMemory
653855JuanGlobal Warming (CEOI18_glo)C++17
100 / 100
235 ms8584 KiB
#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 5;

int v[maxn], bit[2*maxn][2], sz_lds[maxn];
vector<int> ids;

void upd(int x, int val, int t){
	for(; x < 2*maxn; x+=x&-x) {bit[x][t] = max(bit[x][t], val);}
}
int mx(int x, int t){
	int rt = 0;
	for(; x>0; x-=x&-x) rt = max(rt, bit[x][t]);
	return rt;
}

int bbin(int x){
	int l = 0, r = ids.size()-1, rt=0;
	while(l<=r){
		int mid = (l+r)>>1;
		if(ids[mid] >= x) rt=mid, r = mid-1;
		else l = mid+1;
	}
	return rt+1;
}

int main(){
	int n, x; cin >> n >> x;
	for(int i = 0; i < n; i++){
		cin >> v[i];
		ids.push_back(v[i]);
		ids.push_back(v[i]+x);
	}
	sort(ids.begin(), ids.end());
	ids.erase(unique(ids.begin(), ids.end()), ids.end());
	// todas as coordenadas que importam estão comprimidas. Para acessar
	// a coordenada comprimida use "bbin(val)" e ela retornará o id relativo (comprimido)
	// 0-indexado + 1

	int ans = 1;
	reverse(v, v+n);
	for(int i = 0; i < n; i++){
		int id = bbin(v[i]+x);
		id = 2*n+2-id;
		sz_lds[n-1-i] = mx(id-1, 1)+1;// lds usando sufixo {n-1,n-2,..., n-1 - i}, v[i] incluso
		upd(id, sz_lds[n-1-i], 1);
	}

	reverse(v, v+n);
	for(int i = 0; i < n; i++){
		int id_calc = bbin(v[i]+x);// id do limite da lis
		int sz_lis_calc = mx(id_calc-1, 0);
		ans = max(ans, sz_lis_calc + sz_lds[i]);

		int id = bbin(v[i]);
		int sz_lis = mx(id-1, 0)+1;
		upd(id, sz_lis, 0);
	}

	cout << ans << '\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...