#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (l); --x)
typedef long long ll;
typedef std::pair<int,int> pii;
using namespace std;
const int S = 3000;
const int N = 300'010+S;
struct sq_t {
vector<int> arr, val;
void init(int *a, int *b, int n) {
vector<pii> vec;
Loop (i,0,n)
vec.push_back({a[i], b[i]});
sort(vec.begin(), vec.end());
vector<pii> vec2;
Loop (i,0,n) {
if (vec2.size() && vec2.back().second >= vec[i].second)
continue;
vec2.push_back(vec[i]);
}
for (auto x : vec2) {
arr.push_back(x.first);
val.push_back(x.second);
}
}
int get(int x) {
int i = lower_bound(arr.begin(), arr.end(), x) - arr.begin();
return i? val[i-1]: 0;
}
} sq[N/S];
int arr[N], val[N];
int get_naive(int l, int r, int x)
{
int ans = 0;
Loop (i,l,r) {
int dard = arr[i] < x? val[i]: 0;
int marg = dard > ans? dard: ans;
ans = marg;
}
return ans;
}
int get(int l, int r, int x)
{
if (l/S == (r-1)/S)
return get_naive(l, r, x);
int ans = 0;
int l2 = l%S? l+S-l%S: l;
int r2 = r-r%S;
ans = max(get_naive(l, l2, x), get_naive(r2, r, x));
Loop (i,l2/S,r2/S)
ans = max(ans, sq[i].get(x));
return ans;
}
set<int> ok, not_ok;
int ql[N];
int main()
{
cin.tie(0) -> sync_with_stdio(false);
int n, d;
cin >> n >> d;
vector<pii> vec;
Loop (i,0,n) {
cin >> arr[i];
vec.push_back({arr[i], i});
}
sort(vec.begin(), vec.end());
reverse(vec.begin(), vec.end());
not_ok = {-1, n};
Loop (i,-1,n+1)
ok.insert(ok.end(), i);
for (auto [_, i] : vec) {
ql[i] = *--not_ok.lower_bound(i) + 1;
auto it = ok.find(i);
auto it0 = it; --it0;
auto it1 = it; ++it1;
ok.erase(it);
//cerr << i << ' ' << *it0 << ' ' << *it1 << '\n';
if (*it1 - *it0 - 1 < d)
continue;
auto itt = not_ok.insert(i);
for (int x = i+1; x < *it1 && !not_ok.count(x); ++x)
not_ok.insert(x);
for (int x = i-1; x > *it0 && !not_ok.count(x); --x)
not_ok.insert(x);
}
val[0] = 1;
Loop (i,1,n) {
if (i%S == 0)
sq[i/S-1].init(arr+i-S, val+i-S, S);
val[i] = get(ql[i], i, arr[i]) + 1;
}
int ans = 0;
Loop (i,0,n)
ans = max(ans, val[i]);
cout << ans << '\n';
}
Compilation message
Main.cpp: In function 'int main()':
Main.cpp:89:8: warning: variable 'itt' set but not used [-Wunused-but-set-variable]
89 | auto itt = not_ok.insert(i);
| ^~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
0 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
0 ms |
340 KB |
Output is correct |
6 |
Correct |
0 ms |
340 KB |
Output is correct |
7 |
Correct |
0 ms |
340 KB |
Output is correct |
8 |
Correct |
0 ms |
340 KB |
Output is correct |
9 |
Correct |
0 ms |
340 KB |
Output is correct |
10 |
Correct |
0 ms |
340 KB |
Output is correct |
11 |
Correct |
1 ms |
340 KB |
Output is correct |
12 |
Correct |
1 ms |
340 KB |
Output is correct |
13 |
Correct |
1 ms |
340 KB |
Output is correct |
14 |
Correct |
1 ms |
340 KB |
Output is correct |
15 |
Correct |
1 ms |
340 KB |
Output is correct |
16 |
Correct |
1 ms |
340 KB |
Output is correct |
17 |
Correct |
1 ms |
340 KB |
Output is correct |
18 |
Correct |
1 ms |
340 KB |
Output is correct |
19 |
Correct |
1 ms |
340 KB |
Output is correct |
20 |
Correct |
0 ms |
340 KB |
Output is correct |
21 |
Correct |
0 ms |
340 KB |
Output is correct |
22 |
Correct |
1 ms |
384 KB |
Output is correct |
23 |
Correct |
1 ms |
340 KB |
Output is correct |
24 |
Correct |
0 ms |
340 KB |
Output is correct |
25 |
Correct |
0 ms |
340 KB |
Output is correct |
26 |
Correct |
1 ms |
340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
0 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
0 ms |
340 KB |
Output is correct |
6 |
Correct |
0 ms |
340 KB |
Output is correct |
7 |
Correct |
0 ms |
340 KB |
Output is correct |
8 |
Correct |
0 ms |
340 KB |
Output is correct |
9 |
Correct |
0 ms |
340 KB |
Output is correct |
10 |
Correct |
0 ms |
340 KB |
Output is correct |
11 |
Correct |
1 ms |
340 KB |
Output is correct |
12 |
Correct |
1 ms |
340 KB |
Output is correct |
13 |
Correct |
1 ms |
340 KB |
Output is correct |
14 |
Correct |
1 ms |
340 KB |
Output is correct |
15 |
Correct |
1 ms |
340 KB |
Output is correct |
16 |
Correct |
1 ms |
340 KB |
Output is correct |
17 |
Correct |
1 ms |
340 KB |
Output is correct |
18 |
Correct |
1 ms |
340 KB |
Output is correct |
19 |
Correct |
1 ms |
340 KB |
Output is correct |
20 |
Correct |
0 ms |
340 KB |
Output is correct |
21 |
Correct |
0 ms |
340 KB |
Output is correct |
22 |
Correct |
1 ms |
384 KB |
Output is correct |
23 |
Correct |
1 ms |
340 KB |
Output is correct |
24 |
Correct |
0 ms |
340 KB |
Output is correct |
25 |
Correct |
0 ms |
340 KB |
Output is correct |
26 |
Correct |
1 ms |
340 KB |
Output is correct |
27 |
Correct |
1 ms |
340 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 |
344 KB |
Output is correct |
32 |
Correct |
1 ms |
340 KB |
Output is correct |
33 |
Correct |
1 ms |
340 KB |
Output is correct |
34 |
Correct |
1 ms |
340 KB |
Output is correct |
35 |
Correct |
1 ms |
340 KB |
Output is correct |
36 |
Correct |
1 ms |
340 KB |
Output is correct |
37 |
Correct |
1 ms |
344 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 |
340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
0 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
0 ms |
340 KB |
Output is correct |
6 |
Correct |
0 ms |
340 KB |
Output is correct |
7 |
Correct |
0 ms |
340 KB |
Output is correct |
8 |
Correct |
0 ms |
340 KB |
Output is correct |
9 |
Correct |
0 ms |
340 KB |
Output is correct |
10 |
Correct |
0 ms |
340 KB |
Output is correct |
11 |
Correct |
1 ms |
340 KB |
Output is correct |
12 |
Correct |
1 ms |
340 KB |
Output is correct |
13 |
Correct |
1 ms |
340 KB |
Output is correct |
14 |
Correct |
1 ms |
340 KB |
Output is correct |
15 |
Correct |
1 ms |
340 KB |
Output is correct |
16 |
Correct |
1 ms |
340 KB |
Output is correct |
17 |
Correct |
1 ms |
340 KB |
Output is correct |
18 |
Correct |
1 ms |
340 KB |
Output is correct |
19 |
Correct |
1 ms |
340 KB |
Output is correct |
20 |
Correct |
0 ms |
340 KB |
Output is correct |
21 |
Correct |
0 ms |
340 KB |
Output is correct |
22 |
Correct |
1 ms |
384 KB |
Output is correct |
23 |
Correct |
1 ms |
340 KB |
Output is correct |
24 |
Correct |
0 ms |
340 KB |
Output is correct |
25 |
Correct |
0 ms |
340 KB |
Output is correct |
26 |
Correct |
1 ms |
340 KB |
Output is correct |
27 |
Correct |
1 ms |
340 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 |
344 KB |
Output is correct |
32 |
Correct |
1 ms |
340 KB |
Output is correct |
33 |
Correct |
1 ms |
340 KB |
Output is correct |
34 |
Correct |
1 ms |
340 KB |
Output is correct |
35 |
Correct |
1 ms |
340 KB |
Output is correct |
36 |
Correct |
1 ms |
340 KB |
Output is correct |
37 |
Correct |
1 ms |
344 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 |
340 KB |
Output is correct |
41 |
Correct |
5 ms |
852 KB |
Output is correct |
42 |
Correct |
5 ms |
852 KB |
Output is correct |
43 |
Correct |
10 ms |
852 KB |
Output is correct |
44 |
Correct |
22 ms |
852 KB |
Output is correct |
45 |
Correct |
27 ms |
828 KB |
Output is correct |
46 |
Correct |
28 ms |
852 KB |
Output is correct |
47 |
Correct |
16 ms |
920 KB |
Output is correct |
48 |
Correct |
15 ms |
908 KB |
Output is correct |
49 |
Correct |
19 ms |
852 KB |
Output is correct |
50 |
Correct |
26 ms |
864 KB |
Output is correct |
51 |
Correct |
4 ms |
860 KB |
Output is correct |
52 |
Correct |
5 ms |
864 KB |
Output is correct |
53 |
Correct |
12 ms |
980 KB |
Output is correct |
54 |
Correct |
13 ms |
928 KB |
Output is correct |
55 |
Correct |
27 ms |
852 KB |
Output is correct |
56 |
Correct |
16 ms |
868 KB |
Output is correct |
57 |
Correct |
17 ms |
864 KB |
Output is correct |
58 |
Correct |
11 ms |
852 KB |
Output is correct |
59 |
Correct |
11 ms |
936 KB |
Output is correct |
60 |
Correct |
12 ms |
852 KB |
Output is correct |
61 |
Correct |
12 ms |
852 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
607 ms |
21124 KB |
Output is correct |
2 |
Correct |
260 ms |
21096 KB |
Output is correct |
3 |
Correct |
249 ms |
21016 KB |
Output is correct |
4 |
Correct |
326 ms |
21532 KB |
Output is correct |
5 |
Correct |
255 ms |
21632 KB |
Output is correct |
6 |
Correct |
335 ms |
21544 KB |
Output is correct |
7 |
Correct |
769 ms |
25664 KB |
Output is correct |
8 |
Correct |
177 ms |
21524 KB |
Output is correct |
9 |
Correct |
537 ms |
23736 KB |
Output is correct |
10 |
Correct |
149 ms |
21728 KB |
Output is correct |
11 |
Correct |
236 ms |
21544 KB |
Output is correct |
12 |
Correct |
256 ms |
21556 KB |
Output is correct |
13 |
Correct |
466 ms |
23836 KB |
Output is correct |
14 |
Correct |
292 ms |
21632 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
591 ms |
21164 KB |
Output is correct |
2 |
Correct |
1523 ms |
21324 KB |
Output is correct |
3 |
Correct |
2099 ms |
21816 KB |
Output is correct |
4 |
Correct |
2128 ms |
21960 KB |
Output is correct |
5 |
Correct |
1496 ms |
23784 KB |
Output is correct |
6 |
Correct |
2065 ms |
22536 KB |
Output is correct |
7 |
Correct |
759 ms |
25392 KB |
Output is correct |
8 |
Correct |
596 ms |
21128 KB |
Output is correct |
9 |
Correct |
737 ms |
21880 KB |
Output is correct |
10 |
Correct |
1528 ms |
21436 KB |
Output is correct |
11 |
Correct |
1307 ms |
21652 KB |
Output is correct |
12 |
Correct |
720 ms |
20588 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
0 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
0 ms |
340 KB |
Output is correct |
6 |
Correct |
0 ms |
340 KB |
Output is correct |
7 |
Correct |
0 ms |
340 KB |
Output is correct |
8 |
Correct |
0 ms |
340 KB |
Output is correct |
9 |
Correct |
0 ms |
340 KB |
Output is correct |
10 |
Correct |
0 ms |
340 KB |
Output is correct |
11 |
Correct |
1 ms |
340 KB |
Output is correct |
12 |
Correct |
1 ms |
340 KB |
Output is correct |
13 |
Correct |
1 ms |
340 KB |
Output is correct |
14 |
Correct |
1 ms |
340 KB |
Output is correct |
15 |
Correct |
1 ms |
340 KB |
Output is correct |
16 |
Correct |
1 ms |
340 KB |
Output is correct |
17 |
Correct |
1 ms |
340 KB |
Output is correct |
18 |
Correct |
1 ms |
340 KB |
Output is correct |
19 |
Correct |
1 ms |
340 KB |
Output is correct |
20 |
Correct |
0 ms |
340 KB |
Output is correct |
21 |
Correct |
0 ms |
340 KB |
Output is correct |
22 |
Correct |
1 ms |
384 KB |
Output is correct |
23 |
Correct |
1 ms |
340 KB |
Output is correct |
24 |
Correct |
0 ms |
340 KB |
Output is correct |
25 |
Correct |
0 ms |
340 KB |
Output is correct |
26 |
Correct |
1 ms |
340 KB |
Output is correct |
27 |
Correct |
1 ms |
340 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 |
344 KB |
Output is correct |
32 |
Correct |
1 ms |
340 KB |
Output is correct |
33 |
Correct |
1 ms |
340 KB |
Output is correct |
34 |
Correct |
1 ms |
340 KB |
Output is correct |
35 |
Correct |
1 ms |
340 KB |
Output is correct |
36 |
Correct |
1 ms |
340 KB |
Output is correct |
37 |
Correct |
1 ms |
344 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 |
340 KB |
Output is correct |
41 |
Correct |
5 ms |
852 KB |
Output is correct |
42 |
Correct |
5 ms |
852 KB |
Output is correct |
43 |
Correct |
10 ms |
852 KB |
Output is correct |
44 |
Correct |
22 ms |
852 KB |
Output is correct |
45 |
Correct |
27 ms |
828 KB |
Output is correct |
46 |
Correct |
28 ms |
852 KB |
Output is correct |
47 |
Correct |
16 ms |
920 KB |
Output is correct |
48 |
Correct |
15 ms |
908 KB |
Output is correct |
49 |
Correct |
19 ms |
852 KB |
Output is correct |
50 |
Correct |
26 ms |
864 KB |
Output is correct |
51 |
Correct |
4 ms |
860 KB |
Output is correct |
52 |
Correct |
5 ms |
864 KB |
Output is correct |
53 |
Correct |
12 ms |
980 KB |
Output is correct |
54 |
Correct |
13 ms |
928 KB |
Output is correct |
55 |
Correct |
27 ms |
852 KB |
Output is correct |
56 |
Correct |
16 ms |
868 KB |
Output is correct |
57 |
Correct |
17 ms |
864 KB |
Output is correct |
58 |
Correct |
11 ms |
852 KB |
Output is correct |
59 |
Correct |
11 ms |
936 KB |
Output is correct |
60 |
Correct |
12 ms |
852 KB |
Output is correct |
61 |
Correct |
12 ms |
852 KB |
Output is correct |
62 |
Correct |
607 ms |
21124 KB |
Output is correct |
63 |
Correct |
260 ms |
21096 KB |
Output is correct |
64 |
Correct |
249 ms |
21016 KB |
Output is correct |
65 |
Correct |
326 ms |
21532 KB |
Output is correct |
66 |
Correct |
255 ms |
21632 KB |
Output is correct |
67 |
Correct |
335 ms |
21544 KB |
Output is correct |
68 |
Correct |
769 ms |
25664 KB |
Output is correct |
69 |
Correct |
177 ms |
21524 KB |
Output is correct |
70 |
Correct |
537 ms |
23736 KB |
Output is correct |
71 |
Correct |
149 ms |
21728 KB |
Output is correct |
72 |
Correct |
236 ms |
21544 KB |
Output is correct |
73 |
Correct |
256 ms |
21556 KB |
Output is correct |
74 |
Correct |
466 ms |
23836 KB |
Output is correct |
75 |
Correct |
292 ms |
21632 KB |
Output is correct |
76 |
Correct |
591 ms |
21164 KB |
Output is correct |
77 |
Correct |
1523 ms |
21324 KB |
Output is correct |
78 |
Correct |
2099 ms |
21816 KB |
Output is correct |
79 |
Correct |
2128 ms |
21960 KB |
Output is correct |
80 |
Correct |
1496 ms |
23784 KB |
Output is correct |
81 |
Correct |
2065 ms |
22536 KB |
Output is correct |
82 |
Correct |
759 ms |
25392 KB |
Output is correct |
83 |
Correct |
596 ms |
21128 KB |
Output is correct |
84 |
Correct |
737 ms |
21880 KB |
Output is correct |
85 |
Correct |
1528 ms |
21436 KB |
Output is correct |
86 |
Correct |
1307 ms |
21652 KB |
Output is correct |
87 |
Correct |
720 ms |
20588 KB |
Output is correct |
88 |
Correct |
403 ms |
20816 KB |
Output is correct |
89 |
Correct |
501 ms |
20924 KB |
Output is correct |
90 |
Correct |
1377 ms |
22004 KB |
Output is correct |
91 |
Correct |
2301 ms |
22340 KB |
Output is correct |
92 |
Correct |
1588 ms |
21684 KB |
Output is correct |
93 |
Correct |
2369 ms |
22240 KB |
Output is correct |
94 |
Correct |
2388 ms |
22348 KB |
Output is correct |
95 |
Correct |
398 ms |
21812 KB |
Output is correct |
96 |
Correct |
1322 ms |
22544 KB |
Output is correct |
97 |
Correct |
1892 ms |
22076 KB |
Output is correct |
98 |
Correct |
2118 ms |
23020 KB |
Output is correct |
99 |
Correct |
2161 ms |
22432 KB |
Output is correct |
100 |
Correct |
2180 ms |
22328 KB |
Output is correct |
101 |
Correct |
610 ms |
23732 KB |
Output is correct |
102 |
Correct |
756 ms |
22368 KB |
Output is correct |
103 |
Correct |
857 ms |
22192 KB |
Output is correct |
104 |
Correct |
1399 ms |
21832 KB |
Output is correct |
105 |
Correct |
1657 ms |
22120 KB |
Output is correct |
106 |
Correct |
1564 ms |
21852 KB |
Output is correct |
107 |
Correct |
1834 ms |
21924 KB |
Output is correct |
108 |
Correct |
2145 ms |
22428 KB |
Output is correct |
109 |
Correct |
690 ms |
25956 KB |
Output is correct |
110 |
Correct |
1086 ms |
22240 KB |
Output is correct |
111 |
Correct |
1307 ms |
22304 KB |
Output is correct |
112 |
Correct |
928 ms |
25960 KB |
Output is correct |
113 |
Correct |
1305 ms |
22444 KB |
Output is correct |
114 |
Correct |
1373 ms |
22280 KB |
Output is correct |
115 |
Correct |
652 ms |
21876 KB |
Output is correct |
116 |
Correct |
619 ms |
21600 KB |
Output is correct |
117 |
Correct |
626 ms |
21608 KB |
Output is correct |
118 |
Correct |
621 ms |
21584 KB |
Output is correct |
119 |
Correct |
719 ms |
21592 KB |
Output is correct |
120 |
Correct |
698 ms |
21712 KB |
Output is correct |