oj.uz

Submission #168662

# Submission time Handle Problem Language Result Execution time Memory
168662 2019-12-14T20:48:37 Z nikatamliani Global Warming (CEOI18_glo) C++14
10 / 100
 503 ms 7600 KB 
# 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';
}

Subtask #1
0 / 5.0

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

Subtask #2
0 / 10.0

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

Subtask #3
0 / 13.0

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

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 503 ms 7464 KB Output is correct
2 Correct 501 ms 7524 KB Output is correct
3 Correct 499 ms 7600 KB Output is correct
4 Correct 502 ms 7524 KB Output is correct
5 Correct 356 ms 7524 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 2388 KB Output is correct
2 Correct 112 ms 2244 KB Output is correct
3 Correct 112 ms 2160 KB Output is correct
4 Incorrect 81 ms 2288 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

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

Subtask #7
0 / 25.0

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