답안 #737663

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
737663	2023-05-07T13:47:27 Z	bane	Global Warming (CEOI18_glo)	C++17	100 / 100	578 ms	118276 KB

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

const int maxN = (int)4e6;
int x,n,much = 0;

unordered_map<int,int>compress;

class SegmentTree{
	public:
	int tree[maxN * 3];
	inline void upd(int pos, int val, int l = 1, int r = much, int k = 1){
		if (l == r){
			tree[k] = max(tree[k], val);
			return;
		}
		int md = (l + r) >> 1;
		if (pos <= md)upd(pos,val,l,md,k*2);
		else upd(pos,val,md+1,r,k*2+1);
		tree[k] = max(tree[k * 2], tree[k * 2 + 1]);
	}
	
	inline int query(int a, int b, int l = 1, int r = much , int k = 1){
		if (l >= a && r <= b)return tree[k];
		if (l > b || r < a || a > b || a > much || b > much)return 0;
		return max(query(a,b,l,(l+r)/2,k*2), query(a,b,(l+r)/2+1,r,k*2+1));
	}
};

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin >> n >> x;
	vector<int>a(n), b;
	for (int i = 0; i < n; i++){
		cin >> a[i];
		b.push_back(a[i]);
		b.push_back(a[i] - x);
	}
	sort(b.begin(), b.end());
	for (int i = 0; i < (int)b.size(); i++){
		if (!i || b[i] != b[i - 1])compress[b[i]] = ++much;
	}
	int dpLeft[n], dpRight[n], maxima = 0;
	SegmentTree L, R;
	for (int i = n - 1; i>=0; i--){
		dpRight[i] = R.query(compress[a[i]-x] + 1, much) + 1;
		R.upd(compress[a[i]], R.query(compress[a[i]] + 1, much) + 1);
	}
	for (int i = 0 ; i < n; i++){
		dpLeft[i] = L.query(1, compress[a[i]] - 1) + 1;
		L.upd(compress[a[i]], dpLeft[i]);
	}
	for (int i = 0 ; i < n; i++){
		maxima = max(maxima, dpLeft[i] + dpRight[i] - 1);
	}
	cout<<maxima<<'\n';
	return 0;
}

Subtask #1
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	37 ms	94172 KB	Output is correct
2	Correct	36 ms	94144 KB	Output is correct
3	Correct	37 ms	94156 KB	Output is correct
4	Correct	38 ms	94196 KB	Output is correct
5	Correct	37 ms	94192 KB	Output is correct
6	Correct	40 ms	94208 KB	Output is correct
7	Correct	37 ms	94228 KB	Output is correct
8	Correct	37 ms	94228 KB	Output is correct
9	Correct	37 ms	94236 KB	Output is correct
10	Correct	38 ms	94176 KB	Output is correct
11	Correct	37 ms	94140 KB	Output is correct

Subtask #2
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	37 ms	94172 KB	Output is correct
2	Correct	36 ms	94144 KB	Output is correct
3	Correct	37 ms	94156 KB	Output is correct
4	Correct	38 ms	94196 KB	Output is correct
5	Correct	37 ms	94192 KB	Output is correct
6	Correct	40 ms	94208 KB	Output is correct
7	Correct	37 ms	94228 KB	Output is correct
8	Correct	37 ms	94228 KB	Output is correct
9	Correct	37 ms	94236 KB	Output is correct
10	Correct	38 ms	94176 KB	Output is correct
11	Correct	37 ms	94140 KB	Output is correct
12	Correct	36 ms	94148 KB	Output is correct
13	Correct	36 ms	94224 KB	Output is correct
14	Correct	36 ms	94164 KB	Output is correct
15	Correct	37 ms	94160 KB	Output is correct
16	Correct	38 ms	94192 KB	Output is correct
17	Correct	38 ms	94164 KB	Output is correct
18	Correct	36 ms	94220 KB	Output is correct

Subtask #3
13.0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Correct	37 ms	94172 KB	Output is correct
2	Correct	36 ms	94144 KB	Output is correct
3	Correct	37 ms	94156 KB	Output is correct
4	Correct	38 ms	94196 KB	Output is correct
5	Correct	37 ms	94192 KB	Output is correct
6	Correct	40 ms	94208 KB	Output is correct
7	Correct	37 ms	94228 KB	Output is correct
8	Correct	37 ms	94228 KB	Output is correct
9	Correct	37 ms	94236 KB	Output is correct
10	Correct	38 ms	94176 KB	Output is correct
11	Correct	37 ms	94140 KB	Output is correct
12	Correct	36 ms	94148 KB	Output is correct
13	Correct	36 ms	94224 KB	Output is correct
14	Correct	36 ms	94164 KB	Output is correct
15	Correct	37 ms	94160 KB	Output is correct
16	Correct	38 ms	94192 KB	Output is correct
17	Correct	38 ms	94164 KB	Output is correct
18	Correct	36 ms	94220 KB	Output is correct
19	Correct	42 ms	94284 KB	Output is correct
20	Correct	37 ms	94252 KB	Output is correct
21	Correct	38 ms	94292 KB	Output is correct
22	Correct	38 ms	94276 KB	Output is correct
23	Correct	38 ms	94292 KB	Output is correct
24	Correct	37 ms	94232 KB	Output is correct
25	Correct	38 ms	94232 KB	Output is correct
26	Correct	36 ms	94204 KB	Output is correct

