답안 #530365

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
530365	2022-02-25T08:17:45 Z	abc864197532	Global Warming (CEOI18_glo)	C++17	100 / 100	145 ms	17044 KB

glo

#include <bits/stdc++.h>
using namespace std;
#define lli long long int
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define X first
#define Y second
#define pii pair<int,int>
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
void abc() {cout << endl;}
template <typename T, typename ...U> void abc(T i, U ...j) {
	cout << i << ' ', abc(j...);
}
template <typename T> void printv(T l, T r) {
	for (; l != r; ++l)
		cout << *l << " \n"[l + 1 == r];
}
#ifdef Doludu
#define test(x...) abc("[" + string(#x) + "]", x);
#define owo freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout)
#else
#define test(x...) void(0);
#define owo ios::sync_with_stdio(false), cin.tie(0)
#endif
const int N = 400087;
 
struct BIT {
	int val[N];
	void init() {
		fill(val, val + N, 0);
	}
	void add(int p, int v) {
		p += 5;
		for (int i = p; i < N; i += i & (-i))
			val[i] = max(val[i], v);
	}
	int query(int p) {
		p += 5;
		int ans = 0;
		for (int i = p; i > 0; i -= i & (-i))
			ans = max(ans, val[i]);
		return ans;
	}
} bit1, bit2;
 
 
vector <int> a;
int n;
 
int ask(int x) {
	vector <vector <int>> dp(n, vector <int> (2, 0));
	vector <int> v;
	for (int i : a)
		v.pb(i), v.pb(i + x);
	sort(all(v)), v.resize(unique(all(v)) - v.begin());
	bit1.init(), bit2.init();
	dp[0][0] = 1, dp[0][1] = 1;
	int ans = 1;
	for (int i = 0; i < n; ++i) {
		int p = lower_bound(all(v), a[i]) - v.begin();
		int q = lower_bound(all(v), a[i] + x) - v.begin();
		if (i) {
			dp[i][0] = bit1.query(p) + 1;
			dp[i][1] = max(bit1.query(q), bit2.query(q)) + 1;
		}
		bit1.add(p + 1, dp[i][0]);
		bit2.add(q + 1, dp[i][1]);
		ans = max({ans, dp[i][0], dp[i][1]});
	}
	return ans;
}
 
int main () {
	owo;
	int d;
	cin >> n >> d;
	a.resize(n);
	for (int i = 0; i < n; ++i)
		cin >> a[i];
	cout << ask(d) << endl;
}

Subtask #1

5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	3404 KB	Output is correct
2	Correct	2 ms	3404 KB	Output is correct
3	Correct	3 ms	3404 KB	Output is correct
4	Correct	2 ms	3404 KB	Output is correct
5	Correct	2 ms	3404 KB	Output is correct
6	Correct	2 ms	3404 KB	Output is correct
7	Correct	2 ms	3404 KB	Output is correct
8	Correct	2 ms	3404 KB	Output is correct
9	Correct	2 ms	3404 KB	Output is correct
10	Correct	2 ms	3404 KB	Output is correct
11	Correct	2 ms	3404 KB	Output is correct

Subtask #2

10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	3404 KB	Output is correct
2	Correct	2 ms	3404 KB	Output is correct
3	Correct	3 ms	3404 KB	Output is correct
4	Correct	2 ms	3404 KB	Output is correct
5	Correct	2 ms	3404 KB	Output is correct
6	Correct	2 ms	3404 KB	Output is correct
7	Correct	2 ms	3404 KB	Output is correct
8	Correct	2 ms	3404 KB	Output is correct
9	Correct	2 ms	3404 KB	Output is correct
10	Correct	2 ms	3404 KB	Output is correct
11	Correct	2 ms	3404 KB	Output is correct
12	Correct	2 ms	3404 KB	Output is correct
13	Correct	1 ms	3404 KB	Output is correct
14	Correct	2 ms	3404 KB	Output is correct
15	Correct	1 ms	3404 KB	Output is correct
16	Correct	1 ms	3404 KB	Output is correct
17	Correct	2 ms	3404 KB	Output is correct
18	Correct	2 ms	3404 KB	Output is correct

Subtask #3

13.0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	3404 KB	Output is correct
2	Correct	2 ms	3404 KB	Output is correct
3	Correct	3 ms	3404 KB	Output is correct
4	Correct	2 ms	3404 KB	Output is correct
5	Correct	2 ms	3404 KB	Output is correct
6	Correct	2 ms	3404 KB	Output is correct
7	Correct	2 ms	3404 KB	Output is correct
8	Correct	2 ms	3404 KB	Output is correct
9	Correct	2 ms	3404 KB	Output is correct
10	Correct	2 ms	3404 KB	Output is correct
11	Correct	2 ms	3404 KB	Output is correct
12	Correct	2 ms	3404 KB	Output is correct
13	Correct	1 ms	3404 KB	Output is correct
14	Correct	2 ms	3404 KB	Output is correct
15	Correct	1 ms	3404 KB	Output is correct
16	Correct	1 ms	3404 KB	Output is correct
17	Correct	2 ms	3404 KB	Output is correct
18	Correct	2 ms	3404 KB	Output is correct
19	Correct	3 ms	3404 KB	Output is correct
20	Correct	2 ms	3404 KB	Output is correct
21	Correct	2 ms	3404 KB	Output is correct
22	Correct	3 ms	3404 KB	Output is correct
23	Correct	2 ms	3404 KB	Output is correct
24	Correct	2 ms	3404 KB	Output is correct
25	Correct	2 ms	3404 KB	Output is correct
26	Correct	2 ms	3404 KB	Output is correct

