Submission #168661

#	Time	Username	Problem	Language	Result	Execution time	Memory
168661		nikatamliani	Global Warming (CEOI18_glo)	C++14	10 / 100	508 ms	7664 KiB

glo

# include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
int a[N], b[N], dp[N], tree[4 * N], n, d;
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));
}
int 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);
	}
}
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, mn = d, res = 0; 
	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 ++) res = max(res, dp[i]), b[i] = a[i];
	for(int i = r + 1; i <= n; i ++) b[i] += d;
	get_arr();
	get_ans();
	for(int i = 1; i <= n; i ++) res = max(res, dp[i]);
	cout << res << '\n';
}

Compilation message (stderr)

glo.cpp: In function 'int get_ans()':
glo.cpp:30:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^
glo.cpp: In function 'int main()':
glo.cpp:50:20: warning: unused variable 'mn' [-Wunused-variable]
  int r = 1, l = 1, mn = d, res = 0; 
                    ^~

• Subtask 1: 0 / 5
• Subtask 2: 0 / 10
• Subtask 3: 0 / 13
• Subtask 4: 10 / 10
• Subtask 5: 0 / 20
• Subtask 6: 0 / 17
• Subtask 7: 0 / 25