Submission #653850

#	Time	Username	Problem	Language	Result	Execution time	Memory
653850		Juan	Global Warming (CEOI18_glo)	C++17	0 / 100	181 ms	8484 KiB

glo

#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[i] = mx(id-1, 1)+1;// lds usando sufixo, v[i] incluso
		upd(id, sz_lds[i], 1);
	}

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

	cout << ans << '\n';
}

• 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