Subtask #4

10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	120 ms	16840 KB	Output is correct
2	Correct	143 ms	16844 KB	Output is correct
3	Correct	128 ms	16836 KB	Output is correct
4	Correct	124 ms	16828 KB	Output is correct
5	Correct	62 ms	16820 KB	Output is correct

Subtask #5

20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	30 ms	6856 KB	Output is correct
2	Correct	39 ms	6840 KB	Output is correct
3	Correct	31 ms	6800 KB	Output is correct
4	Correct	18 ms	6856 KB	Output is correct
5	Correct	2 ms	3404 KB	Output is correct
6	Correct	18 ms	6800 KB	Output is correct
7	Correct	26 ms	6912 KB	Output is correct

Subtask #6

17.0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	76 ms	10172 KB	Output is correct
2	Correct	80 ms	10176 KB	Output is correct
3	Correct	145 ms	16832 KB	Output is correct
4	Correct	98 ms	16844 KB	Output is correct
5	Correct	45 ms	10188 KB	Output is correct
6	Correct	73 ms	16196 KB	Output is correct
7	Correct	75 ms	16204 KB	Output is correct
8	Correct	59 ms	10240 KB	Output is correct

Subtask #7

25.0 / 25.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	3404 KB	Output is correct
2	Correct	2 ms	3404 KB	Output is correct
3	Correct	3 ms	3404 KB	Output is correct
4	Correct	2 ms	3404 KB	Output is correct
5	Correct	2 ms	3404 KB	Output is correct
6	Correct	2 ms	3404 KB	Output is correct
7	Correct	2 ms	3404 KB	Output is correct
8	Correct	2 ms	3404 KB	Output is correct
9	Correct	2 ms	3404 KB	Output is correct
10	Correct	2 ms	3404 KB	Output is correct
11	Correct	2 ms	3404 KB	Output is correct
12	Correct	2 ms	3404 KB	Output is correct
13	Correct	1 ms	3404 KB	Output is correct
14	Correct	2 ms	3404 KB	Output is correct
15	Correct	1 ms	3404 KB	Output is correct
16	Correct	1 ms	3404 KB	Output is correct
17	Correct	2 ms	3404 KB	Output is correct
18	Correct	2 ms	3404 KB	Output is correct
19	Correct	3 ms	3404 KB	Output is correct
20	Correct	2 ms	3404 KB	Output is correct
21	Correct	2 ms	3404 KB	Output is correct
22	Correct	3 ms	3404 KB	Output is correct
23	Correct	2 ms	3404 KB	Output is correct
24	Correct	2 ms	3404 KB	Output is correct
25	Correct	2 ms	3404 KB	Output is correct
26	Correct	2 ms	3404 KB	Output is correct
27	Correct	120 ms	16840 KB	Output is correct
28	Correct	143 ms	16844 KB	Output is correct
29	Correct	128 ms	16836 KB	Output is correct
30	Correct	124 ms	16828 KB	Output is correct
31	Correct	62 ms	16820 KB	Output is correct
32	Correct	30 ms	6856 KB	Output is correct
33	Correct	39 ms	6840 KB	Output is correct
34	Correct	31 ms	6800 KB	Output is correct
35	Correct	18 ms	6856 KB	Output is correct
36	Correct	2 ms	3404 KB	Output is correct
37	Correct	18 ms	6800 KB	Output is correct
38	Correct	26 ms	6912 KB	Output is correct
39	Correct	76 ms	10172 KB	Output is correct
40	Correct	80 ms	10176 KB	Output is correct
41	Correct	145 ms	16832 KB	Output is correct
42	Correct	98 ms	16844 KB	Output is correct
43	Correct	45 ms	10188 KB	Output is correct
44	Correct	73 ms	16196 KB	Output is correct
45	Correct	75 ms	16204 KB	Output is correct
46	Correct	59 ms	10240 KB	Output is correct
47	Correct	67 ms	10168 KB	Output is correct
48	Correct	69 ms	10324 KB	Output is correct
49	Correct	136 ms	16960 KB	Output is correct
50	Correct	71 ms	16964 KB	Output is correct
51	Correct	63 ms	13560 KB	Output is correct
52	Correct	85 ms	16952 KB	Output is correct
53	Correct	69 ms	16944 KB	Output is correct
54	Correct	76 ms	17044 KB	Output is correct
55	Correct	128 ms	16928 KB	Output is correct