Submission #948559

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
948559	2024-03-18T07:52:58 Z	dio_2	Global Warming (CEOI18_glo)	C++17	100 / 100	701 ms	26488 KB

#include<bits/stdc++.h>
using namespace std;

struct MaxSegree{
	MaxSegree () {}
	MaxSegree (int N){
		build(N);
	}
	int base;
	const int neutral = -(int)1e9;
	vector<int> maxy;
	
	void build(int N){
		base = 1;
		while(base <= N) base *= 2;
		maxy.assign(2 * base, neutral);
	}
	
	void pull(int node){
		maxy[node] = max(maxy[2 * node], maxy[2 * node + 1]);
	}
	
	void update(int node, int lx, int rx, int pos, int val){
		if(lx == rx){
			assert(lx == pos);
			maxy[node] = val;
			return ;
		}
		int mid = (lx + rx) / 2;
		if(pos <= mid){
			update(2 * node, lx, mid, pos, val);
		} else {
			update(2 * node + 1, mid + 1, rx, pos, val);
		}
		pull(node);
	}
	
	int Max(int node, int lx, int rx, int l, int r){
		if(lx > r || rx < l) return neutral;
		if(l <= lx && rx <= r) return maxy[node];
		int mid = (lx + rx) / 2;
		return max(Max(2 * node, lx, mid, l, r), Max(2 * node + 1, mid + 1, rx, l, r));
	}
	
	void update(int pos, int val){
		update(1, 1, base, pos, val);
	}
	
	int Max(int l, int r){
		return Max(1, 1, base, l, r);
	}
};

int main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	
	int n, x;
	cin >> n >> x;
	
	vector<int> t(n);
	set<int> s;
	map<int, int> comp;
	for(int &y : t){
		cin >> y;
		s.insert(y);
	}
	
	// compress for RMQ.
	int cnt = 1;
	for(int y : s){
		comp[y] = cnt++;
	}
	
	MaxSegree LIS(n), LDS(n);
	vector<int> dp(n, 1), dp2(n, 1);
	for(int i = 0;i < n;i++){
		if(comp[t[i]] - 1 >= 1){
			dp[i] = max(dp[i], LIS.Max(1, comp[t[i]] - 1) + 1);
		}
		LIS.update(comp[t[i]], dp[i]);
	}
	
	int answer = *max_element(dp.begin(), dp.end());

	vector<int> greaterCompressed(n, -1);
	for(int i = 0;i < n;i++){
		int nval = t[i] - x;
		auto it = s.upper_bound(nval);
		if(it != s.end()){
			greaterCompressed[i] = comp[*it];
		}
	}
	
	for(int i = n - 1;i >= 0;i--){
		if(comp[t[i]] + 1 <= n){
			dp2[i] = max(dp2[i], LDS.Max(comp[t[i]] + 1, n) + 1);
		}
		LDS.update(comp[t[i]], dp2[i]);
		answer = max(answer, dp2[i]);
		if(i - 1 >= 0){
			if(greaterCompressed[i - 1] == -1) continue;
			answer = max(answer, dp[i - 1] + LDS.Max(greaterCompressed[i - 1], n));
		}
	}
	

	cout << answer << '\n';
	
	return 0;
}

Subtask #1
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	1 ms	348 KB	Output is correct
3	Correct	1 ms	348 KB	Output is correct
4	Correct	1 ms	600 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	0 ms	348 KB	Output is correct

Subtask #2
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	1 ms	348 KB	Output is correct
3	Correct	1 ms	348 KB	Output is correct
4	Correct	1 ms	600 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	0 ms	348 KB	Output is correct
12	Correct	1 ms	344 KB	Output is correct
13	Correct	0 ms	348 KB	Output is correct
14	Correct	0 ms	348 KB	Output is correct
15	Correct	0 ms	348 KB	Output is correct
16	Correct	0 ms	348 KB	Output is correct
17	Correct	0 ms	348 KB	Output is correct
18	Correct	0 ms	348 KB	Output is correct

Subtask #3
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	1 ms	348 KB	Output is correct
3	Correct	1 ms	348 KB	Output is correct
4	Correct	1 ms	600 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	0 ms	348 KB	Output is correct
12	Correct	1 ms	344 KB	Output is correct
13	Correct	0 ms	348 KB	Output is correct
14	Correct	0 ms	348 KB	Output is correct
15	Correct	0 ms	348 KB	Output is correct
16	Correct	0 ms	348 KB	Output is correct
17	Correct	0 ms	348 KB	Output is correct
18	Correct	0 ms	348 KB	Output is correct
19	Correct	2 ms	344 KB	Output is correct
20	Correct	2 ms	600 KB	Output is correct
21	Correct	2 ms	344 KB	Output is correct
22	Correct	2 ms	600 KB	Output is correct
23	Correct	1 ms	528 KB	Output is correct
24	Correct	1 ms	344 KB	Output is correct
25	Correct	1 ms	348 KB	Output is correct
26	Correct	2 ms	344 KB	Output is correct

