#include <bits/stdc++.h>
#define int long long
using namespace std;
namespace std {
template <typename T> ostream &operator<<(ostream &out, const vector<T> &vec) {
out << "[";
for (int i = 0; i < (int)vec.size(); ++i) {
out << vec[i];
if (i + 1 < (int)vec.size())
out << ", ";
}
return out << "]";
}
} // namespace std
void dbg_out() { cout << endl; }
template <typename Head, typename... Tail> void dbg_out(Head H, Tail... T) {
cout << ' ' << H;
dbg_out(T...);
}
#ifdef DEBUG
#define dbg(...) cout << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
#else
#define dbg(...)
#endif
struct UnionFind {
vector<int> id;
vector<int> smallest;
UnionFind() {}
UnionFind(int N) {
id.assign(N, -1);
smallest.resize(N);
iota(smallest.begin(), smallest.end(), 0);
}
int find(int u) {
if (id[u] < 0)
return u;
return id[u] = find(id[u]);
}
bool merge(int u, int v) {
u = find(u), v = find(v);
if (u == v)
return false;
if (id[u] > id[v])
swap(u, v);
id[u] += id[v];
id[v] = u;
smallest[u] = min(smallest[u], smallest[v]);
return true;
}
};
const int INF = 1e18;
signed main(void) {
ios_base::sync_with_stdio(false);
cin.tie(0);
int N, D;
cin >> N >> D;
vector<int> A(N);
for (int &x : A)
cin >> x;
vector<int> order(N);
iota(order.begin(), order.end(), 0);
sort(order.begin(), order.end(), [&](int i, int j) { return A[i] < A[j]; });
set<int> starts;
UnionFind dsu(N);
vector<int> firstBad(N);
int curAdded = N - 1;
for (int i = N - 1; i >= 0; --i) {
int x = A[order[i]];
while (x < A[order[curAdded]]) {
int j = order[curAdded];
if (j and A[j - 1] > x)
dsu.merge(j - 1, j);
if (j + 1 < N and A[j + 1] > x)
dsu.merge(j, j + 1);
int id = dsu.find(j);
if (-dsu.id[id] >= D)
starts.insert(dsu.smallest[id]);
curAdded--;
}
auto it = starts.lower_bound(order[i]);
firstBad[order[i]] = it == starts.end() ? N : min(N, *it + D);
}
dbg(firstBad);
int start = 1;
while (start < N)
start *= 2;
vector<int> seg(2 * start);
auto setPos = [&](int pos, int x) {
pos += start;
seg[pos] = x;
while (pos > 1) {
pos /= 2;
seg[pos] = max(seg[2 * pos], seg[2 * pos + 1]);
}
};
auto query = [&](int deb, int fin) {
int ret = 0;
deb += start, fin += start;
while (deb < fin) {
if (deb % 2)
ret = max(ret, seg[deb++]);
if (fin % 2)
ret = max(ret, seg[--fin]);
deb /= 2;
fin /= 2;
}
return ret;
};
vector<int> pos(N);
for (int i = 0; i < N; ++i)
pos[order[i]] = i;
vector<int> sortedA = A;
sort(sortedA.begin(), sortedA.end());
vector<vector<int>> toDelete(N);
for (int i = 0; i < N; ++i)
if (firstBad[i] < N)
toDelete[firstBad[i]].push_back(i);
for (int i = 0; i < N; ++i) {
for (int j : toDelete[i])
setPos(pos[j], 0);
auto fin =
lower_bound(sortedA.begin(), sortedA.end(), A[i]) - sortedA.begin();
int LIS = query(0, fin) + 1;
dbg(i, fin, LIS);
setPos(pos[i], LIS);
}
cout << query(0, N) << endl;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
316 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
1 ms |
212 KB |
Output is correct |
5 |
Correct |
1 ms |
212 KB |
Output is correct |
6 |
Correct |
1 ms |
324 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
1 ms |
324 KB |
Output is correct |
9 |
Correct |
1 ms |
212 KB |
Output is correct |
10 |
Correct |
1 ms |
212 KB |
Output is correct |
11 |
Correct |
0 ms |
212 KB |
Output is correct |
12 |
Correct |
0 ms |
212 KB |
Output is correct |
13 |
Correct |
1 ms |
212 KB |
Output is correct |
14 |
Correct |
0 ms |
212 KB |
Output is correct |
15 |
Correct |
1 ms |
212 KB |
Output is correct |
16 |
Correct |
1 ms |
212 KB |
Output is correct |
17 |
Correct |
1 ms |
212 KB |
Output is correct |
18 |
Correct |
1 ms |
212 KB |
Output is correct |
19 |
Correct |
0 ms |
212 KB |
Output is correct |
20 |
Correct |
1 ms |
320 KB |
Output is correct |
21 |
Correct |
0 ms |
212 KB |
Output is correct |
22 |
Correct |
1 ms |
212 KB |
Output is correct |
23 |
Correct |
0 ms |
212 KB |
Output is correct |
24 |
Correct |
1 ms |
316 KB |
Output is correct |
25 |
Correct |
0 ms |
212 KB |
Output is correct |
26 |
Correct |
0 ms |
320 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
316 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
1 ms |
212 KB |
Output is correct |
5 |
Correct |
1 ms |
212 KB |
Output is correct |
6 |
Correct |
1 ms |
324 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
1 ms |
324 KB |
Output is correct |
9 |
Correct |
1 ms |
212 KB |
Output is correct |
10 |
Correct |
1 ms |
212 KB |
Output is correct |
11 |
Correct |
0 ms |
212 KB |
Output is correct |
12 |
Correct |
0 ms |
212 KB |
Output is correct |
13 |
Correct |
1 ms |
212 KB |
Output is correct |
14 |
Correct |
0 ms |
212 KB |
Output is correct |
15 |
Correct |
1 ms |
212 KB |
Output is correct |
16 |
Correct |
1 ms |
212 KB |
Output is correct |
17 |
Correct |
1 ms |
212 KB |
Output is correct |
18 |
Correct |
1 ms |
212 KB |
Output is correct |
19 |
Correct |
0 ms |
212 KB |
Output is correct |
20 |
Correct |
1 ms |
320 KB |
Output is correct |
21 |
Correct |
0 ms |
212 KB |
Output is correct |
22 |
Correct |
1 ms |
212 KB |
Output is correct |
23 |
Correct |
0 ms |
212 KB |
Output is correct |
24 |
Correct |
1 ms |
316 KB |
Output is correct |
25 |
Correct |
0 ms |
212 KB |
Output is correct |
26 |
Correct |
0 ms |
320 KB |
Output is correct |
27 |
Correct |
1 ms |
316 KB |
Output is correct |
28 |
Correct |
1 ms |
340 KB |
Output is correct |
29 |
Correct |
1 ms |
340 KB |
Output is correct |
30 |
Correct |
1 ms |
340 KB |
Output is correct |
31 |
Correct |
1 ms |
340 KB |
Output is correct |
32 |
Correct |
1 ms |
340 KB |
Output is correct |
33 |
Correct |
1 ms |
320 KB |
Output is correct |
34 |
Correct |
1 ms |
320 KB |
Output is correct |
35 |
Correct |
1 ms |
340 KB |
Output is correct |
36 |
Correct |
1 ms |
316 KB |
Output is correct |
37 |
Correct |
1 ms |
340 KB |
Output is correct |
38 |
Correct |
1 ms |
340 KB |
Output is correct |
39 |
Correct |
1 ms |
340 KB |
Output is correct |
40 |
Correct |
1 ms |
324 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
316 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
1 ms |
212 KB |
Output is correct |
5 |
Correct |
1 ms |
212 KB |
Output is correct |
6 |
Correct |
1 ms |
324 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
1 ms |
324 KB |
Output is correct |
9 |
Correct |
1 ms |
212 KB |
Output is correct |
10 |
Correct |
1 ms |
212 KB |
Output is correct |
11 |
Correct |
0 ms |
212 KB |
Output is correct |
12 |
Correct |
0 ms |
212 KB |
Output is correct |
13 |
Correct |
1 ms |
212 KB |
Output is correct |
14 |
Correct |
0 ms |
212 KB |
Output is correct |
15 |
Correct |
1 ms |
212 KB |
Output is correct |
16 |
Correct |
1 ms |
212 KB |
Output is correct |
17 |
Correct |
1 ms |
212 KB |
Output is correct |
18 |
Correct |
1 ms |
212 KB |
Output is correct |
19 |
Correct |
0 ms |
212 KB |
Output is correct |
20 |
Correct |
1 ms |
320 KB |
Output is correct |
21 |
Correct |
0 ms |
212 KB |
Output is correct |
22 |
Correct |
1 ms |
212 KB |
Output is correct |
23 |
Correct |
0 ms |
212 KB |
Output is correct |
24 |
Correct |
1 ms |
316 KB |
Output is correct |
25 |
Correct |
0 ms |
212 KB |
Output is correct |
26 |
Correct |
0 ms |
320 KB |
Output is correct |
27 |
Correct |
1 ms |
316 KB |
Output is correct |
28 |
Correct |
1 ms |
340 KB |
Output is correct |
29 |
Correct |
1 ms |
340 KB |
Output is correct |
30 |
Correct |
1 ms |
340 KB |
Output is correct |
31 |
Correct |
1 ms |
340 KB |
Output is correct |
32 |
Correct |
1 ms |
340 KB |
Output is correct |
33 |
Correct |
1 ms |
320 KB |
Output is correct |
34 |
Correct |
1 ms |
320 KB |
Output is correct |
35 |
Correct |
1 ms |
340 KB |
Output is correct |
36 |
Correct |
1 ms |
316 KB |
Output is correct |
37 |
Correct |
1 ms |
340 KB |
Output is correct |
38 |
Correct |
1 ms |
340 KB |
Output is correct |
39 |
Correct |
1 ms |
340 KB |
Output is correct |
40 |
Correct |
1 ms |
324 KB |
Output is correct |
41 |
Correct |
6 ms |
1344 KB |
Output is correct |
42 |
Correct |
5 ms |
1236 KB |
Output is correct |
43 |
Correct |
3 ms |
1032 KB |
Output is correct |
44 |
Correct |
4 ms |
980 KB |
Output is correct |
45 |
Correct |
4 ms |
972 KB |
Output is correct |
46 |
Correct |
4 ms |
972 KB |
Output is correct |
47 |
Correct |
5 ms |
1236 KB |
Output is correct |
48 |
Correct |
5 ms |
1104 KB |
Output is correct |
49 |
Correct |
5 ms |
1096 KB |
Output is correct |
50 |
Correct |
4 ms |
1108 KB |
Output is correct |
51 |
Correct |
5 ms |
1364 KB |
Output is correct |
52 |
Correct |
6 ms |
1236 KB |
Output is correct |
53 |
Correct |
4 ms |
1364 KB |
Output is correct |
54 |
Correct |
3 ms |
1096 KB |
Output is correct |
55 |
Correct |
4 ms |
1108 KB |
Output is correct |
56 |
Correct |
3 ms |
968 KB |
Output is correct |
57 |
Correct |
4 ms |
980 KB |
Output is correct |
58 |
Correct |
4 ms |
1096 KB |
Output is correct |
59 |
Correct |
2 ms |
980 KB |
Output is correct |
60 |
Correct |
3 ms |
968 KB |
Output is correct |
61 |
Correct |
3 ms |
980 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
73 ms |
34912 KB |
Output is correct |
2 |
Correct |
208 ms |
45908 KB |
Output is correct |
3 |
Correct |
365 ms |
47444 KB |
Output is correct |
4 |
Correct |
412 ms |
47540 KB |
Output is correct |
5 |
Correct |
339 ms |
50272 KB |
Output is correct |
6 |
Correct |
392 ms |
47600 KB |
Output is correct |
7 |
Correct |
213 ms |
58068 KB |
Output is correct |
8 |
Correct |
97 ms |
34856 KB |
Output is correct |
9 |
Correct |
187 ms |
52000 KB |
Output is correct |
10 |
Correct |
161 ms |
43732 KB |
Output is correct |
11 |
Correct |
268 ms |
47556 KB |
Output is correct |
12 |
Correct |
288 ms |
47668 KB |
Output is correct |
13 |
Correct |
339 ms |
58384 KB |
Output is correct |
14 |
Correct |
251 ms |
37896 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
80 ms |
35216 KB |
Output is correct |
2 |
Correct |
149 ms |
34756 KB |
Output is correct |
3 |
Correct |
193 ms |
34896 KB |
Output is correct |
4 |
Correct |
209 ms |
35020 KB |
Output is correct |
5 |
Correct |
191 ms |
34792 KB |
Output is correct |
6 |
Correct |
204 ms |
34916 KB |
Output is correct |
7 |
Correct |
100 ms |
34848 KB |
Output is correct |
8 |
Correct |
100 ms |
35020 KB |
Output is correct |
9 |
Correct |
115 ms |
34812 KB |
Output is correct |
10 |
Correct |
178 ms |
34748 KB |
Output is correct |
11 |
Correct |
189 ms |
34924 KB |
Output is correct |
12 |
Correct |
160 ms |
34796 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
316 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
1 ms |
212 KB |
Output is correct |
5 |
Correct |
1 ms |
212 KB |
Output is correct |
6 |
Correct |
1 ms |
324 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
1 ms |
324 KB |
Output is correct |
9 |
Correct |
1 ms |
212 KB |
Output is correct |
10 |
Correct |
1 ms |
212 KB |
Output is correct |
11 |
Correct |
0 ms |
212 KB |
Output is correct |
12 |
Correct |
0 ms |
212 KB |
Output is correct |
13 |
Correct |
1 ms |
212 KB |
Output is correct |
14 |
Correct |
0 ms |
212 KB |
Output is correct |
15 |
Correct |
1 ms |
212 KB |
Output is correct |
16 |
Correct |
1 ms |
212 KB |
Output is correct |
17 |
Correct |
1 ms |
212 KB |
Output is correct |
18 |
Correct |
1 ms |
212 KB |
Output is correct |
19 |
Correct |
0 ms |
212 KB |
Output is correct |
20 |
Correct |
1 ms |
320 KB |
Output is correct |
21 |
Correct |
0 ms |
212 KB |
Output is correct |
22 |
Correct |
1 ms |
212 KB |
Output is correct |
23 |
Correct |
0 ms |
212 KB |
Output is correct |
24 |
Correct |
1 ms |
316 KB |
Output is correct |
25 |
Correct |
0 ms |
212 KB |
Output is correct |
26 |
Correct |
0 ms |
320 KB |
Output is correct |
27 |
Correct |
1 ms |
316 KB |
Output is correct |
28 |
Correct |
1 ms |
340 KB |
Output is correct |
29 |
Correct |
1 ms |
340 KB |
Output is correct |
30 |
Correct |
1 ms |
340 KB |
Output is correct |
31 |
Correct |
1 ms |
340 KB |
Output is correct |
32 |
Correct |
1 ms |
340 KB |
Output is correct |
33 |
Correct |
1 ms |
320 KB |
Output is correct |
34 |
Correct |
1 ms |
320 KB |
Output is correct |
35 |
Correct |
1 ms |
340 KB |
Output is correct |
36 |
Correct |
1 ms |
316 KB |
Output is correct |
37 |
Correct |
1 ms |
340 KB |
Output is correct |
38 |
Correct |
1 ms |
340 KB |
Output is correct |
39 |
Correct |
1 ms |
340 KB |
Output is correct |
40 |
Correct |
1 ms |
324 KB |
Output is correct |
41 |
Correct |
6 ms |
1344 KB |
Output is correct |
42 |
Correct |
5 ms |
1236 KB |
Output is correct |
43 |
Correct |
3 ms |
1032 KB |
Output is correct |
44 |
Correct |
4 ms |
980 KB |
Output is correct |
45 |
Correct |
4 ms |
972 KB |
Output is correct |
46 |
Correct |
4 ms |
972 KB |
Output is correct |
47 |
Correct |
5 ms |
1236 KB |
Output is correct |
48 |
Correct |
5 ms |
1104 KB |
Output is correct |
49 |
Correct |
5 ms |
1096 KB |
Output is correct |
50 |
Correct |
4 ms |
1108 KB |
Output is correct |
51 |
Correct |
5 ms |
1364 KB |
Output is correct |
52 |
Correct |
6 ms |
1236 KB |
Output is correct |
53 |
Correct |
4 ms |
1364 KB |
Output is correct |
54 |
Correct |
3 ms |
1096 KB |
Output is correct |
55 |
Correct |
4 ms |
1108 KB |
Output is correct |
56 |
Correct |
3 ms |
968 KB |
Output is correct |
57 |
Correct |
4 ms |
980 KB |
Output is correct |
58 |
Correct |
4 ms |
1096 KB |
Output is correct |
59 |
Correct |
2 ms |
980 KB |
Output is correct |
60 |
Correct |
3 ms |
968 KB |
Output is correct |
61 |
Correct |
3 ms |
980 KB |
Output is correct |
62 |
Correct |
73 ms |
34912 KB |
Output is correct |
63 |
Correct |
208 ms |
45908 KB |
Output is correct |
64 |
Correct |
365 ms |
47444 KB |
Output is correct |
65 |
Correct |
412 ms |
47540 KB |
Output is correct |
66 |
Correct |
339 ms |
50272 KB |
Output is correct |
67 |
Correct |
392 ms |
47600 KB |
Output is correct |
68 |
Correct |
213 ms |
58068 KB |
Output is correct |
69 |
Correct |
97 ms |
34856 KB |
Output is correct |
70 |
Correct |
187 ms |
52000 KB |
Output is correct |
71 |
Correct |
161 ms |
43732 KB |
Output is correct |
72 |
Correct |
268 ms |
47556 KB |
Output is correct |
73 |
Correct |
288 ms |
47668 KB |
Output is correct |
74 |
Correct |
339 ms |
58384 KB |
Output is correct |
75 |
Correct |
251 ms |
37896 KB |
Output is correct |
76 |
Correct |
80 ms |
35216 KB |
Output is correct |
77 |
Correct |
149 ms |
34756 KB |
Output is correct |
78 |
Correct |
193 ms |
34896 KB |
Output is correct |
79 |
Correct |
209 ms |
35020 KB |
Output is correct |
80 |
Correct |
191 ms |
34792 KB |
Output is correct |
81 |
Correct |
204 ms |
34916 KB |
Output is correct |
82 |
Correct |
100 ms |
34848 KB |
Output is correct |
83 |
Correct |
100 ms |
35020 KB |
Output is correct |
84 |
Correct |
115 ms |
34812 KB |
Output is correct |
85 |
Correct |
178 ms |
34748 KB |
Output is correct |
86 |
Correct |
189 ms |
34924 KB |
Output is correct |
87 |
Correct |
160 ms |
34796 KB |
Output is correct |
88 |
Correct |
347 ms |
44364 KB |
Output is correct |
89 |
Correct |
323 ms |
42860 KB |
Output is correct |
90 |
Correct |
276 ms |
39212 KB |
Output is correct |
91 |
Correct |
223 ms |
35416 KB |
Output is correct |
92 |
Correct |
134 ms |
34912 KB |
Output is correct |
93 |
Correct |
215 ms |
34784 KB |
Output is correct |
94 |
Correct |
206 ms |
34780 KB |
Output is correct |
95 |
Correct |
317 ms |
45912 KB |
Output is correct |
96 |
Correct |
254 ms |
40656 KB |
Output is correct |
97 |
Correct |
236 ms |
37984 KB |
Output is correct |
98 |
Correct |
234 ms |
35576 KB |
Output is correct |
99 |
Correct |
217 ms |
35052 KB |
Output is correct |
100 |
Correct |
217 ms |
34980 KB |
Output is correct |
101 |
Correct |
172 ms |
47352 KB |
Output is correct |
102 |
Correct |
157 ms |
39908 KB |
Output is correct |
103 |
Correct |
156 ms |
38456 KB |
Output is correct |
104 |
Correct |
169 ms |
38096 KB |
Output is correct |
105 |
Correct |
192 ms |
37184 KB |
Output is correct |
106 |
Correct |
155 ms |
35292 KB |
Output is correct |
107 |
Correct |
177 ms |
34892 KB |
Output is correct |
108 |
Correct |
187 ms |
34912 KB |
Output is correct |
109 |
Correct |
288 ms |
58208 KB |
Output is correct |
110 |
Correct |
225 ms |
39360 KB |
Output is correct |
111 |
Correct |
210 ms |
35552 KB |
Output is correct |
112 |
Correct |
163 ms |
38884 KB |
Output is correct |
113 |
Correct |
187 ms |
35036 KB |
Output is correct |
114 |
Correct |
190 ms |
34896 KB |
Output is correct |
115 |
Correct |
97 ms |
34900 KB |
Output is correct |
116 |
Correct |
104 ms |
34784 KB |
Output is correct |
117 |
Correct |
158 ms |
34952 KB |
Output is correct |
118 |
Correct |
156 ms |
34892 KB |
Output is correct |
119 |
Correct |
154 ms |
34920 KB |
Output is correct |
120 |
Correct |
158 ms |
34900 KB |
Output is correct |