#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair<int, int> pii;
#define SZ(x) (int) x.size()
#define F first
#define S second
#define lc id << 1
#define rc lc | 1
const int N = 3e5 + 10, MOD = 1e9 + 7;
int n, D, dp[N], A[N], seg[N << 2]; vector<int> cp, vec[N]; set<int> st1, st2;
void upd(int p, int x, int id = 1, int l = 1, int r = n + 1) {
if (r - l < 2) {
seg[id] = x;
return;
}
int md = (l + r) >> 1;
if (p < md) upd(p, x, lc, l, md);
else upd(p, x, rc, md, r);
seg[id] = max(seg[lc], seg[rc]);
}
int get(int ql, int qr, int id = 1, int l = 1, int r = n + 1) {
if (qr <= l || r <= ql || ql >= qr) return 0;
if (ql <= l && r <= qr) return seg[id];
int md = (l + r) >> 1;
return max(get(ql, qr, lc, l, md), get(ql, qr, rc, md, r));
}
void add(int pos) {
if (SZ(st1)) {
if (*st1.begin() < pos) {
auto it = st1.upper_bound(pos); it--;
if (pos - *it > D) st2.insert(pos);
it++;
if (it != st1.end()) {
st2.erase(*it);
if (*it - pos > D) st2.insert(*it);
}
st1.insert(pos);
} else {
auto it = st1.upper_bound(pos);
st1.insert(pos);
if (*it - pos > D) st2.insert(*it);
}
} else {
st1.insert(pos);
}
}
void remove(int pos) {
if (*st1.begin() < pos) {
st2.erase(pos);
auto it = st1.upper_bound(pos);
if (it != st1.end()) {
st2.erase(*it);
int x = *it;
it--; assert(*it == pos);
it--;
if (x - *it > D) st2.insert(x);
}
st1.erase(pos);
} else {
auto it = st1.upper_bound(pos);
if (it != st1.end()) st2.erase(*it);
st1.erase(pos);
}
}
void print() {
printf("start\n");
for (int x : st2)
printf("%d ", x);
printf("\nend\n");
}
int main() {
scanf("%d%d", &n, &D);
for (int i = 1; i <= n; i++)
scanf("%d", &A[i]), cp.push_back(A[i]);
sort(begin(cp), end(cp));
cp.resize(unique(begin(cp), end(cp)) - begin(cp));
for (int i = 1; i <= n; i++) {
int id = lower_bound(begin(cp), end(cp), A[i]) - begin(cp);
vec[id].push_back(i);
}
for (int i = 0; i < SZ(cp); i++) {
for (int &j : vec[i]) {
//dp[i] = get(l, j) + 1;
add(j);
if (st2.empty() || *st2.begin() > j) dp[j] = get(1, j) + 1;
else {
auto it = st2.upper_bound(j); it--;
dp[j] = get(*it, j) + 1;
}
remove(j);
}
for (int &j : vec[i])
upd(j, dp[j]), add(j);
//print();
}
int ret = dp[n];
st1.clear();
st2.clear();
for (int i = 0; i < SZ(cp); i++) {
for (int &j : vec[i])
add(j);
if (cp[i] >= A[n]) {
for (int &j : vec[i]) {
auto it = st2.upper_bound(j);
if (it == st2.end()) ret = max(ret, dp[j]);
}
}
}
printf("%d\n", ret);
return 0;
}
Compilation message
Main.cpp: In function 'int main()':
Main.cpp:83:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
83 | scanf("%d%d", &n, &D);
| ~~~~~^~~~~~~~~~~~~~~~
Main.cpp:85:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
85 | scanf("%d", &A[i]), cp.push_back(A[i]);
| ~~~~~^~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
6 ms |
7244 KB |
Output is correct |
2 |
Correct |
5 ms |
7244 KB |
Output is correct |
3 |
Correct |
5 ms |
7244 KB |
Output is correct |
4 |
Correct |
5 ms |
7284 KB |
Output is correct |
5 |
Correct |
5 ms |
7244 KB |
Output is correct |
6 |
Correct |
5 ms |
7244 KB |
Output is correct |
7 |
Correct |
5 ms |
7244 KB |
Output is correct |
8 |
Correct |
5 ms |
7360 KB |
Output is correct |
9 |
Correct |
5 ms |
7244 KB |
Output is correct |
10 |
Correct |
5 ms |
7352 KB |
Output is correct |
11 |
Correct |
5 ms |
7244 KB |
Output is correct |
12 |
Correct |
5 ms |
7244 KB |
Output is correct |
13 |
Correct |
5 ms |
7292 KB |
Output is correct |
14 |
Correct |
5 ms |
7368 KB |
Output is correct |
15 |
Correct |
6 ms |
7360 KB |
Output is correct |
16 |
Correct |
5 ms |
7244 KB |
Output is correct |
17 |
Correct |
6 ms |
7244 KB |
Output is correct |
18 |
Correct |
5 ms |
7244 KB |
Output is correct |
19 |
Correct |
6 ms |
7244 KB |
Output is correct |
20 |
Correct |
7 ms |
7244 KB |
Output is correct |
21 |
Correct |
5 ms |
7244 KB |
Output is correct |
22 |
Correct |
6 ms |
7252 KB |
Output is correct |
23 |
Correct |
5 ms |
7244 KB |
Output is correct |
24 |
Correct |
6 ms |
7244 KB |
Output is correct |
25 |
Correct |
6 ms |
7244 KB |
Output is correct |
26 |
Correct |
6 ms |
7244 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
6 ms |
7244 KB |
Output is correct |
2 |
Correct |
5 ms |
7244 KB |
Output is correct |
3 |
Correct |
5 ms |
7244 KB |
Output is correct |
4 |
Correct |
5 ms |
7284 KB |
Output is correct |
5 |
Correct |
5 ms |
7244 KB |
Output is correct |
6 |
Correct |
5 ms |
7244 KB |
Output is correct |
7 |
Correct |
5 ms |
7244 KB |
Output is correct |
8 |
Correct |
5 ms |
7360 KB |
Output is correct |
9 |
Correct |
5 ms |
7244 KB |
Output is correct |
10 |
Correct |
5 ms |
7352 KB |
Output is correct |
11 |
Correct |
5 ms |
7244 KB |
Output is correct |
12 |
Correct |
5 ms |
7244 KB |
Output is correct |
13 |
Correct |
5 ms |
7292 KB |
Output is correct |
14 |
Correct |
5 ms |
7368 KB |
Output is correct |
15 |
Correct |
6 ms |
7360 KB |
Output is correct |
16 |
Correct |
5 ms |
7244 KB |
Output is correct |
17 |
Correct |
6 ms |
7244 KB |
Output is correct |
18 |
Correct |
5 ms |
7244 KB |
Output is correct |
19 |
Correct |
6 ms |
7244 KB |
Output is correct |
20 |
Correct |
7 ms |
7244 KB |
Output is correct |
21 |
Correct |
5 ms |
7244 KB |
Output is correct |
22 |
Correct |
6 ms |
7252 KB |
Output is correct |
23 |
Correct |
5 ms |
7244 KB |
Output is correct |
24 |
Correct |
6 ms |
7244 KB |
Output is correct |
25 |
Correct |
6 ms |
7244 KB |
Output is correct |
26 |
Correct |
6 ms |
7244 KB |
Output is correct |
27 |
Correct |
7 ms |
7312 KB |
Output is correct |
28 |
Correct |
6 ms |
7400 KB |
Output is correct |
29 |
Correct |
6 ms |
7372 KB |
Output is correct |
30 |
Correct |
6 ms |
7380 KB |
Output is correct |
31 |
Correct |
6 ms |
7372 KB |
Output is correct |
32 |
Correct |
6 ms |
7372 KB |
Output is correct |
33 |
Correct |
6 ms |
7372 KB |
Output is correct |
34 |
Correct |
7 ms |
7372 KB |
Output is correct |
35 |
Correct |
7 ms |
7372 KB |
Output is correct |
36 |
Correct |
6 ms |
7384 KB |
Output is correct |
37 |
Correct |
6 ms |
7404 KB |
Output is correct |
38 |
Correct |
7 ms |
7372 KB |
Output is correct |
39 |
Correct |
6 ms |
7372 KB |
Output is correct |
40 |
Correct |
7 ms |
7392 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
6 ms |
7244 KB |
Output is correct |
2 |
Correct |
5 ms |
7244 KB |
Output is correct |
3 |
Correct |
5 ms |
7244 KB |
Output is correct |
4 |
Correct |
5 ms |
7284 KB |
Output is correct |
5 |
Correct |
5 ms |
7244 KB |
Output is correct |
6 |
Correct |
5 ms |
7244 KB |
Output is correct |
7 |
Correct |
5 ms |
7244 KB |
Output is correct |
8 |
Correct |
5 ms |
7360 KB |
Output is correct |
9 |
Correct |
5 ms |
7244 KB |
Output is correct |
10 |
Correct |
5 ms |
7352 KB |
Output is correct |
11 |
Correct |
5 ms |
7244 KB |
Output is correct |
12 |
Correct |
5 ms |
7244 KB |
Output is correct |
13 |
Correct |
5 ms |
7292 KB |
Output is correct |
14 |
Correct |
5 ms |
7368 KB |
Output is correct |
15 |
Correct |
6 ms |
7360 KB |
Output is correct |
16 |
Correct |
5 ms |
7244 KB |
Output is correct |
17 |
Correct |
6 ms |
7244 KB |
Output is correct |
18 |
Correct |
5 ms |
7244 KB |
Output is correct |
19 |
Correct |
6 ms |
7244 KB |
Output is correct |
20 |
Correct |
7 ms |
7244 KB |
Output is correct |
21 |
Correct |
5 ms |
7244 KB |
Output is correct |
22 |
Correct |
6 ms |
7252 KB |
Output is correct |
23 |
Correct |
5 ms |
7244 KB |
Output is correct |
24 |
Correct |
6 ms |
7244 KB |
Output is correct |
25 |
Correct |
6 ms |
7244 KB |
Output is correct |
26 |
Correct |
6 ms |
7244 KB |
Output is correct |
27 |
Correct |
7 ms |
7312 KB |
Output is correct |
28 |
Correct |
6 ms |
7400 KB |
Output is correct |
29 |
Correct |
6 ms |
7372 KB |
Output is correct |
30 |
Correct |
6 ms |
7380 KB |
Output is correct |
31 |
Correct |
6 ms |
7372 KB |
Output is correct |
32 |
Correct |
6 ms |
7372 KB |
Output is correct |
33 |
Correct |
6 ms |
7372 KB |
Output is correct |
34 |
Correct |
7 ms |
7372 KB |
Output is correct |
35 |
Correct |
7 ms |
7372 KB |
Output is correct |
36 |
Correct |
6 ms |
7384 KB |
Output is correct |
37 |
Correct |
6 ms |
7404 KB |
Output is correct |
38 |
Correct |
7 ms |
7372 KB |
Output is correct |
39 |
Correct |
6 ms |
7372 KB |
Output is correct |
40 |
Correct |
7 ms |
7392 KB |
Output is correct |
41 |
Correct |
31 ms |
7868 KB |
Output is correct |
42 |
Correct |
27 ms |
8032 KB |
Output is correct |
43 |
Correct |
16 ms |
7756 KB |
Output is correct |
44 |
Correct |
17 ms |
7884 KB |
Output is correct |
45 |
Correct |
17 ms |
7892 KB |
Output is correct |
46 |
Correct |
19 ms |
8060 KB |
Output is correct |
47 |
Correct |
19 ms |
7964 KB |
Output is correct |
48 |
Correct |
21 ms |
8036 KB |
Output is correct |
49 |
Correct |
21 ms |
8040 KB |
Output is correct |
50 |
Correct |
20 ms |
8020 KB |
Output is correct |
51 |
Correct |
21 ms |
7944 KB |
Output is correct |
52 |
Correct |
27 ms |
7960 KB |
Output is correct |
53 |
Correct |
16 ms |
7980 KB |
Output is correct |
54 |
Correct |
17 ms |
7968 KB |
Output is correct |
55 |
Correct |
18 ms |
8016 KB |
Output is correct |
56 |
Correct |
20 ms |
8044 KB |
Output is correct |
57 |
Correct |
18 ms |
7944 KB |
Output is correct |
58 |
Correct |
15 ms |
8036 KB |
Output is correct |
59 |
Correct |
14 ms |
8012 KB |
Output is correct |
60 |
Correct |
22 ms |
7948 KB |
Output is correct |
61 |
Correct |
22 ms |
8024 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
488 ms |
30228 KB |
Output is correct |
2 |
Correct |
759 ms |
30440 KB |
Output is correct |
3 |
Correct |
1965 ms |
30568 KB |
Output is correct |
4 |
Correct |
2423 ms |
36956 KB |
Output is correct |
5 |
Correct |
1722 ms |
38392 KB |
Output is correct |
6 |
Correct |
2082 ms |
38404 KB |
Output is correct |
7 |
Correct |
674 ms |
38280 KB |
Output is correct |
8 |
Correct |
579 ms |
38272 KB |
Output is correct |
9 |
Correct |
516 ms |
38476 KB |
Output is correct |
10 |
Correct |
552 ms |
38392 KB |
Output is correct |
11 |
Correct |
1216 ms |
38440 KB |
Output is correct |
12 |
Correct |
1499 ms |
38444 KB |
Output is correct |
13 |
Correct |
1421 ms |
38396 KB |
Output is correct |
14 |
Correct |
1954 ms |
38448 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
497 ms |
30208 KB |
Output is correct |
2 |
Correct |
902 ms |
30444 KB |
Output is correct |
3 |
Correct |
1269 ms |
30968 KB |
Output is correct |
4 |
Correct |
1525 ms |
38452 KB |
Output is correct |
5 |
Correct |
1109 ms |
38444 KB |
Output is correct |
6 |
Correct |
1381 ms |
38444 KB |
Output is correct |
7 |
Correct |
712 ms |
38508 KB |
Output is correct |
8 |
Correct |
627 ms |
38396 KB |
Output is correct |
9 |
Correct |
579 ms |
38272 KB |
Output is correct |
10 |
Correct |
832 ms |
38368 KB |
Output is correct |
11 |
Correct |
1459 ms |
38424 KB |
Output is correct |
12 |
Correct |
1173 ms |
38408 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
6 ms |
7244 KB |
Output is correct |
2 |
Correct |
5 ms |
7244 KB |
Output is correct |
3 |
Correct |
5 ms |
7244 KB |
Output is correct |
4 |
Correct |
5 ms |
7284 KB |
Output is correct |
5 |
Correct |
5 ms |
7244 KB |
Output is correct |
6 |
Correct |
5 ms |
7244 KB |
Output is correct |
7 |
Correct |
5 ms |
7244 KB |
Output is correct |
8 |
Correct |
5 ms |
7360 KB |
Output is correct |
9 |
Correct |
5 ms |
7244 KB |
Output is correct |
10 |
Correct |
5 ms |
7352 KB |
Output is correct |
11 |
Correct |
5 ms |
7244 KB |
Output is correct |
12 |
Correct |
5 ms |
7244 KB |
Output is correct |
13 |
Correct |
5 ms |
7292 KB |
Output is correct |
14 |
Correct |
5 ms |
7368 KB |
Output is correct |
15 |
Correct |
6 ms |
7360 KB |
Output is correct |
16 |
Correct |
5 ms |
7244 KB |
Output is correct |
17 |
Correct |
6 ms |
7244 KB |
Output is correct |
18 |
Correct |
5 ms |
7244 KB |
Output is correct |
19 |
Correct |
6 ms |
7244 KB |
Output is correct |
20 |
Correct |
7 ms |
7244 KB |
Output is correct |
21 |
Correct |
5 ms |
7244 KB |
Output is correct |
22 |
Correct |
6 ms |
7252 KB |
Output is correct |
23 |
Correct |
5 ms |
7244 KB |
Output is correct |
24 |
Correct |
6 ms |
7244 KB |
Output is correct |
25 |
Correct |
6 ms |
7244 KB |
Output is correct |
26 |
Correct |
6 ms |
7244 KB |
Output is correct |
27 |
Correct |
7 ms |
7312 KB |
Output is correct |
28 |
Correct |
6 ms |
7400 KB |
Output is correct |
29 |
Correct |
6 ms |
7372 KB |
Output is correct |
30 |
Correct |
6 ms |
7380 KB |
Output is correct |
31 |
Correct |
6 ms |
7372 KB |
Output is correct |
32 |
Correct |
6 ms |
7372 KB |
Output is correct |
33 |
Correct |
6 ms |
7372 KB |
Output is correct |
34 |
Correct |
7 ms |
7372 KB |
Output is correct |
35 |
Correct |
7 ms |
7372 KB |
Output is correct |
36 |
Correct |
6 ms |
7384 KB |
Output is correct |
37 |
Correct |
6 ms |
7404 KB |
Output is correct |
38 |
Correct |
7 ms |
7372 KB |
Output is correct |
39 |
Correct |
6 ms |
7372 KB |
Output is correct |
40 |
Correct |
7 ms |
7392 KB |
Output is correct |
41 |
Correct |
31 ms |
7868 KB |
Output is correct |
42 |
Correct |
27 ms |
8032 KB |
Output is correct |
43 |
Correct |
16 ms |
7756 KB |
Output is correct |
44 |
Correct |
17 ms |
7884 KB |
Output is correct |
45 |
Correct |
17 ms |
7892 KB |
Output is correct |
46 |
Correct |
19 ms |
8060 KB |
Output is correct |
47 |
Correct |
19 ms |
7964 KB |
Output is correct |
48 |
Correct |
21 ms |
8036 KB |
Output is correct |
49 |
Correct |
21 ms |
8040 KB |
Output is correct |
50 |
Correct |
20 ms |
8020 KB |
Output is correct |
51 |
Correct |
21 ms |
7944 KB |
Output is correct |
52 |
Correct |
27 ms |
7960 KB |
Output is correct |
53 |
Correct |
16 ms |
7980 KB |
Output is correct |
54 |
Correct |
17 ms |
7968 KB |
Output is correct |
55 |
Correct |
18 ms |
8016 KB |
Output is correct |
56 |
Correct |
20 ms |
8044 KB |
Output is correct |
57 |
Correct |
18 ms |
7944 KB |
Output is correct |
58 |
Correct |
15 ms |
8036 KB |
Output is correct |
59 |
Correct |
14 ms |
8012 KB |
Output is correct |
60 |
Correct |
22 ms |
7948 KB |
Output is correct |
61 |
Correct |
22 ms |
8024 KB |
Output is correct |
62 |
Correct |
488 ms |
30228 KB |
Output is correct |
63 |
Correct |
759 ms |
30440 KB |
Output is correct |
64 |
Correct |
1965 ms |
30568 KB |
Output is correct |
65 |
Correct |
2423 ms |
36956 KB |
Output is correct |
66 |
Correct |
1722 ms |
38392 KB |
Output is correct |
67 |
Correct |
2082 ms |
38404 KB |
Output is correct |
68 |
Correct |
674 ms |
38280 KB |
Output is correct |
69 |
Correct |
579 ms |
38272 KB |
Output is correct |
70 |
Correct |
516 ms |
38476 KB |
Output is correct |
71 |
Correct |
552 ms |
38392 KB |
Output is correct |
72 |
Correct |
1216 ms |
38440 KB |
Output is correct |
73 |
Correct |
1499 ms |
38444 KB |
Output is correct |
74 |
Correct |
1421 ms |
38396 KB |
Output is correct |
75 |
Correct |
1954 ms |
38448 KB |
Output is correct |
76 |
Correct |
497 ms |
30208 KB |
Output is correct |
77 |
Correct |
902 ms |
30444 KB |
Output is correct |
78 |
Correct |
1269 ms |
30968 KB |
Output is correct |
79 |
Correct |
1525 ms |
38452 KB |
Output is correct |
80 |
Correct |
1109 ms |
38444 KB |
Output is correct |
81 |
Correct |
1381 ms |
38444 KB |
Output is correct |
82 |
Correct |
712 ms |
38508 KB |
Output is correct |
83 |
Correct |
627 ms |
38396 KB |
Output is correct |
84 |
Correct |
579 ms |
38272 KB |
Output is correct |
85 |
Correct |
832 ms |
38368 KB |
Output is correct |
86 |
Correct |
1459 ms |
38424 KB |
Output is correct |
87 |
Correct |
1173 ms |
38408 KB |
Output is correct |
88 |
Correct |
1770 ms |
30576 KB |
Output is correct |
89 |
Correct |
1858 ms |
38212 KB |
Output is correct |
90 |
Correct |
1719 ms |
31764 KB |
Output is correct |
91 |
Correct |
1526 ms |
38428 KB |
Output is correct |
92 |
Correct |
673 ms |
30728 KB |
Output is correct |
93 |
Correct |
1256 ms |
30736 KB |
Output is correct |
94 |
Correct |
1342 ms |
35680 KB |
Output is correct |
95 |
Correct |
1664 ms |
38440 KB |
Output is correct |
96 |
Correct |
1488 ms |
38440 KB |
Output is correct |
97 |
Correct |
1326 ms |
38372 KB |
Output is correct |
98 |
Correct |
1391 ms |
38444 KB |
Output is correct |
99 |
Correct |
1305 ms |
38444 KB |
Output is correct |
100 |
Correct |
1274 ms |
38444 KB |
Output is correct |
101 |
Correct |
514 ms |
38444 KB |
Output is correct |
102 |
Correct |
550 ms |
38448 KB |
Output is correct |
103 |
Correct |
696 ms |
38440 KB |
Output is correct |
104 |
Correct |
676 ms |
38444 KB |
Output is correct |
105 |
Correct |
824 ms |
38444 KB |
Output is correct |
106 |
Correct |
712 ms |
38424 KB |
Output is correct |
107 |
Correct |
809 ms |
38320 KB |
Output is correct |
108 |
Correct |
1183 ms |
38536 KB |
Output is correct |
109 |
Correct |
1081 ms |
38468 KB |
Output is correct |
110 |
Correct |
1420 ms |
38404 KB |
Output is correct |
111 |
Correct |
1391 ms |
38440 KB |
Output is correct |
112 |
Correct |
900 ms |
38424 KB |
Output is correct |
113 |
Correct |
1268 ms |
38320 KB |
Output is correct |
114 |
Correct |
1367 ms |
38452 KB |
Output is correct |
115 |
Correct |
710 ms |
38448 KB |
Output is correct |
116 |
Correct |
621 ms |
38420 KB |
Output is correct |
117 |
Correct |
852 ms |
38424 KB |
Output is correct |
118 |
Correct |
838 ms |
38428 KB |
Output is correct |
119 |
Correct |
813 ms |
38412 KB |
Output is correct |
120 |
Correct |
844 ms |
38408 KB |
Output is correct |