Subtask #4
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	694 ms	26464 KB	Output is correct
2	Correct	644 ms	26360 KB	Output is correct
3	Correct	686 ms	26476 KB	Output is correct
4	Correct	701 ms	26484 KB	Output is correct
5	Correct	255 ms	17088 KB	Output is correct

Subtask #5
20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	112 ms	6780 KB	Output is correct
2	Correct	113 ms	6804 KB	Output is correct
3	Correct	119 ms	6964 KB	Output is correct
4	Correct	46 ms	4436 KB	Output is correct
5	Correct	1 ms	348 KB	Output is correct
6	Correct	61 ms	4436 KB	Output is correct
7	Correct	91 ms	6932 KB	Output is correct

Subtask #6
17.0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	202 ms	13408 KB	Output is correct
2	Correct	210 ms	13468 KB	Output is correct
3	Correct	503 ms	26480 KB	Output is correct
4	Correct	219 ms	17088 KB	Output is correct
5	Correct	146 ms	13336 KB	Output is correct
6	Correct	283 ms	25172 KB	Output is correct
7	Correct	282 ms	25380 KB	Output is correct
8	Correct	181 ms	13332 KB	Output is correct

Subtask #7
25.0 / 25.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	1 ms	348 KB	Output is correct
3	Correct	1 ms	348 KB	Output is correct
4	Correct	1 ms	600 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	0 ms	348 KB	Output is correct
12	Correct	1 ms	344 KB	Output is correct
13	Correct	0 ms	348 KB	Output is correct
14	Correct	0 ms	348 KB	Output is correct
15	Correct	0 ms	348 KB	Output is correct
16	Correct	0 ms	348 KB	Output is correct
17	Correct	0 ms	348 KB	Output is correct
18	Correct	0 ms	348 KB	Output is correct
19	Correct	2 ms	344 KB	Output is correct
20	Correct	2 ms	600 KB	Output is correct
21	Correct	2 ms	344 KB	Output is correct
22	Correct	2 ms	600 KB	Output is correct
23	Correct	1 ms	528 KB	Output is correct
24	Correct	1 ms	344 KB	Output is correct
25	Correct	1 ms	348 KB	Output is correct
26	Correct	2 ms	344 KB	Output is correct
27	Correct	694 ms	26464 KB	Output is correct
28	Correct	644 ms	26360 KB	Output is correct
29	Correct	686 ms	26476 KB	Output is correct
30	Correct	701 ms	26484 KB	Output is correct
31	Correct	255 ms	17088 KB	Output is correct
32	Correct	112 ms	6780 KB	Output is correct
33	Correct	113 ms	6804 KB	Output is correct
34	Correct	119 ms	6964 KB	Output is correct
35	Correct	46 ms	4436 KB	Output is correct
36	Correct	1 ms	348 KB	Output is correct
37	Correct	61 ms	4436 KB	Output is correct
38	Correct	91 ms	6932 KB	Output is correct
39	Correct	202 ms	13408 KB	Output is correct
40	Correct	210 ms	13468 KB	Output is correct
41	Correct	503 ms	26480 KB	Output is correct
42	Correct	219 ms	17088 KB	Output is correct
43	Correct	146 ms	13336 KB	Output is correct
44	Correct	283 ms	25172 KB	Output is correct
45	Correct	282 ms	25380 KB	Output is correct
46	Correct	181 ms	13332 KB	Output is correct
47	Correct	265 ms	13336 KB	Output is correct
48	Correct	275 ms	13464 KB	Output is correct
49	Correct	684 ms	26480 KB	Output is correct
50	Correct	235 ms	17084 KB	Output is correct
51	Correct	206 ms	16304 KB	Output is correct
52	Correct	357 ms	26488 KB	Output is correct
53	Correct	295 ms	26488 KB	Output is correct
54	Correct	318 ms	26488 KB	Output is correct
55	Correct	471 ms	26480 KB	Output is correct

Submission #948559

Compilation message

Subtask #1 5.0 / 5.0

Subtask #2 10.0 / 10.0

Subtask #3 13.0 / 13.0

Subtask #4 10.0 / 10.0

Subtask #5 20.0 / 20.0

Subtask #6 17.0 / 17.0

Subtask #7 25.0 / 25.0

Subtask #1
5.0 / 5.0

Subtask #2
10.0 / 10.0

Subtask #3
13.0 / 13.0

Subtask #4
10.0 / 10.0

Subtask #5
20.0 / 20.0

Subtask #6
17.0 / 17.0

Subtask #7
25.0 / 25.0