Subtask #4
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	360 ms	109120 KB	Output is correct
2	Correct	368 ms	109104 KB	Output is correct
3	Correct	353 ms	109100 KB	Output is correct
4	Correct	394 ms	109112 KB	Output is correct
5	Correct	194 ms	104004 KB	Output is correct

Subtask #5
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	129 ms	100112 KB	Output is correct
2	Correct	117 ms	100076 KB	Output is correct
3	Correct	117 ms	100188 KB	Output is correct
4	Correct	76 ms	97732 KB	Output is correct
5	Correct	38 ms	94156 KB	Output is correct
6	Correct	70 ms	97740 KB	Output is correct
7	Correct	101 ms	98976 KB	Output is correct

Subtask #6
17.0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	273 ms	106156 KB	Output is correct
2	Correct	242 ms	106088 KB	Output is correct
3	Correct	578 ms	118180 KB	Output is correct
4	Correct	232 ms	108284 KB	Output is correct
5	Correct	124 ms	105732 KB	Output is correct
6	Correct	200 ms	116940 KB	Output is correct
7	Correct	205 ms	117688 KB	Output is correct
8	Correct	194 ms	106080 KB	Output is correct

Subtask #7
25.0 / 25.0

#	결과	실행 시간	메모리	Grader output
1	Correct	37 ms	94172 KB	Output is correct
2	Correct	36 ms	94144 KB	Output is correct
3	Correct	37 ms	94156 KB	Output is correct
4	Correct	38 ms	94196 KB	Output is correct
5	Correct	37 ms	94192 KB	Output is correct
6	Correct	40 ms	94208 KB	Output is correct
7	Correct	37 ms	94228 KB	Output is correct
8	Correct	37 ms	94228 KB	Output is correct
9	Correct	37 ms	94236 KB	Output is correct
10	Correct	38 ms	94176 KB	Output is correct
11	Correct	37 ms	94140 KB	Output is correct
12	Correct	36 ms	94148 KB	Output is correct
13	Correct	36 ms	94224 KB	Output is correct
14	Correct	36 ms	94164 KB	Output is correct
15	Correct	37 ms	94160 KB	Output is correct
16	Correct	38 ms	94192 KB	Output is correct
17	Correct	38 ms	94164 KB	Output is correct
18	Correct	36 ms	94220 KB	Output is correct
19	Correct	42 ms	94284 KB	Output is correct
20	Correct	37 ms	94252 KB	Output is correct
21	Correct	38 ms	94292 KB	Output is correct
22	Correct	38 ms	94276 KB	Output is correct
23	Correct	38 ms	94292 KB	Output is correct
24	Correct	37 ms	94232 KB	Output is correct
25	Correct	38 ms	94232 KB	Output is correct
26	Correct	36 ms	94204 KB	Output is correct
27	Correct	360 ms	109120 KB	Output is correct
28	Correct	368 ms	109104 KB	Output is correct
29	Correct	353 ms	109100 KB	Output is correct
30	Correct	394 ms	109112 KB	Output is correct
31	Correct	194 ms	104004 KB	Output is correct
32	Correct	129 ms	100112 KB	Output is correct
33	Correct	117 ms	100076 KB	Output is correct
34	Correct	117 ms	100188 KB	Output is correct
35	Correct	76 ms	97732 KB	Output is correct
36	Correct	38 ms	94156 KB	Output is correct
37	Correct	70 ms	97740 KB	Output is correct
38	Correct	101 ms	98976 KB	Output is correct
39	Correct	273 ms	106156 KB	Output is correct
40	Correct	242 ms	106088 KB	Output is correct
41	Correct	578 ms	118180 KB	Output is correct
42	Correct	232 ms	108284 KB	Output is correct
43	Correct	124 ms	105732 KB	Output is correct
44	Correct	200 ms	116940 KB	Output is correct
45	Correct	205 ms	117688 KB	Output is correct
46	Correct	194 ms	106080 KB	Output is correct
47	Correct	238 ms	106176 KB	Output is correct
48	Correct	300 ms	106152 KB	Output is correct
49	Correct	558 ms	118112 KB	Output is correct
50	Correct	239 ms	108408 KB	Output is correct
51	Correct	147 ms	104132 KB	Output is correct
52	Correct	211 ms	108484 KB	Output is correct
53	Correct	212 ms	117432 KB	Output is correct
54	Correct	226 ms	118276 KB	Output is correct
55	Correct	408 ms	113332 KB	Output is correct

답안 #737663

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