제출 #168662

#제출 시각아이디문제언어결과실행 시간메모리
168662nikatamlianiGlobal Warming (CEOI18_glo)C++14
10 / 100
503 ms7600 KiB
# include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
int a[N], b[N], dp[N], tree[4 * N], n, d, res; 
vector < pair < int, int > > v;
void update(int l, int r, int x, int v, int p){
	if(l > x || r < x) return;
	if(l == r){
		tree[p] = v;
	}else{
		int m = (l + r) >> 1;
		update(l, m, x, v, p << 1);
		update(m + 1, r, x, v, p << 1 | 1);
		tree[p] = max(tree[p << 1], tree[p << 1 | 1]);
	}
}
int query(int l, int r, int L, int R, int p){
	if(l > R || L > r) return 0;
	if(L <= l && R >= r) return tree[p];
	int m = (l + r) >> 1;
	return max(query(l, m, L, R, p << 1), query(m + 1, r, L, R, p << 1 | 1));
}
void get_ans(){
	for(int i = 1; i <= n; i ++) dp[i] = 0; 
	for(int i = 1; i <= 4 * n; i ++) tree[i] = 0;
	for(int i = 1; i <= n; i ++){
		dp[i] = query(1, n, 1, b[i] - 1, 1) + 1;
		update(1, n, b[i], dp[i], 1);
		res = max(res, dp[i]);
	}
}
void get_arr(){
	for(int i = 1; i <= n; i ++) v.push_back({b[i], i});  
	sort(v.begin(), v.end());
	int cnt = 0; 
	for(int i = 0; i < n; i ++){
		if(!i || v[i].first != v[i - 1].first)cnt ++;
		b[v[i].second] = cnt;
	}
	v.clear();
}
int main(){
	cin >> n >> d; 
	for(int i = 1; i <= n; i ++){
		cin >> a[i];
		a[i] += 1e9;
		b[i] = a[i];
	} 
	get_arr();
	get_ans();
	int r = 1, l = 1; 
	for(int i = 1; i <= n; i ++)
		if(dp[r] < dp[i]) r = l = i;
	for(int j = l; j > 0; j --)
		if(dp[j] == dp[l] - 1 && a[j] < a[l]) l = j; 
	for(int i = 1; i <= n; i ++) b[i] = a[i];
	for(int i = 1; i <= l - 1; i ++) b[i] -= d; 
	get_arr();
	get_ans();
	for(int i = 1; i <= n; i ++) b[i] = a[i];
	for(int i = r + 1; i <= n; i ++) b[i] += d;
	get_arr();
	get_ans();
	cout << res << '\n';
} 
#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...