Submission #653792

#	Time	Username	Problem	Language	Result	Execution time	Memory
653792		Juan	Global Warming (CEOI18_glo)	C++17	0 / 100	91 ms	4160 KiB

glo

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

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

void upd(int x, int val){
	for(; x < 2*maxn; x+=x&-x) {bit[x] = max(bit[x], val);}
}
int mx(int x){
	int rt = 0;
	for(; x>0; x-=x&-x) rt = max(rt, bit[x]);
	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 x; cin >> n >> x;
	x = -abs(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)

	for(int i = 0; i < n; i++){
		int id1 = bbin(v[i]);
		int id2 = bbin(v[i]+x);
		int sz_lis1 = mx(id1-1)+1;
		int sz_lis2 = mx(id2-1)+1;
		upd(id1, sz_lis1);
		upd(id2, sz_lis2);
	}

	cout << mx(2*maxn-1) << '\n';
}

Compilation message (stderr)

glo.cpp: In function 'int bbin(int)':
glo.cpp:26:12: warning: 'rt' may be used uninitialized in this function [-Wmaybe-uninitialized]
   26 |  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