Submission #653827

#	Time	Username	Problem	Language	Result	Execution time	Memory
653827		Juan	Global Warming (CEOI18_glo)	C++17	0 / 100	188 ms	6628 KiB

glo

#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 5;

int v[maxn], bit[2*maxn][2], sz_lis[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;
	while(l<=r){
		int mid = (l+r)>>1;
		if(ids[mid] > x) r = mid-1;
		else if(ids[mid] < x) l = mid+1;
		else {rt = mid; break;}
	}
	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;
	for(int i = 0; i < n; i++){
		int id = bbin(v[i]-x);
		sz_lis[i+1] = mx(id-1, 0)+1;
		upd(id, sz_lis[i+1], 0);
	}
	reverse(v, v+n);
	for(int i = 0; i < n; i++){
		int id = bbin(v[i]);
		id = 2*n+2-id;
		int sz_lds = mx(id-1, 1)+1;
		ans = max( ans, sz_lds+sz_lis[n-i-1] );
		upd(id, sz_lds, 1);
	}

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

Compilation message (stderr)

glo.cpp: In function 'int bbin(int)':
glo.cpp:25:12: warning: 'rt' may be used uninitialized in this function [-Wmaybe-uninitialized]
   25 |  return rt+1;
      |            ^

• 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