oj.uz

Submission #657377

# Submission time Handle Problem Language Result Execution time Memory
657377 2022-11-09T18:44:45 Z teesla Global Warming (CEOI18_glo) C++14
0 / 100
 111 ms 3792 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 111 ms 3792 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 32 ms 1104 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 53 ms 1976 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -