Submission #810586

#TimeUsernameProblemLanguageResultExecution timeMemory
810586welleythGlobal Warming (CEOI18_glo)C++17
100 / 100
683 ms46892 KiB
#include <bits/stdc++.h>

using namespace std;

constexpr int N = (int)7e5;

int t[3][N];

void upd(int r,int d,int v){
	for(int i = r; i < N; i |= i+1)
		t[v][i] = max(t[v][i],d);
	return;
}
int get(int r,int v){
	int s = 0;
	for(int i = r; i >= 0; i &= i+1,i--){
		s = max(s,t[v][i]);
	}
	return s;
}

void solve(){
	int n,x;
	cin >> n >> x;

	int a[n+1];
	set<int> st;

	for(int i = 1; i <= n; i++){
		cin >> a[i];
		st.insert(a[i]-x);
		st.insert(a[i]);
	}

	vector<int> v(st.begin(),st.end());
	map<int,int> tr;
	for(auto& x : v){
		tr[x] = tr.size();
	}

	int ans = 0;

	for(int i = 1; i <= n; i++){
		int c;
		c = get(tr[a[i]]-1,2);
		ans = max(ans,c+1);
		upd(tr[a[i]],c+1,2);

		c = get(tr[a[i]]-1,1);
		ans = max(ans,c+1);
		upd(tr[a[i]],c+1,2);

		c = get(tr[a[i]-x]-1,1);
		ans = max(ans,c+1);
		upd(tr[a[i]-x],c+1,1);

		c = get(tr[a[i]-x]-1,0);
		ans = max(ans,c+1);
		upd(tr[a[i]-x],c+1,1);

		c = get(tr[a[i]]-1,0);
		ans = max(ans,c+1);
		upd(tr[a[i]],c+1,0);
	}
	cout << ans << "\n";

	return;
}

signed main(){
	ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
	int tests = 1;
	for(int test = 1; test <= tests; test++){
		solve();
	}

	return 0;
}
/**
8 10
7 3 5 12 2 7 3 4
      [    ]

1 2 2

**/
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...