답안 #580495

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
580495	2022-06-21T10:47:13 Z	amunduzbaev	Global Warming (CEOI18_glo)	C++17	100 / 100	424 ms	16692 KB

#include "bits/stdc++.h"
using namespace std;
 
#define ar array
typedef int64_t ll;
#define int ll

const int N = 4e5 + 5;
int a[N];

struct ST{
	int tree[N << 2];
	void sett(int i, int v, int lx = 0, int rx = N, int x = 1){
		if(lx == rx) { tree[x] = v; return; }
		int m = (lx + rx) >> 1;
		if(i <= m) sett(i, v, lx, m, x << 1);
		else sett(i, v, m + 1, rx, x << 1 | 1);
		tree[x] = max(tree[x << 1], tree[x << 1 | 1]);
	}
	
	int get(int l, int r, int lx = 0, int rx = N, int x = 1){
		if(lx > r || rx < l) return 0;
		if(lx >= l && rx <= r) return tree[x];
		int m = (lx + rx) >> 1;
		return max(get(l, r, lx, m, x << 1), get(l, r, m + 1, rx, x << 1 | 1));
	}
}tree;
int pref[N], suff[N];

signed main(){
	ios::sync_with_stdio(0); cin.tie(0);
	
	int n, x; cin>>n>>x;
	vector<int> t;
	for(int i=0;i<n;i++){
		cin>>a[i];
		t.push_back(a[i]);
		t.push_back(a[i] - x);
	}
	
	sort(t.begin(), t.end());
	t.erase(unique(t.begin(), t.end()), t.end());
	for(int i=0;i<n;i++){
		int p = lower_bound(t.begin(), t.end(), a[i]) - t.begin() + 1;
		pref[i] = tree.get(0, p - 1) + 1;
		tree.sett(p, pref[i]);
	}
	for(int i=0;i<N;i++) tree.sett(i, 0);
	
	for(int i=n-1;~i;i--){
		int p = upper_bound(t.begin(), t.end(), a[i]) - t.begin() + 1;
		int tmp = tree.get(p, N - 1);
		int p2 = upper_bound(t.begin(), t.end(), a[i] - x) - t.begin() + 1;
		suff[i] = tree.get(p2, N - 1);
		tree.sett(p - 1, tmp + 1);
	}
	
	int res = 0;
	for(int i=0;i<n;i++){
		res = max(res, pref[i] + suff[i]);
	}
	//~ for(int i=0;i<n;i++){
		//~ cout<<pref[i]<<" ";
	//~ } cout<<"\n";
	//~ for(int i=0;i<n;i++){
		//~ cout<<suff[i]<<" ";
	//~ } cout<<"\n";
	
	cout<<res<<"\n";
}

Subtask #1
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	31 ms	8464 KB	Output is correct
2	Correct	32 ms	8424 KB	Output is correct
3	Correct	30 ms	8432 KB	Output is correct
4	Correct	28 ms	8472 KB	Output is correct
5	Correct	30 ms	8432 KB	Output is correct
6	Correct	30 ms	8496 KB	Output is correct
7	Correct	31 ms	8428 KB	Output is correct
8	Correct	34 ms	8480 KB	Output is correct
9	Correct	30 ms	8532 KB	Output is correct
10	Correct	29 ms	8488 KB	Output is correct
11	Correct	30 ms	8492 KB	Output is correct

Subtask #2
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	31 ms	8464 KB	Output is correct
2	Correct	32 ms	8424 KB	Output is correct
3	Correct	30 ms	8432 KB	Output is correct
4	Correct	28 ms	8472 KB	Output is correct
5	Correct	30 ms	8432 KB	Output is correct
6	Correct	30 ms	8496 KB	Output is correct
7	Correct	31 ms	8428 KB	Output is correct
8	Correct	34 ms	8480 KB	Output is correct
9	Correct	30 ms	8532 KB	Output is correct
10	Correct	29 ms	8488 KB	Output is correct
11	Correct	30 ms	8492 KB	Output is correct
12	Correct	28 ms	8532 KB	Output is correct
13	Correct	31 ms	8456 KB	Output is correct
14	Correct	31 ms	8532 KB	Output is correct
15	Correct	30 ms	8452 KB	Output is correct
16	Correct	31 ms	8560 KB	Output is correct
17	Correct	31 ms	8436 KB	Output is correct
18	Correct	34 ms	8496 KB	Output is correct

Subtask #3
13.0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Correct	31 ms	8464 KB	Output is correct
2	Correct	32 ms	8424 KB	Output is correct
3	Correct	30 ms	8432 KB	Output is correct
4	Correct	28 ms	8472 KB	Output is correct
5	Correct	30 ms	8432 KB	Output is correct
6	Correct	30 ms	8496 KB	Output is correct
7	Correct	31 ms	8428 KB	Output is correct
8	Correct	34 ms	8480 KB	Output is correct
9	Correct	30 ms	8532 KB	Output is correct
10	Correct	29 ms	8488 KB	Output is correct
11	Correct	30 ms	8492 KB	Output is correct
12	Correct	28 ms	8532 KB	Output is correct
13	Correct	31 ms	8456 KB	Output is correct
14	Correct	31 ms	8532 KB	Output is correct
15	Correct	30 ms	8452 KB	Output is correct
16	Correct	31 ms	8560 KB	Output is correct
17	Correct	31 ms	8436 KB	Output is correct
18	Correct	34 ms	8496 KB	Output is correct
19	Correct	32 ms	8564 KB	Output is correct
20	Correct	33 ms	8516 KB	Output is correct
21	Correct	31 ms	8560 KB	Output is correct
22	Correct	30 ms	8544 KB	Output is correct
23	Correct	29 ms	8604 KB	Output is correct
24	Correct	29 ms	8524 KB	Output is correct
25	Correct	29 ms	8504 KB	Output is correct
26	Correct	30 ms	8496 KB	Output is correct

