#include <bits/stdc++.h>
using namespace std;
#define int long long
mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());
const int N = 3e5 + 5;
int n, k;
vector<int> a(N), seg(N * 4), par(N), min_lol(N);
bool cmp(pair<int, int> x, pair<int, int> y) {
if(x.first == y.first) {
return x.second > y.second;
}
return x.first < y.first;
}
int Find(int x) {
if(x == par[x]) return x;
return par[x] = Find(par[x]);
}
void Unite(int x, int y) {
x = Find(x), y = Find(y);
min_lol[y] = min(min_lol[x], min_lol[y]);
par[x] = y;
}
int Query(int l, int r, int pos, int ql, int qr) {
if(ql <= l && r <= qr) {
return seg[pos];
}
if(ql > r || l > qr) {
return 0;
}
int mid = (l + r) >> 1;
return max(Query(l, mid, pos * 2, ql, qr), Query(mid + 1, r, pos * 2 + 1, ql, qr));
}
void Update(int l, int r, int pos, int qpos, int qval) {
if(l == r) {
seg[pos] = qval;
return;
}
int mid = (l + r) >> 1;
if(qpos <= mid) {
Update(l, mid, pos * 2, qpos, qval);
}
else {
Update(mid + 1, r, pos * 2 + 1, qpos, qval);
}
seg[pos] = max(seg[pos * 2], seg[pos * 2 + 1]);
}
void Solve() {
cin >> n >> k;
for(int i = 1; i <= n; i++) {
cin >> a[i];
par[i] = i;
min_lol[i] = i;
}
map<int, int> mp;
for(int i = 1; i <= n; i++) {
mp[a[i]]++;
}
int cnt = 1;
for(auto i: mp) {
mp[i.first] = cnt++;
}
for(int i = 1; i <= n; i++) {
a[i] = mp[a[i]];
}
vector<pair<int, int> > temp;
for(int i = 1; i <= n; i++) {
temp.push_back({a[i], i});
}
sort(temp.begin(), temp.end(), cmp);
for(int i = 0; i < temp.size(); i++) {
//cout << temp[i].first << " " << temp[i].second << "\n";
for(int j = temp[i].second; j > max(1LL, temp[i].second - k); j--) {
//cout << temp[i].first << " " << temp[i].second << " " << j << "\n";
if(Find(j) != Find(j - 1)) {
Unite(j - 1, j);
}
j = min_lol[Find(j)] + 1;
}
/*for(int j = temp[i].second; j < min(n, temp[i].second + k); j++) {
if(Find(j) != Find(j + 1)) {
Unite(j, j + 1);
}
}*/
int val = Query(1, n, 1, min_lol[Find(temp[i].second)], temp[i].second - 1);
Update(1, n, 1, temp[i].second, val + 1);
//cout << "val = " << val << "\n";
}
cout << seg[1] << "\n";
}
int32_t main() {
auto begin = std::chrono::high_resolution_clock::now();
ios_base::sync_with_stdio(0);
cin.tie(0);
int t = 1;
//cin >> t;
while(t--) {
Solve();
}
auto end = std::chrono::high_resolution_clock::now();
auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n";
return 0;
}
Compilation message
Main.cpp: In function 'void Solve()':
Main.cpp:78:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
78 | for(int i = 0; i < temp.size(); i++) {
| ~~^~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
9 ms |
16700 KB |
Output is correct |
2 |
Correct |
8 ms |
16724 KB |
Output is correct |
3 |
Correct |
8 ms |
16768 KB |
Output is correct |
4 |
Correct |
10 ms |
16724 KB |
Output is correct |
5 |
Correct |
8 ms |
16740 KB |
Output is correct |
6 |
Correct |
7 ms |
16724 KB |
Output is correct |
7 |
Correct |
7 ms |
16652 KB |
Output is correct |
8 |
Correct |
7 ms |
16724 KB |
Output is correct |
9 |
Correct |
7 ms |
16748 KB |
Output is correct |
10 |
Correct |
7 ms |
16724 KB |
Output is correct |
11 |
Correct |
9 ms |
16688 KB |
Output is correct |
12 |
Correct |
8 ms |
16724 KB |
Output is correct |
13 |
Correct |
8 ms |
16724 KB |
Output is correct |
14 |
Correct |
8 ms |
16724 KB |
Output is correct |
15 |
Correct |
7 ms |
16724 KB |
Output is correct |
16 |
Correct |
10 ms |
16724 KB |
Output is correct |
17 |
Correct |
8 ms |
16724 KB |
Output is correct |
18 |
Correct |
9 ms |
16724 KB |
Output is correct |
19 |
Correct |
10 ms |
16720 KB |
Output is correct |
20 |
Correct |
9 ms |
16724 KB |
Output is correct |
21 |
Correct |
8 ms |
16724 KB |
Output is correct |
22 |
Correct |
7 ms |
16664 KB |
Output is correct |
23 |
Correct |
7 ms |
16696 KB |
Output is correct |
24 |
Correct |
7 ms |
16768 KB |
Output is correct |
25 |
Correct |
7 ms |
16724 KB |
Output is correct |
26 |
Correct |
7 ms |
16724 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
9 ms |
16700 KB |
Output is correct |
2 |
Correct |
8 ms |
16724 KB |
Output is correct |
3 |
Correct |
8 ms |
16768 KB |
Output is correct |
4 |
Correct |
10 ms |
16724 KB |
Output is correct |
5 |
Correct |
8 ms |
16740 KB |
Output is correct |
6 |
Correct |
7 ms |
16724 KB |
Output is correct |
7 |
Correct |
7 ms |
16652 KB |
Output is correct |
8 |
Correct |
7 ms |
16724 KB |
Output is correct |
9 |
Correct |
7 ms |
16748 KB |
Output is correct |
10 |
Correct |
7 ms |
16724 KB |
Output is correct |
11 |
Correct |
9 ms |
16688 KB |
Output is correct |
12 |
Correct |
8 ms |
16724 KB |
Output is correct |
13 |
Correct |
8 ms |
16724 KB |
Output is correct |
14 |
Correct |
8 ms |
16724 KB |
Output is correct |
15 |
Correct |
7 ms |
16724 KB |
Output is correct |
16 |
Correct |
10 ms |
16724 KB |
Output is correct |
17 |
Correct |
8 ms |
16724 KB |
Output is correct |
18 |
Correct |
9 ms |
16724 KB |
Output is correct |
19 |
Correct |
10 ms |
16720 KB |
Output is correct |
20 |
Correct |
9 ms |
16724 KB |
Output is correct |
21 |
Correct |
8 ms |
16724 KB |
Output is correct |
22 |
Correct |
7 ms |
16664 KB |
Output is correct |
23 |
Correct |
7 ms |
16696 KB |
Output is correct |
24 |
Correct |
7 ms |
16768 KB |
Output is correct |
25 |
Correct |
7 ms |
16724 KB |
Output is correct |
26 |
Correct |
7 ms |
16724 KB |
Output is correct |
27 |
Correct |
10 ms |
16764 KB |
Output is correct |
28 |
Correct |
8 ms |
16724 KB |
Output is correct |
29 |
Correct |
7 ms |
16724 KB |
Output is correct |
30 |
Correct |
7 ms |
16724 KB |
Output is correct |
31 |
Correct |
8 ms |
16724 KB |
Output is correct |
32 |
Correct |
8 ms |
16724 KB |
Output is correct |
33 |
Correct |
8 ms |
16724 KB |
Output is correct |
34 |
Correct |
8 ms |
16724 KB |
Output is correct |
35 |
Correct |
8 ms |
16724 KB |
Output is correct |
36 |
Correct |
8 ms |
16800 KB |
Output is correct |
37 |
Correct |
8 ms |
16724 KB |
Output is correct |
38 |
Correct |
7 ms |
16724 KB |
Output is correct |
39 |
Correct |
7 ms |
16724 KB |
Output is correct |
40 |
Correct |
7 ms |
16724 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
9 ms |
16700 KB |
Output is correct |
2 |
Correct |
8 ms |
16724 KB |
Output is correct |
3 |
Correct |
8 ms |
16768 KB |
Output is correct |
4 |
Correct |
10 ms |
16724 KB |
Output is correct |
5 |
Correct |
8 ms |
16740 KB |
Output is correct |
6 |
Correct |
7 ms |
16724 KB |
Output is correct |
7 |
Correct |
7 ms |
16652 KB |
Output is correct |
8 |
Correct |
7 ms |
16724 KB |
Output is correct |
9 |
Correct |
7 ms |
16748 KB |
Output is correct |
10 |
Correct |
7 ms |
16724 KB |
Output is correct |
11 |
Correct |
9 ms |
16688 KB |
Output is correct |
12 |
Correct |
8 ms |
16724 KB |
Output is correct |
13 |
Correct |
8 ms |
16724 KB |
Output is correct |
14 |
Correct |
8 ms |
16724 KB |
Output is correct |
15 |
Correct |
7 ms |
16724 KB |
Output is correct |
16 |
Correct |
10 ms |
16724 KB |
Output is correct |
17 |
Correct |
8 ms |
16724 KB |
Output is correct |
18 |
Correct |
9 ms |
16724 KB |
Output is correct |
19 |
Correct |
10 ms |
16720 KB |
Output is correct |
20 |
Correct |
9 ms |
16724 KB |
Output is correct |
21 |
Correct |
8 ms |
16724 KB |
Output is correct |
22 |
Correct |
7 ms |
16664 KB |
Output is correct |
23 |
Correct |
7 ms |
16696 KB |
Output is correct |
24 |
Correct |
7 ms |
16768 KB |
Output is correct |
25 |
Correct |
7 ms |
16724 KB |
Output is correct |
26 |
Correct |
7 ms |
16724 KB |
Output is correct |
27 |
Correct |
10 ms |
16764 KB |
Output is correct |
28 |
Correct |
8 ms |
16724 KB |
Output is correct |
29 |
Correct |
7 ms |
16724 KB |
Output is correct |
30 |
Correct |
7 ms |
16724 KB |
Output is correct |
31 |
Correct |
8 ms |
16724 KB |
Output is correct |
32 |
Correct |
8 ms |
16724 KB |
Output is correct |
33 |
Correct |
8 ms |
16724 KB |
Output is correct |
34 |
Correct |
8 ms |
16724 KB |
Output is correct |
35 |
Correct |
8 ms |
16724 KB |
Output is correct |
36 |
Correct |
8 ms |
16800 KB |
Output is correct |
37 |
Correct |
8 ms |
16724 KB |
Output is correct |
38 |
Correct |
7 ms |
16724 KB |
Output is correct |
39 |
Correct |
7 ms |
16724 KB |
Output is correct |
40 |
Correct |
7 ms |
16724 KB |
Output is correct |
41 |
Correct |
14 ms |
16996 KB |
Output is correct |
42 |
Correct |
13 ms |
17340 KB |
Output is correct |
43 |
Correct |
12 ms |
16980 KB |
Output is correct |
44 |
Correct |
13 ms |
17148 KB |
Output is correct |
45 |
Correct |
12 ms |
17236 KB |
Output is correct |
46 |
Correct |
18 ms |
17452 KB |
Output is correct |
47 |
Correct |
13 ms |
17328 KB |
Output is correct |
48 |
Correct |
16 ms |
17380 KB |
Output is correct |
49 |
Correct |
14 ms |
17392 KB |
Output is correct |
50 |
Correct |
16 ms |
17364 KB |
Output is correct |
51 |
Correct |
12 ms |
17364 KB |
Output is correct |
52 |
Correct |
14 ms |
17364 KB |
Output is correct |
53 |
Correct |
11 ms |
17364 KB |
Output is correct |
54 |
Correct |
12 ms |
17416 KB |
Output is correct |
55 |
Correct |
13 ms |
17364 KB |
Output is correct |
56 |
Correct |
12 ms |
17400 KB |
Output is correct |
57 |
Correct |
15 ms |
17364 KB |
Output is correct |
58 |
Correct |
11 ms |
17456 KB |
Output is correct |
59 |
Correct |
13 ms |
17364 KB |
Output is correct |
60 |
Correct |
12 ms |
17376 KB |
Output is correct |
61 |
Correct |
12 ms |
17384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
153 ms |
25076 KB |
Output is correct |
2 |
Correct |
185 ms |
25060 KB |
Output is correct |
3 |
Correct |
304 ms |
25068 KB |
Output is correct |
4 |
Correct |
581 ms |
41096 KB |
Output is correct |
5 |
Correct |
474 ms |
43960 KB |
Output is correct |
6 |
Correct |
644 ms |
43848 KB |
Output is correct |
7 |
Correct |
264 ms |
43704 KB |
Output is correct |
8 |
Correct |
257 ms |
43828 KB |
Output is correct |
9 |
Correct |
225 ms |
43888 KB |
Output is correct |
10 |
Correct |
225 ms |
43840 KB |
Output is correct |
11 |
Correct |
359 ms |
43892 KB |
Output is correct |
12 |
Correct |
415 ms |
43884 KB |
Output is correct |
13 |
Correct |
442 ms |
43844 KB |
Output is correct |
14 |
Correct |
612 ms |
43856 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
153 ms |
25028 KB |
Output is correct |
2 |
Correct |
255 ms |
27864 KB |
Output is correct |
3 |
Correct |
291 ms |
28236 KB |
Output is correct |
4 |
Correct |
647 ms |
46744 KB |
Output is correct |
5 |
Correct |
537 ms |
46760 KB |
Output is correct |
6 |
Correct |
583 ms |
46752 KB |
Output is correct |
7 |
Correct |
245 ms |
46684 KB |
Output is correct |
8 |
Correct |
256 ms |
46808 KB |
Output is correct |
9 |
Correct |
243 ms |
46552 KB |
Output is correct |
10 |
Correct |
360 ms |
46672 KB |
Output is correct |
11 |
Correct |
532 ms |
46752 KB |
Output is correct |
12 |
Correct |
404 ms |
46692 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
9 ms |
16700 KB |
Output is correct |
2 |
Correct |
8 ms |
16724 KB |
Output is correct |
3 |
Correct |
8 ms |
16768 KB |
Output is correct |
4 |
Correct |
10 ms |
16724 KB |
Output is correct |
5 |
Correct |
8 ms |
16740 KB |
Output is correct |
6 |
Correct |
7 ms |
16724 KB |
Output is correct |
7 |
Correct |
7 ms |
16652 KB |
Output is correct |
8 |
Correct |
7 ms |
16724 KB |
Output is correct |
9 |
Correct |
7 ms |
16748 KB |
Output is correct |
10 |
Correct |
7 ms |
16724 KB |
Output is correct |
11 |
Correct |
9 ms |
16688 KB |
Output is correct |
12 |
Correct |
8 ms |
16724 KB |
Output is correct |
13 |
Correct |
8 ms |
16724 KB |
Output is correct |
14 |
Correct |
8 ms |
16724 KB |
Output is correct |
15 |
Correct |
7 ms |
16724 KB |
Output is correct |
16 |
Correct |
10 ms |
16724 KB |
Output is correct |
17 |
Correct |
8 ms |
16724 KB |
Output is correct |
18 |
Correct |
9 ms |
16724 KB |
Output is correct |
19 |
Correct |
10 ms |
16720 KB |
Output is correct |
20 |
Correct |
9 ms |
16724 KB |
Output is correct |
21 |
Correct |
8 ms |
16724 KB |
Output is correct |
22 |
Correct |
7 ms |
16664 KB |
Output is correct |
23 |
Correct |
7 ms |
16696 KB |
Output is correct |
24 |
Correct |
7 ms |
16768 KB |
Output is correct |
25 |
Correct |
7 ms |
16724 KB |
Output is correct |
26 |
Correct |
7 ms |
16724 KB |
Output is correct |
27 |
Correct |
10 ms |
16764 KB |
Output is correct |
28 |
Correct |
8 ms |
16724 KB |
Output is correct |
29 |
Correct |
7 ms |
16724 KB |
Output is correct |
30 |
Correct |
7 ms |
16724 KB |
Output is correct |
31 |
Correct |
8 ms |
16724 KB |
Output is correct |
32 |
Correct |
8 ms |
16724 KB |
Output is correct |
33 |
Correct |
8 ms |
16724 KB |
Output is correct |
34 |
Correct |
8 ms |
16724 KB |
Output is correct |
35 |
Correct |
8 ms |
16724 KB |
Output is correct |
36 |
Correct |
8 ms |
16800 KB |
Output is correct |
37 |
Correct |
8 ms |
16724 KB |
Output is correct |
38 |
Correct |
7 ms |
16724 KB |
Output is correct |
39 |
Correct |
7 ms |
16724 KB |
Output is correct |
40 |
Correct |
7 ms |
16724 KB |
Output is correct |
41 |
Correct |
14 ms |
16996 KB |
Output is correct |
42 |
Correct |
13 ms |
17340 KB |
Output is correct |
43 |
Correct |
12 ms |
16980 KB |
Output is correct |
44 |
Correct |
13 ms |
17148 KB |
Output is correct |
45 |
Correct |
12 ms |
17236 KB |
Output is correct |
46 |
Correct |
18 ms |
17452 KB |
Output is correct |
47 |
Correct |
13 ms |
17328 KB |
Output is correct |
48 |
Correct |
16 ms |
17380 KB |
Output is correct |
49 |
Correct |
14 ms |
17392 KB |
Output is correct |
50 |
Correct |
16 ms |
17364 KB |
Output is correct |
51 |
Correct |
12 ms |
17364 KB |
Output is correct |
52 |
Correct |
14 ms |
17364 KB |
Output is correct |
53 |
Correct |
11 ms |
17364 KB |
Output is correct |
54 |
Correct |
12 ms |
17416 KB |
Output is correct |
55 |
Correct |
13 ms |
17364 KB |
Output is correct |
56 |
Correct |
12 ms |
17400 KB |
Output is correct |
57 |
Correct |
15 ms |
17364 KB |
Output is correct |
58 |
Correct |
11 ms |
17456 KB |
Output is correct |
59 |
Correct |
13 ms |
17364 KB |
Output is correct |
60 |
Correct |
12 ms |
17376 KB |
Output is correct |
61 |
Correct |
12 ms |
17384 KB |
Output is correct |
62 |
Correct |
153 ms |
25076 KB |
Output is correct |
63 |
Correct |
185 ms |
25060 KB |
Output is correct |
64 |
Correct |
304 ms |
25068 KB |
Output is correct |
65 |
Correct |
581 ms |
41096 KB |
Output is correct |
66 |
Correct |
474 ms |
43960 KB |
Output is correct |
67 |
Correct |
644 ms |
43848 KB |
Output is correct |
68 |
Correct |
264 ms |
43704 KB |
Output is correct |
69 |
Correct |
257 ms |
43828 KB |
Output is correct |
70 |
Correct |
225 ms |
43888 KB |
Output is correct |
71 |
Correct |
225 ms |
43840 KB |
Output is correct |
72 |
Correct |
359 ms |
43892 KB |
Output is correct |
73 |
Correct |
415 ms |
43884 KB |
Output is correct |
74 |
Correct |
442 ms |
43844 KB |
Output is correct |
75 |
Correct |
612 ms |
43856 KB |
Output is correct |
76 |
Correct |
153 ms |
25028 KB |
Output is correct |
77 |
Correct |
255 ms |
27864 KB |
Output is correct |
78 |
Correct |
291 ms |
28236 KB |
Output is correct |
79 |
Correct |
647 ms |
46744 KB |
Output is correct |
80 |
Correct |
537 ms |
46760 KB |
Output is correct |
81 |
Correct |
583 ms |
46752 KB |
Output is correct |
82 |
Correct |
245 ms |
46684 KB |
Output is correct |
83 |
Correct |
256 ms |
46808 KB |
Output is correct |
84 |
Correct |
243 ms |
46552 KB |
Output is correct |
85 |
Correct |
360 ms |
46672 KB |
Output is correct |
86 |
Correct |
532 ms |
46752 KB |
Output is correct |
87 |
Correct |
404 ms |
46692 KB |
Output is correct |
88 |
Correct |
360 ms |
28128 KB |
Output is correct |
89 |
Correct |
594 ms |
46032 KB |
Output is correct |
90 |
Correct |
382 ms |
30824 KB |
Output is correct |
91 |
Correct |
615 ms |
46816 KB |
Output is correct |
92 |
Correct |
214 ms |
27964 KB |
Output is correct |
93 |
Correct |
293 ms |
28348 KB |
Output is correct |
94 |
Correct |
526 ms |
41100 KB |
Output is correct |
95 |
Correct |
527 ms |
46748 KB |
Output is correct |
96 |
Correct |
545 ms |
46932 KB |
Output is correct |
97 |
Correct |
581 ms |
46744 KB |
Output is correct |
98 |
Correct |
597 ms |
46836 KB |
Output is correct |
99 |
Correct |
589 ms |
46724 KB |
Output is correct |
100 |
Correct |
574 ms |
46752 KB |
Output is correct |
101 |
Correct |
231 ms |
46680 KB |
Output is correct |
102 |
Correct |
248 ms |
46728 KB |
Output is correct |
103 |
Correct |
281 ms |
46780 KB |
Output is correct |
104 |
Correct |
310 ms |
46744 KB |
Output is correct |
105 |
Correct |
391 ms |
46692 KB |
Output is correct |
106 |
Correct |
333 ms |
46760 KB |
Output is correct |
107 |
Correct |
409 ms |
46780 KB |
Output is correct |
108 |
Correct |
561 ms |
46756 KB |
Output is correct |
109 |
Correct |
360 ms |
46744 KB |
Output is correct |
110 |
Correct |
520 ms |
46756 KB |
Output is correct |
111 |
Correct |
553 ms |
46740 KB |
Output is correct |
112 |
Correct |
384 ms |
46680 KB |
Output is correct |
113 |
Correct |
526 ms |
46756 KB |
Output is correct |
114 |
Correct |
527 ms |
46748 KB |
Output is correct |
115 |
Correct |
258 ms |
46712 KB |
Output is correct |
116 |
Correct |
254 ms |
46676 KB |
Output is correct |
117 |
Correct |
286 ms |
46780 KB |
Output is correct |
118 |
Correct |
265 ms |
46780 KB |
Output is correct |
119 |
Correct |
285 ms |
46944 KB |
Output is correct |
120 |
Correct |
261 ms |
46808 KB |
Output is correct |