Submission #720809

#	Time	Username	Problem	Language	Result	Execution time	Memory
720809		a_aguilo	Global Warming (CEOI18_glo)	C++14	100 / 100	382 ms	17160 KiB

glo

#include<bits/stdc++.h>

using namespace std;

int N, X;
vector<int> temperatures, auxiliar, LIS, lengthOfLisByValue, segTree, previousValInPosition;
unordered_map<int, int> positionOrder;

void print(vector<int>&V){
	for(int n: V) cout << n << " ";
	cout << endl;
}

int binarySearchCrescent(int t){
	int lo = 0, hi = N-1;
	int ans = 0;
	while(lo <= hi){
		int mid = lo + (hi - lo)/2;
		if(LIS[mid] < t){
			ans = mid+1;
			lo = mid+1;
		}else hi = mid-1;
	}
	return min(ans, N-1);
}

void buildTree(int node, int left, int right, vector<int>& arr){
	if(left > right) return;
	if(left == right){
		segTree[node] = arr[left];
		return;
	}
	int mid = left + (right - left)/2;
	buildTree(2*node, left, mid, arr);
	buildTree(2*node+1, mid+1, right, arr);
	segTree[node] = max(segTree[2*node], segTree[2*node+1]);
}

void modifyPos(int node, int left, int right, int pos, int newVal){
	if(left > pos or right < pos) return;
	if(left == right){
		segTree[node] = newVal;
		return;
	}
	int mid = left + (right - left)/2;
	modifyPos(2*node, left, mid, pos, newVal);
	modifyPos(2*node+1, mid+1, right, pos, newVal);
	segTree[node] = max(segTree[2*node], segTree[2*node+1]);
}

int query(int node, int lBound, int rBound, int left, int right){
	if(right < left) return 0;
	if(lBound > right or rBound < left) return 0;
	if(lBound>=left && rBound<=right) return segTree[node];
	int mid = lBound + (rBound - lBound)/2;
	return max(query(2*node, lBound, mid, left, right), query(2*node+1, mid+1, rBound, left, right));
}

void rellenarPrimerLIS(){
	//Perfecto
	lengthOfLisByValue = vector<int>(N, 0);
	previousValInPosition = vector<int>(N);
	LIS = vector<int>(N, 1e9+7);
	//Crescent LIS
	for(int i = 0; i < N; ++i){
		int position = binarySearchCrescent(temperatures[i]);
		//You find where to put it in the crescent LIS
		LIS[position] = min(LIS[position], temperatures[i]);
		int length = position+1;
		//cout << "Temperatura: " << temperatures[i] << "\t tamaño de LIS: " << length << endl;
		//cout << position << endl;
		//you save what whas there before
		previousValInPosition[i] = lengthOfLisByValue[positionOrder[temperatures[i]]];
		//You save that for that VALUE the maximum LIS ending in that is what you've found
		lengthOfLisByValue[positionOrder[temperatures[i]]] = length;
	}
}

int binarySearchLimit(long long t){
	int lo = 0, ans = -1, hi = N-1;
	while(lo <= hi){
		int mid = lo + (hi - lo)/2;
		if(auxiliar[mid] < t){
			lo = mid+1;
			ans = mid;
		}else hi = mid-1;
	}
	return ans;
}

int rellenarSegundoLIS(){
	LIS = vector<int>(N, 1e9);
	segTree = vector<int>(4*N);
	buildTree(1, 0, N-1, lengthOfLisByValue);
	int ans = 1;
	for(int i = N-1; i >= 0; --i){
		//LIS Decreciente
		int positionDecrescent = binarySearchCrescent(-temperatures[i]);
		LIS[positionDecrescent] = -temperatures[i];
		int length = positionDecrescent+1;
		//cout << "Temperatura: " << temperatures[i] << "\t Longitud segundo LIS: " << length << endl;
		//Combinar con las soluciones previas
		//deshacer lo puesto
		lengthOfLisByValue[positionOrder[temperatures[i]]] = previousValInPosition[i];
		//cout << previousValInPosition[i] << endl;
		//de manera q no interfiera con la query
		modifyPos(1, 0, N-1, positionOrder[temperatures[i]], previousValInPosition[i]);
		long long limitVal = (long long)temperatures[i] + (long long)X;
		int LimitPos = binarySearchLimit(limitVal);
		//cout << "Query en el rango [" << 0 <<", " << LimitPos << "]" << endl;
		int otherLIS = query(1, 0, N-1, 0, LimitPos);
		//print(lengthOfLisByValue);
		//cout << "Position until which get the LIS: " << LimitPos << "\t Other LIS value: " << otherLIS << "\t the total value of LIS: " << length + otherLIS << endl;
		ans = max(ans, length+otherLIS);
		//de manera que vuelva a lo anterior
	}
	return ans;
}

signed main(){
	cin >> N >> X;
	temperatures = vector<int>(N);
	auxiliar = vector<int>(N);
	for(int i = 0; i < N; ++i){
		cin >> temperatures[i];
		auxiliar[i] = temperatures[i];
	}
	//cout << "Data entry" << endl;
	//setting the positions for values - a.k.a. coordinate compression
	positionOrder.reserve(N);
	sort(auxiliar.begin(), auxiliar.end());
	for(int i = 0; i < N; ++i){
		if(positionOrder.find(auxiliar[i]) == positionOrder.end()){
			positionOrder[auxiliar[i]] = i;
			//cout << "Temperatura: " << auxiliar[i] <<"\t posicion relativa: " << positionOrder[auxiliar[i]] << endl;
		}
	}
	rellenarPrimerLIS();
	//cout << "Primer LIS ok" << endl;
	cout << rellenarSegundoLIS() << endl;
	return 0;
}

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 13 / 13
• Subtask 4: 10 / 10
• Subtask 5: 20 / 20
• Subtask 6: 17 / 17
• Subtask 7: 25 / 25