#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct segTree{
int tree[1200002], lazy[1200002];
void init(int i, int l, int r){
tree[i] = 1, lazy[i] = 0;
if(l==r) return;
int m = (l+r)>>1;
init(i*2, l, m);
init(i*2+1, m+1, r);
}
void propagate(int i, int l, int r){
tree[i] = max(tree[i], lazy[i]);
if(l!=r){
lazy[i*2] = max(lazy[i*2], lazy[i]);
lazy[i*2+1] = max(lazy[i*2+1], lazy[i]);
}
lazy[i] = 0;
}
void update(int i, int l, int r, int s, int e, int val){
propagate(i, l, r);
if(r<s || e<l) return;
if(s<=l && r<=e){
lazy[i] = max(lazy[i], val);
propagate(i, l, r);
return;
}
int m = (l+r)>>1;
update(i*2, l, m, s, e, val);
update(i*2+1, m+1, r, s, e, val);
}
int query(int i, int l, int r, int idx){
propagate(i, l, r);
if(l==r) return tree[i];
int m = (l+r)>>1;
if(idx <= m) return query(i*2, l, m, idx);
return query(i*2+1, m+1, r, idx);
}
} tree;
struct segTree2{
struct Node{
int l, r, s, a;
Node(){}
Node(int l, int r, int s, int a): l(l), r(r), s(s), a(a){}
Node operator+(const Node &nxt)const{
return Node(max(l, s+nxt.l), max(r+nxt.s, nxt.r), max(s+nxt.s, -1000000000), max({a, nxt.a, r+nxt.l}));
}
} tree[1200002];
void init(int i, int l, int r){
if(l==r){
tree[i] = Node(1, 1, 1, 1);
return;
}
int m = (l+r)>>1;
init(i*2, l, m);
init(i*2+1, m+1, r);
tree[i] = tree[i*2] + tree[i*2+1];
}
void update(int i, int l, int r, int idx){
if(l==r){
tree[i] = Node(-1000000000, -1000000000, -1000000000, -1000000000);
return;
}
int m = (l+r)>>1;
if(idx <= m) update(i*2, l, m, idx);
else update(i*2+1, m+1, r, idx);
tree[i] = tree[i*2] + tree[i*2+1];
}
int rLim(int i, int l, int r, int x, int lim, Node &node){
if(l==r){
if((node+tree[i]).a <= lim){
node = node+tree[i];
return r;
}
node.a = lim+1;
return l-1;
}
int m = (l+r)>>1;
if(x > m) return rLim(i*2+1, m+1, r, x, lim, node);
if(x<=l && (node+tree[i]).a <= lim){
node = node+tree[i];
return r;
}
int ret = rLim(i*2, l, m, x, lim, node);
if(node.a <= lim) return rLim(i*2+1, m+1, r, x, lim, node);
return ret;
}
} tree2;
int n, k;
int arr[300002];
void input();
void operate();
int main(){
input();
operate();
}
void input(){
scanf("%d %d", &n, &k);
for(int i=1; i<=n; i++){
scanf("%d", &arr[i]);
}
}
void operate(){
vector<pair<int, int> > vec;
for(int i=1; i<=n; i++) vec.push_back(make_pair(arr[i], i));
sort(vec.begin(), vec.end(), [&](pair<int, int> x, pair<int, int> y){
if(x.first != y.first) return x.first < y.first;
return x.second > y.second;
});
tree.init(1, 1, n);
tree2.init(1, 1, n);
int ans = 0;
for(auto p: vec){
int x = p.second;
int val = tree.query(1, 1, n, x);
tree2.update(1, 1, n, x);
segTree2::Node node(0, 0, 0, 0);
int lim = tree2.rLim(1, 1, n, x, k-1, node);
tree.update(1, 1, n, x+1, lim+1, val+1);
ans = max(ans, val);
}
printf("%d", ans);
}
Compilation message
Main.cpp: In function 'void input()':
Main.cpp:115:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
115 | scanf("%d %d", &n, &k);
| ~~~~~^~~~~~~~~~~~~~~~~
Main.cpp:117:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
117 | scanf("%d", &arr[i]);
| ~~~~~^~~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
204 KB |
Output is correct |
2 |
Correct |
0 ms |
204 KB |
Output is correct |
3 |
Correct |
0 ms |
204 KB |
Output is correct |
4 |
Correct |
1 ms |
204 KB |
Output is correct |
5 |
Correct |
1 ms |
204 KB |
Output is correct |
6 |
Correct |
1 ms |
204 KB |
Output is correct |
7 |
Correct |
0 ms |
204 KB |
Output is correct |
8 |
Correct |
0 ms |
204 KB |
Output is correct |
9 |
Correct |
1 ms |
204 KB |
Output is correct |
10 |
Correct |
0 ms |
204 KB |
Output is correct |
11 |
Correct |
0 ms |
204 KB |
Output is correct |
12 |
Correct |
0 ms |
332 KB |
Output is correct |
13 |
Correct |
1 ms |
204 KB |
Output is correct |
14 |
Correct |
0 ms |
204 KB |
Output is correct |
15 |
Correct |
0 ms |
204 KB |
Output is correct |
16 |
Correct |
1 ms |
204 KB |
Output is correct |
17 |
Correct |
0 ms |
204 KB |
Output is correct |
18 |
Correct |
0 ms |
204 KB |
Output is correct |
19 |
Correct |
1 ms |
204 KB |
Output is correct |
20 |
Correct |
0 ms |
204 KB |
Output is correct |
21 |
Correct |
1 ms |
204 KB |
Output is correct |
22 |
Correct |
1 ms |
204 KB |
Output is correct |
23 |
Correct |
1 ms |
204 KB |
Output is correct |
24 |
Correct |
0 ms |
204 KB |
Output is correct |
25 |
Correct |
0 ms |
204 KB |
Output is correct |
26 |
Correct |
0 ms |
204 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
204 KB |
Output is correct |
2 |
Correct |
0 ms |
204 KB |
Output is correct |
3 |
Correct |
0 ms |
204 KB |
Output is correct |
4 |
Correct |
1 ms |
204 KB |
Output is correct |
5 |
Correct |
1 ms |
204 KB |
Output is correct |
6 |
Correct |
1 ms |
204 KB |
Output is correct |
7 |
Correct |
0 ms |
204 KB |
Output is correct |
8 |
Correct |
0 ms |
204 KB |
Output is correct |
9 |
Correct |
1 ms |
204 KB |
Output is correct |
10 |
Correct |
0 ms |
204 KB |
Output is correct |
11 |
Correct |
0 ms |
204 KB |
Output is correct |
12 |
Correct |
0 ms |
332 KB |
Output is correct |
13 |
Correct |
1 ms |
204 KB |
Output is correct |
14 |
Correct |
0 ms |
204 KB |
Output is correct |
15 |
Correct |
0 ms |
204 KB |
Output is correct |
16 |
Correct |
1 ms |
204 KB |
Output is correct |
17 |
Correct |
0 ms |
204 KB |
Output is correct |
18 |
Correct |
0 ms |
204 KB |
Output is correct |
19 |
Correct |
1 ms |
204 KB |
Output is correct |
20 |
Correct |
0 ms |
204 KB |
Output is correct |
21 |
Correct |
1 ms |
204 KB |
Output is correct |
22 |
Correct |
1 ms |
204 KB |
Output is correct |
23 |
Correct |
1 ms |
204 KB |
Output is correct |
24 |
Correct |
0 ms |
204 KB |
Output is correct |
25 |
Correct |
0 ms |
204 KB |
Output is correct |
26 |
Correct |
0 ms |
204 KB |
Output is correct |
27 |
Correct |
1 ms |
332 KB |
Output is correct |
28 |
Correct |
1 ms |
332 KB |
Output is correct |
29 |
Correct |
1 ms |
332 KB |
Output is correct |
30 |
Correct |
1 ms |
332 KB |
Output is correct |
31 |
Correct |
1 ms |
332 KB |
Output is correct |
32 |
Correct |
1 ms |
332 KB |
Output is correct |
33 |
Correct |
1 ms |
332 KB |
Output is correct |
34 |
Correct |
1 ms |
332 KB |
Output is correct |
35 |
Correct |
1 ms |
332 KB |
Output is correct |
36 |
Correct |
1 ms |
332 KB |
Output is correct |
37 |
Correct |
1 ms |
332 KB |
Output is correct |
38 |
Correct |
1 ms |
332 KB |
Output is correct |
39 |
Correct |
1 ms |
332 KB |
Output is correct |
40 |
Correct |
1 ms |
332 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
204 KB |
Output is correct |
2 |
Correct |
0 ms |
204 KB |
Output is correct |
3 |
Correct |
0 ms |
204 KB |
Output is correct |
4 |
Correct |
1 ms |
204 KB |
Output is correct |
5 |
Correct |
1 ms |
204 KB |
Output is correct |
6 |
Correct |
1 ms |
204 KB |
Output is correct |
7 |
Correct |
0 ms |
204 KB |
Output is correct |
8 |
Correct |
0 ms |
204 KB |
Output is correct |
9 |
Correct |
1 ms |
204 KB |
Output is correct |
10 |
Correct |
0 ms |
204 KB |
Output is correct |
11 |
Correct |
0 ms |
204 KB |
Output is correct |
12 |
Correct |
0 ms |
332 KB |
Output is correct |
13 |
Correct |
1 ms |
204 KB |
Output is correct |
14 |
Correct |
0 ms |
204 KB |
Output is correct |
15 |
Correct |
0 ms |
204 KB |
Output is correct |
16 |
Correct |
1 ms |
204 KB |
Output is correct |
17 |
Correct |
0 ms |
204 KB |
Output is correct |
18 |
Correct |
0 ms |
204 KB |
Output is correct |
19 |
Correct |
1 ms |
204 KB |
Output is correct |
20 |
Correct |
0 ms |
204 KB |
Output is correct |
21 |
Correct |
1 ms |
204 KB |
Output is correct |
22 |
Correct |
1 ms |
204 KB |
Output is correct |
23 |
Correct |
1 ms |
204 KB |
Output is correct |
24 |
Correct |
0 ms |
204 KB |
Output is correct |
25 |
Correct |
0 ms |
204 KB |
Output is correct |
26 |
Correct |
0 ms |
204 KB |
Output is correct |
27 |
Correct |
1 ms |
332 KB |
Output is correct |
28 |
Correct |
1 ms |
332 KB |
Output is correct |
29 |
Correct |
1 ms |
332 KB |
Output is correct |
30 |
Correct |
1 ms |
332 KB |
Output is correct |
31 |
Correct |
1 ms |
332 KB |
Output is correct |
32 |
Correct |
1 ms |
332 KB |
Output is correct |
33 |
Correct |
1 ms |
332 KB |
Output is correct |
34 |
Correct |
1 ms |
332 KB |
Output is correct |
35 |
Correct |
1 ms |
332 KB |
Output is correct |
36 |
Correct |
1 ms |
332 KB |
Output is correct |
37 |
Correct |
1 ms |
332 KB |
Output is correct |
38 |
Correct |
1 ms |
332 KB |
Output is correct |
39 |
Correct |
1 ms |
332 KB |
Output is correct |
40 |
Correct |
1 ms |
332 KB |
Output is correct |
41 |
Correct |
8 ms |
844 KB |
Output is correct |
42 |
Correct |
7 ms |
844 KB |
Output is correct |
43 |
Correct |
8 ms |
844 KB |
Output is correct |
44 |
Correct |
6 ms |
716 KB |
Output is correct |
45 |
Correct |
7 ms |
844 KB |
Output is correct |
46 |
Correct |
7 ms |
856 KB |
Output is correct |
47 |
Correct |
7 ms |
852 KB |
Output is correct |
48 |
Correct |
7 ms |
844 KB |
Output is correct |
49 |
Correct |
9 ms |
844 KB |
Output is correct |
50 |
Correct |
9 ms |
856 KB |
Output is correct |
51 |
Correct |
6 ms |
844 KB |
Output is correct |
52 |
Correct |
7 ms |
856 KB |
Output is correct |
53 |
Correct |
6 ms |
844 KB |
Output is correct |
54 |
Correct |
7 ms |
844 KB |
Output is correct |
55 |
Correct |
7 ms |
856 KB |
Output is correct |
56 |
Correct |
7 ms |
844 KB |
Output is correct |
57 |
Correct |
7 ms |
844 KB |
Output is correct |
58 |
Correct |
5 ms |
844 KB |
Output is correct |
59 |
Correct |
5 ms |
972 KB |
Output is correct |
60 |
Correct |
6 ms |
848 KB |
Output is correct |
61 |
Correct |
6 ms |
844 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
262 ms |
28524 KB |
Output is correct |
2 |
Correct |
319 ms |
28584 KB |
Output is correct |
3 |
Correct |
419 ms |
28580 KB |
Output is correct |
4 |
Correct |
472 ms |
28584 KB |
Output is correct |
5 |
Correct |
386 ms |
28448 KB |
Output is correct |
6 |
Correct |
478 ms |
28520 KB |
Output is correct |
7 |
Correct |
256 ms |
28536 KB |
Output is correct |
8 |
Correct |
263 ms |
28556 KB |
Output is correct |
9 |
Correct |
268 ms |
28532 KB |
Output is correct |
10 |
Correct |
273 ms |
28508 KB |
Output is correct |
11 |
Correct |
351 ms |
28452 KB |
Output is correct |
12 |
Correct |
370 ms |
28488 KB |
Output is correct |
13 |
Correct |
348 ms |
28520 KB |
Output is correct |
14 |
Correct |
518 ms |
28468 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
273 ms |
28524 KB |
Output is correct |
2 |
Correct |
381 ms |
28452 KB |
Output is correct |
3 |
Correct |
436 ms |
28560 KB |
Output is correct |
4 |
Correct |
435 ms |
28460 KB |
Output is correct |
5 |
Correct |
386 ms |
28576 KB |
Output is correct |
6 |
Correct |
431 ms |
28456 KB |
Output is correct |
7 |
Correct |
263 ms |
28512 KB |
Output is correct |
8 |
Correct |
263 ms |
28488 KB |
Output is correct |
9 |
Correct |
286 ms |
28584 KB |
Output is correct |
10 |
Correct |
364 ms |
28612 KB |
Output is correct |
11 |
Correct |
425 ms |
28452 KB |
Output is correct |
12 |
Correct |
363 ms |
28520 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
204 KB |
Output is correct |
2 |
Correct |
0 ms |
204 KB |
Output is correct |
3 |
Correct |
0 ms |
204 KB |
Output is correct |
4 |
Correct |
1 ms |
204 KB |
Output is correct |
5 |
Correct |
1 ms |
204 KB |
Output is correct |
6 |
Correct |
1 ms |
204 KB |
Output is correct |
7 |
Correct |
0 ms |
204 KB |
Output is correct |
8 |
Correct |
0 ms |
204 KB |
Output is correct |
9 |
Correct |
1 ms |
204 KB |
Output is correct |
10 |
Correct |
0 ms |
204 KB |
Output is correct |
11 |
Correct |
0 ms |
204 KB |
Output is correct |
12 |
Correct |
0 ms |
332 KB |
Output is correct |
13 |
Correct |
1 ms |
204 KB |
Output is correct |
14 |
Correct |
0 ms |
204 KB |
Output is correct |
15 |
Correct |
0 ms |
204 KB |
Output is correct |
16 |
Correct |
1 ms |
204 KB |
Output is correct |
17 |
Correct |
0 ms |
204 KB |
Output is correct |
18 |
Correct |
0 ms |
204 KB |
Output is correct |
19 |
Correct |
1 ms |
204 KB |
Output is correct |
20 |
Correct |
0 ms |
204 KB |
Output is correct |
21 |
Correct |
1 ms |
204 KB |
Output is correct |
22 |
Correct |
1 ms |
204 KB |
Output is correct |
23 |
Correct |
1 ms |
204 KB |
Output is correct |
24 |
Correct |
0 ms |
204 KB |
Output is correct |
25 |
Correct |
0 ms |
204 KB |
Output is correct |
26 |
Correct |
0 ms |
204 KB |
Output is correct |
27 |
Correct |
1 ms |
332 KB |
Output is correct |
28 |
Correct |
1 ms |
332 KB |
Output is correct |
29 |
Correct |
1 ms |
332 KB |
Output is correct |
30 |
Correct |
1 ms |
332 KB |
Output is correct |
31 |
Correct |
1 ms |
332 KB |
Output is correct |
32 |
Correct |
1 ms |
332 KB |
Output is correct |
33 |
Correct |
1 ms |
332 KB |
Output is correct |
34 |
Correct |
1 ms |
332 KB |
Output is correct |
35 |
Correct |
1 ms |
332 KB |
Output is correct |
36 |
Correct |
1 ms |
332 KB |
Output is correct |
37 |
Correct |
1 ms |
332 KB |
Output is correct |
38 |
Correct |
1 ms |
332 KB |
Output is correct |
39 |
Correct |
1 ms |
332 KB |
Output is correct |
40 |
Correct |
1 ms |
332 KB |
Output is correct |
41 |
Correct |
8 ms |
844 KB |
Output is correct |
42 |
Correct |
7 ms |
844 KB |
Output is correct |
43 |
Correct |
8 ms |
844 KB |
Output is correct |
44 |
Correct |
6 ms |
716 KB |
Output is correct |
45 |
Correct |
7 ms |
844 KB |
Output is correct |
46 |
Correct |
7 ms |
856 KB |
Output is correct |
47 |
Correct |
7 ms |
852 KB |
Output is correct |
48 |
Correct |
7 ms |
844 KB |
Output is correct |
49 |
Correct |
9 ms |
844 KB |
Output is correct |
50 |
Correct |
9 ms |
856 KB |
Output is correct |
51 |
Correct |
6 ms |
844 KB |
Output is correct |
52 |
Correct |
7 ms |
856 KB |
Output is correct |
53 |
Correct |
6 ms |
844 KB |
Output is correct |
54 |
Correct |
7 ms |
844 KB |
Output is correct |
55 |
Correct |
7 ms |
856 KB |
Output is correct |
56 |
Correct |
7 ms |
844 KB |
Output is correct |
57 |
Correct |
7 ms |
844 KB |
Output is correct |
58 |
Correct |
5 ms |
844 KB |
Output is correct |
59 |
Correct |
5 ms |
972 KB |
Output is correct |
60 |
Correct |
6 ms |
848 KB |
Output is correct |
61 |
Correct |
6 ms |
844 KB |
Output is correct |
62 |
Correct |
262 ms |
28524 KB |
Output is correct |
63 |
Correct |
319 ms |
28584 KB |
Output is correct |
64 |
Correct |
419 ms |
28580 KB |
Output is correct |
65 |
Correct |
472 ms |
28584 KB |
Output is correct |
66 |
Correct |
386 ms |
28448 KB |
Output is correct |
67 |
Correct |
478 ms |
28520 KB |
Output is correct |
68 |
Correct |
256 ms |
28536 KB |
Output is correct |
69 |
Correct |
263 ms |
28556 KB |
Output is correct |
70 |
Correct |
268 ms |
28532 KB |
Output is correct |
71 |
Correct |
273 ms |
28508 KB |
Output is correct |
72 |
Correct |
351 ms |
28452 KB |
Output is correct |
73 |
Correct |
370 ms |
28488 KB |
Output is correct |
74 |
Correct |
348 ms |
28520 KB |
Output is correct |
75 |
Correct |
518 ms |
28468 KB |
Output is correct |
76 |
Correct |
273 ms |
28524 KB |
Output is correct |
77 |
Correct |
381 ms |
28452 KB |
Output is correct |
78 |
Correct |
436 ms |
28560 KB |
Output is correct |
79 |
Correct |
435 ms |
28460 KB |
Output is correct |
80 |
Correct |
386 ms |
28576 KB |
Output is correct |
81 |
Correct |
431 ms |
28456 KB |
Output is correct |
82 |
Correct |
263 ms |
28512 KB |
Output is correct |
83 |
Correct |
263 ms |
28488 KB |
Output is correct |
84 |
Correct |
286 ms |
28584 KB |
Output is correct |
85 |
Correct |
364 ms |
28612 KB |
Output is correct |
86 |
Correct |
425 ms |
28452 KB |
Output is correct |
87 |
Correct |
363 ms |
28520 KB |
Output is correct |
88 |
Correct |
484 ms |
28456 KB |
Output is correct |
89 |
Correct |
509 ms |
28520 KB |
Output is correct |
90 |
Correct |
505 ms |
28524 KB |
Output is correct |
91 |
Correct |
446 ms |
28456 KB |
Output is correct |
92 |
Correct |
368 ms |
28520 KB |
Output is correct |
93 |
Correct |
463 ms |
28520 KB |
Output is correct |
94 |
Correct |
437 ms |
28548 KB |
Output is correct |
95 |
Correct |
449 ms |
28472 KB |
Output is correct |
96 |
Correct |
482 ms |
28520 KB |
Output is correct |
97 |
Correct |
569 ms |
28460 KB |
Output is correct |
98 |
Correct |
457 ms |
28572 KB |
Output is correct |
99 |
Correct |
434 ms |
28516 KB |
Output is correct |
100 |
Correct |
437 ms |
28484 KB |
Output is correct |
101 |
Correct |
281 ms |
28496 KB |
Output is correct |
102 |
Correct |
338 ms |
28568 KB |
Output is correct |
103 |
Correct |
382 ms |
28452 KB |
Output is correct |
104 |
Correct |
434 ms |
28488 KB |
Output is correct |
105 |
Correct |
468 ms |
28456 KB |
Output is correct |
106 |
Correct |
333 ms |
28456 KB |
Output is correct |
107 |
Correct |
355 ms |
28616 KB |
Output is correct |
108 |
Correct |
408 ms |
28544 KB |
Output is correct |
109 |
Correct |
381 ms |
28476 KB |
Output is correct |
110 |
Correct |
478 ms |
28500 KB |
Output is correct |
111 |
Correct |
432 ms |
28628 KB |
Output is correct |
112 |
Correct |
348 ms |
28456 KB |
Output is correct |
113 |
Correct |
411 ms |
28580 KB |
Output is correct |
114 |
Correct |
435 ms |
28472 KB |
Output is correct |
115 |
Correct |
267 ms |
28584 KB |
Output is correct |
116 |
Correct |
268 ms |
28540 KB |
Output is correct |
117 |
Correct |
300 ms |
28456 KB |
Output is correct |
118 |
Correct |
298 ms |
28516 KB |
Output is correct |
119 |
Correct |
365 ms |
28516 KB |
Output is correct |
120 |
Correct |
360 ms |
28500 KB |
Output is correct |