Submission #657377

#	Time	Username	Problem	Language	Result	Execution time	Memory
657377		teesla	Global Warming (CEOI18_glo)	C++14	0 / 100	111 ms	3792 KiB

glo

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

int v[maxn],lis[maxn],lds[maxn],ida[maxn],volta[maxn];

int busca(int i, int f, int x){
	int res=1;
	while(i<=f){
		int mid=(i+f)/2;

		if(lis[mid]>=x or lis[mid]==0)f=mid-1;

		else{
			i=mid+1;
			res=mid+1;
		}
	}
	return res;
}

int busca2(int i, int f, int x){
	int res=1; 

	while(i<=f){
		int mid=(i+f)/2;

		if(lds[mid]<=x) f=mid-1;
		else{
			i=mid+1;
			res=mid+1;
		}
	}
	return res;
}

int main(){

	int n,x;
	cin >> n>> x;

	for(int i=1; i<=n; i++)cin >> v[i];

	for(int i=1; i<=n; i++){//v[i] faz parte da lis final
		int j= busca(1,n,v[i]);// pos do menor maior que v[i]
		lis[j]=v[i];
		ida[i]=j;
	}

	for(int i=n; i>=1; i--){
		int j=busca2(1,n,v[i]-x);// pos do menor >v[i]-x (tam lds)
		volta[j]=j;

		int k=busca2(1,n,v[i]);//lds normal para colocar na lista
		lds[k]=v[i];
	}

	int res=0;

	for(int i=1; i<=n; i++){
		res=max(res,ida[i]+volta[i]);
	}
	cout << res<<endl;
	return 0;
}

• 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