Submission #948539

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
948539	2024-03-18T07:45:40 Z	dio_2	Global Warming (CEOI18_glo)	C++17	28 / 100	2000 ms	27376 KB

glo

#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 = 0;
	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){
			int prev_val = t[i - 1] - x;
			// find first strictly <
			for(int j = i;j < n;j++){
				if(prev_val < t[j]){
					answer = max(answer, dp[i - 1] + dp2[j]);
				}
			}
		}
	}
	

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

Subtask #1

5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	600 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	1 ms	344 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	1 ms	348 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	1 ms	344 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	600 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	1 ms	344 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	1 ms	348 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	1 ms	344 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	0 ms	348 KB	Output is correct
12	Correct	0 ms	348 KB	Output is correct
13	Correct	1 ms	348 KB	Output is correct
14	Correct	1 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	1 ms	348 KB	Output is correct

Subtask #3

13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	600 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	1 ms	344 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	1 ms	348 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	1 ms	344 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	0 ms	348 KB	Output is correct
12	Correct	0 ms	348 KB	Output is correct
13	Correct	1 ms	348 KB	Output is correct
14	Correct	1 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	1 ms	348 KB	Output is correct
19	Correct	3 ms	348 KB	Output is correct
20	Correct	2 ms	348 KB	Output is correct
21	Correct	2 ms	348 KB	Output is correct
22	Correct	2 ms	460 KB	Output is correct
23	Correct	1 ms	348 KB	Output is correct
24	Correct	2 ms	348 KB	Output is correct
25	Correct	2 ms	348 KB	Output is correct
26	Correct	2 ms	348 KB	Output is correct

Subtask #4

0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	2083 ms	27376 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Subtask #5

0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	2029 ms	6996 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Subtask #6

0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	2057 ms	13844 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Subtask #7

0 / 25.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	600 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	1 ms	344 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	1 ms	348 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	1 ms	344 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	0 ms	348 KB	Output is correct
12	Correct	0 ms	348 KB	Output is correct
13	Correct	1 ms	348 KB	Output is correct
14	Correct	1 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	1 ms	348 KB	Output is correct
19	Correct	3 ms	348 KB	Output is correct
20	Correct	2 ms	348 KB	Output is correct
21	Correct	2 ms	348 KB	Output is correct
22	Correct	2 ms	460 KB	Output is correct
23	Correct	1 ms	348 KB	Output is correct
24	Correct	2 ms	348 KB	Output is correct
25	Correct	2 ms	348 KB	Output is correct
26	Correct	2 ms	348 KB	Output is correct
27	Execution timed out	2083 ms	27376 KB	Time limit exceeded
28	Halted	0 ms	0 KB	-