Submission #133797

#TimeUsernameProblemLanguageResultExecution timeMemory
133797mirbek01Global Warming (CEOI18_glo)C++11
100 / 100
403 ms13544 KiB
# include <bits/stdc++.h>

using namespace std;

const int N = 4e5 + 3;

int n, x, a[N], b[N], t[N * 4];
int f[N], s[N], ans;
vector <int> vec;

void upd(int pos, int val, int v = 1, int tl = 1, int tr = N - 1){
	if(tl == tr){
		t[v] = max(t[v], val);
	} else {
		int tm = (tl + tr) >> 1;
		if(pos <= tm)
			upd(pos, val, v << 1, tl, tm);
		else 
			upd(pos, val, v << 1 | 1, tm + 1, tr);
		t[v] = max(t[v << 1], t[v << 1 | 1]);
	}
}

int get(int l, int r, int v = 1, int tl = 1, int tr = N - 1){
	if(l > tr || tl > r) 
		return 0;
	if(l <= tl && tr <= r)
		return t[v];
	int tm = (tl + tr) >> 1;
	return max(get(l, r, v << 1, tl, tm), 
				get(l, r, v << 1 | 1, tm + 1, tr));
}

int main(){
	cin >> n >> x;
	
	for(int i = 1; i <= n; i ++){
		scanf("%d", a+i);
		b[i] = a[i] + x;
		vec.push_back(a[i]);
		vec.push_back(b[i]);
 	}
	
	sort(vec.begin(), vec.end());
	vec.resize( unique(vec.begin(), vec.end()) - vec.begin() );
	
	for(int i = 1; i <= n; i ++){
		a[i] = lower_bound(vec.begin(), vec.end(), a[i]) - vec.begin() + 1;
		b[i] = lower_bound(vec.begin(), vec.end(), b[i]) - vec.begin() + 1;
	}
	
	for(int i = n; i >= 1; i --){
		s[i] = get(b[i] + 1, N - 1) + 1;
		upd(b[i], s[i]);
		ans = max(ans, s[i]);
	}
		
	memset(t, 0, sizeof(t));

	for(int i = 1; i <= n; i ++){
		ans = max(ans, get(1, b[i] - 1) + s[i]);
		f[i] = get(1, a[i] - 1) + 1;
		upd(a[i], f[i]);
	}
	
	cout << ans << endl;
}

Compilation message (stderr)

glo.cpp: In function 'int main()':
glo.cpp:38:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", a+i);
   ~~~~~^~~~~~~~~~~
#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...