Subtask #4
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	379 ms	16424 KB	Output is correct
2	Correct	360 ms	16436 KB	Output is correct
3	Correct	367 ms	16692 KB	Output is correct
4	Correct	342 ms	16424 KB	Output is correct
5	Correct	216 ms	16428 KB	Output is correct

Subtask #5
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	113 ms	10652 KB	Output is correct
2	Correct	104 ms	10520 KB	Output is correct
3	Correct	108 ms	10580 KB	Output is correct
4	Correct	74 ms	10688 KB	Output is correct
5	Correct	31 ms	8520 KB	Output is correct
6	Correct	69 ms	10560 KB	Output is correct
7	Correct	90 ms	10672 KB	Output is correct

Subtask #6
17.0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	208 ms	12580 KB	Output is correct
2	Correct	208 ms	12644 KB	Output is correct
3	Correct	423 ms	16448 KB	Output is correct
4	Correct	184 ms	16388 KB	Output is correct
5	Correct	124 ms	12536 KB	Output is correct
6	Correct	200 ms	16076 KB	Output is correct
7	Correct	191 ms	16028 KB	Output is correct
8	Correct	161 ms	12536 KB	Output is correct

Subtask #7
25.0 / 25.0

#	결과	실행 시간	메모리	Grader output
1	Correct	31 ms	8464 KB	Output is correct
2	Correct	32 ms	8424 KB	Output is correct
3	Correct	30 ms	8432 KB	Output is correct
4	Correct	28 ms	8472 KB	Output is correct
5	Correct	30 ms	8432 KB	Output is correct
6	Correct	30 ms	8496 KB	Output is correct
7	Correct	31 ms	8428 KB	Output is correct
8	Correct	34 ms	8480 KB	Output is correct
9	Correct	30 ms	8532 KB	Output is correct
10	Correct	29 ms	8488 KB	Output is correct
11	Correct	30 ms	8492 KB	Output is correct
12	Correct	28 ms	8532 KB	Output is correct
13	Correct	31 ms	8456 KB	Output is correct
14	Correct	31 ms	8532 KB	Output is correct
15	Correct	30 ms	8452 KB	Output is correct
16	Correct	31 ms	8560 KB	Output is correct
17	Correct	31 ms	8436 KB	Output is correct
18	Correct	34 ms	8496 KB	Output is correct
19	Correct	32 ms	8564 KB	Output is correct
20	Correct	33 ms	8516 KB	Output is correct
21	Correct	31 ms	8560 KB	Output is correct
22	Correct	30 ms	8544 KB	Output is correct
23	Correct	29 ms	8604 KB	Output is correct
24	Correct	29 ms	8524 KB	Output is correct
25	Correct	29 ms	8504 KB	Output is correct
26	Correct	30 ms	8496 KB	Output is correct
27	Correct	379 ms	16424 KB	Output is correct
28	Correct	360 ms	16436 KB	Output is correct
29	Correct	367 ms	16692 KB	Output is correct
30	Correct	342 ms	16424 KB	Output is correct
31	Correct	216 ms	16428 KB	Output is correct
32	Correct	113 ms	10652 KB	Output is correct
33	Correct	104 ms	10520 KB	Output is correct
34	Correct	108 ms	10580 KB	Output is correct
35	Correct	74 ms	10688 KB	Output is correct
36	Correct	31 ms	8520 KB	Output is correct
37	Correct	69 ms	10560 KB	Output is correct
38	Correct	90 ms	10672 KB	Output is correct
39	Correct	208 ms	12580 KB	Output is correct
40	Correct	208 ms	12644 KB	Output is correct
41	Correct	423 ms	16448 KB	Output is correct
42	Correct	184 ms	16388 KB	Output is correct
43	Correct	124 ms	12536 KB	Output is correct
44	Correct	200 ms	16076 KB	Output is correct
45	Correct	191 ms	16028 KB	Output is correct
46	Correct	161 ms	12536 KB	Output is correct
47	Correct	203 ms	12668 KB	Output is correct
48	Correct	189 ms	12560 KB	Output is correct
49	Correct	424 ms	16424 KB	Output is correct
50	Correct	186 ms	16424 KB	Output is correct
51	Correct	170 ms	14564 KB	Output is correct
52	Correct	244 ms	16440 KB	Output is correct
53	Correct	205 ms	16452 KB	Output is correct
54	Correct	212 ms	16612 KB	Output is correct
55	Correct	310 ms	16468 KB	Output is correct

답안 #580495

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