Submission #1038592

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1038592	2024-07-30T02:56:47 Z	vjudge1	Global Warming (CEOI18_glo)	C++14	48 / 100	175 ms	7088 KB

#include <bits/stdc++.h>

using namespace std;

int n, x;

int a[200005];

int o[200005];

int st[200005];

void upd(int i, int v) {
	
	int l = 1, r = n, id = 1;
	
	while (l < r) {
		int mid = (l + r) / 2;
		id *= 2;
		
		if (i <= mid) {
			r = mid;
		} else {
			l = mid + 1;
			id++;
		}
		
	}
	
	st[id] = max(st[id], v);
	
	while (id > 1) {
		
		id /= 2;
		st[id] = max(st[id * 2], st[id * 2 + 1]);
		
	}
}

int get(int i, int j, int id = 1, int l = 1, int r = n) {
	
	if (i > j) {
		return 0;
	}
	
	if (i <= l && r <= j) {
		return st[id];
	}
	
	int mid = (l + r) / 2;
	
	if (i <= mid && mid < j) {
		return max(get(i, j, id * 2, l, mid), get(i, j, id * 2 + 1, mid + 1, r));
	}
	
	if (mid < i) {
		return get(i, j, id * 2 + 1, mid + 1, r);
	}
	
	return get(i, j, id * 2, l, mid);
}

int lis_l[200005], lis_r[200005];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> n >> x;
	
	vector<int> val;
	
	for (int i = 1; i <= n; ++i) {
		
		cin >> a[i];
		
		val.emplace_back(a[i]);
	}
	
	sort(val.begin(), val.end());
	
	val.erase(unique(val.begin(), val.end()), val.end());
	
	for (int i = 1; i <= n; ++i) {
		
		o[i] = lower_bound(val.begin(), val.end(), a[i]) - val.begin() + 1;
		
	}
	
	memset(st, 0, sizeof st);
	
	for (int i = 1; i <= n; ++i) {
		
		lis_l[i] = get(1, o[i] - 1) + 1;
		
		upd(o[i], lis_l[i]);
	}
	
	memset(st, 0, sizeof st);
	
	for (int i = n; i >= 1; --i) {
		
		lis_r[i] = get(o[i] + 1, n) + 1;
		
		upd(o[i], lis_r[i]);
	}
	
	memset(st, 0, sizeof st);

	int ans = 0;	
	
	for (int i = 1; i <= n; ++i) {
		
		int j = upper_bound(val.begin(), val.end(), a[i] + x - 1) - val.begin();
		
		ans = max(ans, get(1, j) + lis_r[i]);
		
		upd(o[i], lis_l[i]);
	}
		
	cout << ans << '\n';
}

Subtask #1
5.0 / 5.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
13.0 / 13.0

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

Subtask #4
0 / 10.0

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

Subtask #5
20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	47 ms	2820 KB	Output is correct
2	Correct	48 ms	2772 KB	Output is correct
3	Correct	47 ms	2632 KB	Output is correct
4	Correct	23 ms	2524 KB	Output is correct
5	Correct	1 ms	1116 KB	Output is correct
6	Correct	26 ms	2500 KB	Output is correct
7	Correct	40 ms	2772 KB	Output is correct

Subtask #6
0 / 17.0

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

Subtask #7
0 / 25.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	1116 KB	Output is correct
2	Correct	1 ms	1116 KB	Output is correct
3	Correct	0 ms	1116 KB	Output is correct
4	Correct	0 ms	1116 KB	Output is correct
5	Correct	1 ms	1116 KB	Output is correct
6	Correct	1 ms	1116 KB	Output is correct
7	Correct	1 ms	1116 KB	Output is correct
8	Correct	1 ms	1116 KB	Output is correct
9	Correct	1 ms	1116 KB	Output is correct
10	Correct	1 ms	1116 KB	Output is correct
11	Correct	1 ms	1116 KB	Output is correct
12	Correct	1 ms	1116 KB	Output is correct
13	Correct	1 ms	1116 KB	Output is correct
14	Correct	1 ms	1116 KB	Output is correct
15	Correct	1 ms	1116 KB	Output is correct
16	Correct	0 ms	1116 KB	Output is correct
17	Correct	1 ms	1116 KB	Output is correct
18	Correct	1 ms	1116 KB	Output is correct
19	Correct	1 ms	1116 KB	Output is correct
20	Correct	1 ms	1116 KB	Output is correct
21	Correct	1 ms	1116 KB	Output is correct
22	Correct	1 ms	1116 KB	Output is correct
23	Correct	1 ms	1116 KB	Output is correct
24	Correct	1 ms	1116 KB	Output is correct
25	Correct	1 ms	1116 KB	Output is correct
26	Correct	1 ms	1116 KB	Output is correct
27	Incorrect	175 ms	7088 KB	Output isn't correct
28	Halted	0 ms	0 KB	-

Submission #1038592

Compilation message

Subtask #1 5.0 / 5.0

Subtask #2 10.0 / 10.0

Subtask #3 13.0 / 13.0

Subtask #4 0 / 10.0

Subtask #5 20.0 / 20.0

Subtask #6 0 / 17.0

Subtask #7 0 / 25.0

Subtask #1
5.0 / 5.0

Subtask #2
10.0 / 10.0

Subtask #3
13.0 / 13.0

Subtask #4
0 / 10.0

Subtask #5
20.0 / 20.0

Subtask #6
0 / 17.0

Subtask #7
0 / 25.0