#include <bits/stdc++.h>
using namespace std;
struct Cell {
int len, pref, suf, ans;
Cell() {len = 0, pref = 0, suf = 0, ans = 0;}
Cell operator+(const Cell& other) const {
Cell res;
res.len = len + other.len;
res.pref = pref;
if (pref == len) { res.pref += other.pref; }
res.suf = other.suf;
if (other.suf == other.len) { res.suf += suf; }
res.ans = max(suf + other.pref, max(ans, other.ans));
return res;
}
~Cell() {}
};
struct TreeSeg {
int n, N;
vector<Cell> st;
TreeSeg() {}
TreeSeg(int _n) {
n = _n, N = 1;
while (N < n) {
N <<= 1;
}
st.resize(2 * N);
for (int i = 0; i < n; ++i) {
st[N + i].len = 1;
}
for (int i = N - 1; i > 0; --i) {
st[i].len = st[2 * i].len + st[2 * i + 1].len;
}
}
void turn(int v, int tl, int tr, int i) {
if (tl + 1 == tr) {
st[v].pref = st[v].suf = st[v].ans = 1;
return;
}
int m = tl + (tr - tl) / 2;
if (i >= m) {
turn(2 * v + 1, m, tr, i);
} else {
turn(2 * v, tl, m, i);
}
st[v] = st[2 * v] + st[2 * v + 1];
}
void turn(int i) {
turn(1, 0, N, i);
}
Cell curLeft;
int getSeg(int v, int tl, int tr, int l, int d) {
if (tr <= l) {
return tr;
}
if (tl >= l && (curLeft + st[v]).ans < d) {
curLeft = curLeft + st[v];
return tr;
}
if (tl + 1 == tr) {
return tl;
}
int m = tl + (tr - tl) / 2;
int res = getSeg(2 * v, tl, m, l, d);
if (res == m) {
res = getSeg(2 * v + 1, m, tr, l, d);
}
return res;
}
int getSeg(int l, int d) {
curLeft.len = curLeft.pref = curLeft.suf = curLeft.ans = 0;
return getSeg(1, 0, N, l, d);
}
~TreeSeg() {}
};
struct TreeDP {
int n, N;
vector<set<pair<int, int>>> st;
TreeDP() {}
TreeDP(int _n) {
n = _n, N = 1;
while (N < n) {
N <<= 1;
}
st.resize(2 * N);
}
void insert(int v, int tl, int tr, int l, int r, int key, int val) {
if (tl >= r || tr <= l) {
return;
}
if (l <= tl && tr <= r) {
pair<int, int> cur = {key, n + 10};
auto it = st[v].upper_bound(cur);
cur.second = val;
if (it == st[v].begin() || prev(it)->second < val) {
while (it != st[v].end() && it->second <= val) {
it = st[v].erase(it);
}
st[v].insert(cur);
}
return;
}
int m = tl + (tr - tl) / 2;
insert(2 * v, tl, m, l, r, key, val);
insert(2 * v + 1, m, tr, l, r, key, val);
}
void insert(int l, int r, int key, int val) {
if (l >= r) {
return;
}
insert(1, 0, N, l, r, key, val);
}
int query(int v, int tl, int tr, int i, int x) {
int res = 0;
auto it = st[v].lower_bound(make_pair(x, -1));
if (it != st[v].begin()) {
res = prev(it)->second;
}
if (tl + 1 < tr) {
int m = tl + (tr - tl) / 2;
if (i < m) {
res = max(res, query(2 * v, tl, m, i, x));
} else {
res = max(res, query(2 * v + 1, m, tr, i, x));
}
}
return res;
}
int query(int i, int x) {
return query(1, 0, N, i, x);
}
~TreeDP() {}
};
void solve() {
int n, d;
cin >> n >> d;
vector<int> a(n), order(n);
for (int i = 0; i < n; ++i) {
cin >> a[i];
order[i] = i;
}
sort(order.begin(), order.end(), [&](const int& A, const int& B) {
return make_pair(-a[A], A) < make_pair(-a[B], B);
});
TreeSeg aux(n);
vector<int> border(n);
for (const int& i : order) {
border[i] = aux.getSeg(i + 1, d);
aux.turn(i);
}
TreeDP st(n);
vector<int> dp(n);
int ans = 0;
for (int i = 0; i < n; ++i) {
dp[i] = st.query(i, a[i]) + 1;
st.insert(i + 1, min(border[i] + 1, n), a[i], dp[i]);
ans = max(ans, dp[i]);
}
cout << ans << '\n';
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
#ifdef LOCAL
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
int T = 1;
cin >> T;
while (T--) {
solve();
cerr << "-----------\n";
cout << "-----------\n";
}
#else
int T = 1;
// cin >> T;
while (T--) {
solve();
}
#endif
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
1 ms |
604 KB |
Output is correct |
7 |
Correct |
1 ms |
348 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
11 |
Correct |
1 ms |
344 KB |
Output is correct |
12 |
Correct |
1 ms |
348 KB |
Output is correct |
13 |
Correct |
1 ms |
348 KB |
Output is correct |
14 |
Correct |
0 ms |
348 KB |
Output is correct |
15 |
Correct |
0 ms |
344 KB |
Output is correct |
16 |
Correct |
0 ms |
348 KB |
Output is correct |
17 |
Correct |
0 ms |
348 KB |
Output is correct |
18 |
Correct |
0 ms |
348 KB |
Output is correct |
19 |
Correct |
0 ms |
348 KB |
Output is correct |
20 |
Correct |
0 ms |
348 KB |
Output is correct |
21 |
Correct |
0 ms |
372 KB |
Output is correct |
22 |
Correct |
0 ms |
348 KB |
Output is correct |
23 |
Correct |
1 ms |
348 KB |
Output is correct |
24 |
Correct |
0 ms |
348 KB |
Output is correct |
25 |
Correct |
1 ms |
604 KB |
Output is correct |
26 |
Correct |
1 ms |
348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
1 ms |
604 KB |
Output is correct |
7 |
Correct |
1 ms |
348 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
11 |
Correct |
1 ms |
344 KB |
Output is correct |
12 |
Correct |
1 ms |
348 KB |
Output is correct |
13 |
Correct |
1 ms |
348 KB |
Output is correct |
14 |
Correct |
0 ms |
348 KB |
Output is correct |
15 |
Correct |
0 ms |
344 KB |
Output is correct |
16 |
Correct |
0 ms |
348 KB |
Output is correct |
17 |
Correct |
0 ms |
348 KB |
Output is correct |
18 |
Correct |
0 ms |
348 KB |
Output is correct |
19 |
Correct |
0 ms |
348 KB |
Output is correct |
20 |
Correct |
0 ms |
348 KB |
Output is correct |
21 |
Correct |
0 ms |
372 KB |
Output is correct |
22 |
Correct |
0 ms |
348 KB |
Output is correct |
23 |
Correct |
1 ms |
348 KB |
Output is correct |
24 |
Correct |
0 ms |
348 KB |
Output is correct |
25 |
Correct |
1 ms |
604 KB |
Output is correct |
26 |
Correct |
1 ms |
348 KB |
Output is correct |
27 |
Correct |
1 ms |
504 KB |
Output is correct |
28 |
Correct |
1 ms |
348 KB |
Output is correct |
29 |
Correct |
1 ms |
348 KB |
Output is correct |
30 |
Correct |
1 ms |
348 KB |
Output is correct |
31 |
Correct |
1 ms |
452 KB |
Output is correct |
32 |
Correct |
1 ms |
348 KB |
Output is correct |
33 |
Correct |
1 ms |
348 KB |
Output is correct |
34 |
Correct |
1 ms |
348 KB |
Output is correct |
35 |
Correct |
1 ms |
344 KB |
Output is correct |
36 |
Correct |
1 ms |
344 KB |
Output is correct |
37 |
Correct |
1 ms |
348 KB |
Output is correct |
38 |
Correct |
1 ms |
348 KB |
Output is correct |
39 |
Correct |
1 ms |
348 KB |
Output is correct |
40 |
Correct |
1 ms |
348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
1 ms |
604 KB |
Output is correct |
7 |
Correct |
1 ms |
348 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
11 |
Correct |
1 ms |
344 KB |
Output is correct |
12 |
Correct |
1 ms |
348 KB |
Output is correct |
13 |
Correct |
1 ms |
348 KB |
Output is correct |
14 |
Correct |
0 ms |
348 KB |
Output is correct |
15 |
Correct |
0 ms |
344 KB |
Output is correct |
16 |
Correct |
0 ms |
348 KB |
Output is correct |
17 |
Correct |
0 ms |
348 KB |
Output is correct |
18 |
Correct |
0 ms |
348 KB |
Output is correct |
19 |
Correct |
0 ms |
348 KB |
Output is correct |
20 |
Correct |
0 ms |
348 KB |
Output is correct |
21 |
Correct |
0 ms |
372 KB |
Output is correct |
22 |
Correct |
0 ms |
348 KB |
Output is correct |
23 |
Correct |
1 ms |
348 KB |
Output is correct |
24 |
Correct |
0 ms |
348 KB |
Output is correct |
25 |
Correct |
1 ms |
604 KB |
Output is correct |
26 |
Correct |
1 ms |
348 KB |
Output is correct |
27 |
Correct |
1 ms |
504 KB |
Output is correct |
28 |
Correct |
1 ms |
348 KB |
Output is correct |
29 |
Correct |
1 ms |
348 KB |
Output is correct |
30 |
Correct |
1 ms |
348 KB |
Output is correct |
31 |
Correct |
1 ms |
452 KB |
Output is correct |
32 |
Correct |
1 ms |
348 KB |
Output is correct |
33 |
Correct |
1 ms |
348 KB |
Output is correct |
34 |
Correct |
1 ms |
348 KB |
Output is correct |
35 |
Correct |
1 ms |
344 KB |
Output is correct |
36 |
Correct |
1 ms |
344 KB |
Output is correct |
37 |
Correct |
1 ms |
348 KB |
Output is correct |
38 |
Correct |
1 ms |
348 KB |
Output is correct |
39 |
Correct |
1 ms |
348 KB |
Output is correct |
40 |
Correct |
1 ms |
348 KB |
Output is correct |
41 |
Correct |
6 ms |
2140 KB |
Output is correct |
42 |
Correct |
7 ms |
2156 KB |
Output is correct |
43 |
Correct |
9 ms |
2140 KB |
Output is correct |
44 |
Correct |
12 ms |
2684 KB |
Output is correct |
45 |
Correct |
17 ms |
2652 KB |
Output is correct |
46 |
Correct |
15 ms |
2908 KB |
Output is correct |
47 |
Correct |
9 ms |
2396 KB |
Output is correct |
48 |
Correct |
10 ms |
2652 KB |
Output is correct |
49 |
Correct |
13 ms |
2652 KB |
Output is correct |
50 |
Correct |
14 ms |
2648 KB |
Output is correct |
51 |
Correct |
6 ms |
2140 KB |
Output is correct |
52 |
Correct |
7 ms |
2140 KB |
Output is correct |
53 |
Correct |
6 ms |
2396 KB |
Output is correct |
54 |
Correct |
10 ms |
2648 KB |
Output is correct |
55 |
Correct |
16 ms |
2888 KB |
Output is correct |
56 |
Correct |
17 ms |
2908 KB |
Output is correct |
57 |
Correct |
19 ms |
2860 KB |
Output is correct |
58 |
Correct |
7 ms |
2000 KB |
Output is correct |
59 |
Correct |
7 ms |
1952 KB |
Output is correct |
60 |
Correct |
8 ms |
1952 KB |
Output is correct |
61 |
Correct |
8 ms |
1884 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
252 ms |
87664 KB |
Output is correct |
2 |
Correct |
285 ms |
93160 KB |
Output is correct |
3 |
Correct |
278 ms |
94656 KB |
Output is correct |
4 |
Correct |
312 ms |
94800 KB |
Output is correct |
5 |
Correct |
282 ms |
93240 KB |
Output is correct |
6 |
Correct |
325 ms |
94972 KB |
Output is correct |
7 |
Correct |
190 ms |
87632 KB |
Output is correct |
8 |
Correct |
414 ms |
87508 KB |
Output is correct |
9 |
Correct |
208 ms |
89948 KB |
Output is correct |
10 |
Correct |
357 ms |
93412 KB |
Output is correct |
11 |
Correct |
286 ms |
95052 KB |
Output is correct |
12 |
Correct |
279 ms |
94788 KB |
Output is correct |
13 |
Correct |
241 ms |
87888 KB |
Output is correct |
14 |
Correct |
329 ms |
89196 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
236 ms |
88088 KB |
Output is correct |
2 |
Correct |
710 ms |
126824 KB |
Output is correct |
3 |
Correct |
1302 ms |
145852 KB |
Output is correct |
4 |
Correct |
1218 ms |
145936 KB |
Output is correct |
5 |
Correct |
1602 ms |
209084 KB |
Output is correct |
6 |
Correct |
1257 ms |
144684 KB |
Output is correct |
7 |
Correct |
1698 ms |
293708 KB |
Output is correct |
8 |
Correct |
383 ms |
87636 KB |
Output is correct |
9 |
Correct |
911 ms |
148188 KB |
Output is correct |
10 |
Correct |
1156 ms |
135508 KB |
Output is correct |
11 |
Correct |
1194 ms |
148304 KB |
Output is correct |
12 |
Correct |
530 ms |
90196 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
1 ms |
604 KB |
Output is correct |
7 |
Correct |
1 ms |
348 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
11 |
Correct |
1 ms |
344 KB |
Output is correct |
12 |
Correct |
1 ms |
348 KB |
Output is correct |
13 |
Correct |
1 ms |
348 KB |
Output is correct |
14 |
Correct |
0 ms |
348 KB |
Output is correct |
15 |
Correct |
0 ms |
344 KB |
Output is correct |
16 |
Correct |
0 ms |
348 KB |
Output is correct |
17 |
Correct |
0 ms |
348 KB |
Output is correct |
18 |
Correct |
0 ms |
348 KB |
Output is correct |
19 |
Correct |
0 ms |
348 KB |
Output is correct |
20 |
Correct |
0 ms |
348 KB |
Output is correct |
21 |
Correct |
0 ms |
372 KB |
Output is correct |
22 |
Correct |
0 ms |
348 KB |
Output is correct |
23 |
Correct |
1 ms |
348 KB |
Output is correct |
24 |
Correct |
0 ms |
348 KB |
Output is correct |
25 |
Correct |
1 ms |
604 KB |
Output is correct |
26 |
Correct |
1 ms |
348 KB |
Output is correct |
27 |
Correct |
1 ms |
504 KB |
Output is correct |
28 |
Correct |
1 ms |
348 KB |
Output is correct |
29 |
Correct |
1 ms |
348 KB |
Output is correct |
30 |
Correct |
1 ms |
348 KB |
Output is correct |
31 |
Correct |
1 ms |
452 KB |
Output is correct |
32 |
Correct |
1 ms |
348 KB |
Output is correct |
33 |
Correct |
1 ms |
348 KB |
Output is correct |
34 |
Correct |
1 ms |
348 KB |
Output is correct |
35 |
Correct |
1 ms |
344 KB |
Output is correct |
36 |
Correct |
1 ms |
344 KB |
Output is correct |
37 |
Correct |
1 ms |
348 KB |
Output is correct |
38 |
Correct |
1 ms |
348 KB |
Output is correct |
39 |
Correct |
1 ms |
348 KB |
Output is correct |
40 |
Correct |
1 ms |
348 KB |
Output is correct |
41 |
Correct |
6 ms |
2140 KB |
Output is correct |
42 |
Correct |
7 ms |
2156 KB |
Output is correct |
43 |
Correct |
9 ms |
2140 KB |
Output is correct |
44 |
Correct |
12 ms |
2684 KB |
Output is correct |
45 |
Correct |
17 ms |
2652 KB |
Output is correct |
46 |
Correct |
15 ms |
2908 KB |
Output is correct |
47 |
Correct |
9 ms |
2396 KB |
Output is correct |
48 |
Correct |
10 ms |
2652 KB |
Output is correct |
49 |
Correct |
13 ms |
2652 KB |
Output is correct |
50 |
Correct |
14 ms |
2648 KB |
Output is correct |
51 |
Correct |
6 ms |
2140 KB |
Output is correct |
52 |
Correct |
7 ms |
2140 KB |
Output is correct |
53 |
Correct |
6 ms |
2396 KB |
Output is correct |
54 |
Correct |
10 ms |
2648 KB |
Output is correct |
55 |
Correct |
16 ms |
2888 KB |
Output is correct |
56 |
Correct |
17 ms |
2908 KB |
Output is correct |
57 |
Correct |
19 ms |
2860 KB |
Output is correct |
58 |
Correct |
7 ms |
2000 KB |
Output is correct |
59 |
Correct |
7 ms |
1952 KB |
Output is correct |
60 |
Correct |
8 ms |
1952 KB |
Output is correct |
61 |
Correct |
8 ms |
1884 KB |
Output is correct |
62 |
Correct |
252 ms |
87664 KB |
Output is correct |
63 |
Correct |
285 ms |
93160 KB |
Output is correct |
64 |
Correct |
278 ms |
94656 KB |
Output is correct |
65 |
Correct |
312 ms |
94800 KB |
Output is correct |
66 |
Correct |
282 ms |
93240 KB |
Output is correct |
67 |
Correct |
325 ms |
94972 KB |
Output is correct |
68 |
Correct |
190 ms |
87632 KB |
Output is correct |
69 |
Correct |
414 ms |
87508 KB |
Output is correct |
70 |
Correct |
208 ms |
89948 KB |
Output is correct |
71 |
Correct |
357 ms |
93412 KB |
Output is correct |
72 |
Correct |
286 ms |
95052 KB |
Output is correct |
73 |
Correct |
279 ms |
94788 KB |
Output is correct |
74 |
Correct |
241 ms |
87888 KB |
Output is correct |
75 |
Correct |
329 ms |
89196 KB |
Output is correct |
76 |
Correct |
236 ms |
88088 KB |
Output is correct |
77 |
Correct |
710 ms |
126824 KB |
Output is correct |
78 |
Correct |
1302 ms |
145852 KB |
Output is correct |
79 |
Correct |
1218 ms |
145936 KB |
Output is correct |
80 |
Correct |
1602 ms |
209084 KB |
Output is correct |
81 |
Correct |
1257 ms |
144684 KB |
Output is correct |
82 |
Correct |
1698 ms |
293708 KB |
Output is correct |
83 |
Correct |
383 ms |
87636 KB |
Output is correct |
84 |
Correct |
911 ms |
148188 KB |
Output is correct |
85 |
Correct |
1156 ms |
135508 KB |
Output is correct |
86 |
Correct |
1194 ms |
148304 KB |
Output is correct |
87 |
Correct |
530 ms |
90196 KB |
Output is correct |
88 |
Correct |
386 ms |
104532 KB |
Output is correct |
89 |
Correct |
465 ms |
111952 KB |
Output is correct |
90 |
Correct |
831 ms |
131560 KB |
Output is correct |
91 |
Correct |
1206 ms |
145772 KB |
Output is correct |
92 |
Correct |
525 ms |
117756 KB |
Output is correct |
93 |
Correct |
1209 ms |
145588 KB |
Output is correct |
94 |
Correct |
1325 ms |
145912 KB |
Output is correct |
95 |
Correct |
362 ms |
104548 KB |
Output is correct |
96 |
Correct |
675 ms |
126888 KB |
Output is correct |
97 |
Correct |
1047 ms |
133816 KB |
Output is correct |
98 |
Correct |
1397 ms |
147196 KB |
Output is correct |
99 |
Correct |
1332 ms |
146360 KB |
Output is correct |
100 |
Correct |
1418 ms |
146464 KB |
Output is correct |
101 |
Correct |
231 ms |
96584 KB |
Output is correct |
102 |
Correct |
449 ms |
112984 KB |
Output is correct |
103 |
Correct |
665 ms |
121428 KB |
Output is correct |
104 |
Correct |
862 ms |
129876 KB |
Output is correct |
105 |
Correct |
1150 ms |
138440 KB |
Output is correct |
106 |
Correct |
852 ms |
125508 KB |
Output is correct |
107 |
Correct |
1081 ms |
135060 KB |
Output is correct |
108 |
Correct |
1186 ms |
143308 KB |
Output is correct |
109 |
Correct |
467 ms |
152628 KB |
Output is correct |
110 |
Correct |
1090 ms |
149552 KB |
Output is correct |
111 |
Correct |
1192 ms |
139704 KB |
Output is correct |
112 |
Correct |
1259 ms |
189552 KB |
Output is correct |
113 |
Correct |
1283 ms |
148804 KB |
Output is correct |
114 |
Correct |
1206 ms |
141324 KB |
Output is correct |
115 |
Correct |
389 ms |
87704 KB |
Output is correct |
116 |
Correct |
387 ms |
87592 KB |
Output is correct |
117 |
Correct |
416 ms |
87620 KB |
Output is correct |
118 |
Correct |
429 ms |
87660 KB |
Output is correct |
119 |
Correct |
509 ms |
88484 KB |
Output is correct |
120 |
Correct |
494 ms |
88400 KB |
Output is correct |