#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[1000002];
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]);
| ~~~~~^~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
204 KB |
Output is correct |
2 |
Correct |
1 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 |
0 ms |
204 KB |
Output is correct |
6 |
Correct |
1 ms |
204 KB |
Output is correct |
7 |
Correct |
1 ms |
204 KB |
Output is correct |
8 |
Correct |
0 ms |
204 KB |
Output is correct |
9 |
Correct |
0 ms |
204 KB |
Output is correct |
10 |
Correct |
1 ms |
204 KB |
Output is correct |
11 |
Correct |
0 ms |
204 KB |
Output is correct |
12 |
Correct |
1 ms |
204 KB |
Output is correct |
13 |
Correct |
0 ms |
204 KB |
Output is correct |
14 |
Correct |
0 ms |
204 KB |
Output is correct |
15 |
Correct |
1 ms |
204 KB |
Output is correct |
16 |
Correct |
1 ms |
204 KB |
Output is correct |
17 |
Correct |
1 ms |
204 KB |
Output is correct |
18 |
Correct |
1 ms |
204 KB |
Output is correct |
19 |
Correct |
1 ms |
204 KB |
Output is correct |
20 |
Correct |
1 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 |
1 ms |
204 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
204 KB |
Output is correct |
2 |
Correct |
1 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 |
0 ms |
204 KB |
Output is correct |
6 |
Correct |
1 ms |
204 KB |
Output is correct |
7 |
Correct |
1 ms |
204 KB |
Output is correct |
8 |
Correct |
0 ms |
204 KB |
Output is correct |
9 |
Correct |
0 ms |
204 KB |
Output is correct |
10 |
Correct |
1 ms |
204 KB |
Output is correct |
11 |
Correct |
0 ms |
204 KB |
Output is correct |
12 |
Correct |
1 ms |
204 KB |
Output is correct |
13 |
Correct |
0 ms |
204 KB |
Output is correct |
14 |
Correct |
0 ms |
204 KB |
Output is correct |
15 |
Correct |
1 ms |
204 KB |
Output is correct |
16 |
Correct |
1 ms |
204 KB |
Output is correct |
17 |
Correct |
1 ms |
204 KB |
Output is correct |
18 |
Correct |
1 ms |
204 KB |
Output is correct |
19 |
Correct |
1 ms |
204 KB |
Output is correct |
20 |
Correct |
1 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 |
1 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 |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
204 KB |
Output is correct |
2 |
Correct |
1 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 |
0 ms |
204 KB |
Output is correct |
6 |
Correct |
1 ms |
204 KB |
Output is correct |
7 |
Correct |
1 ms |
204 KB |
Output is correct |
8 |
Correct |
0 ms |
204 KB |
Output is correct |
9 |
Correct |
0 ms |
204 KB |
Output is correct |
10 |
Correct |
1 ms |
204 KB |
Output is correct |
11 |
Correct |
0 ms |
204 KB |
Output is correct |
12 |
Correct |
1 ms |
204 KB |
Output is correct |
13 |
Correct |
0 ms |
204 KB |
Output is correct |
14 |
Correct |
0 ms |
204 KB |
Output is correct |
15 |
Correct |
1 ms |
204 KB |
Output is correct |
16 |
Correct |
1 ms |
204 KB |
Output is correct |
17 |
Correct |
1 ms |
204 KB |
Output is correct |
18 |
Correct |
1 ms |
204 KB |
Output is correct |
19 |
Correct |
1 ms |
204 KB |
Output is correct |
20 |
Correct |
1 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 |
1 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 |
9 ms |
856 KB |
Output is correct |
42 |
Correct |
7 ms |
844 KB |
Output is correct |
43 |
Correct |
9 ms |
844 KB |
Output is correct |
44 |
Correct |
7 ms |
844 KB |
Output is correct |
45 |
Correct |
7 ms |
848 KB |
Output is correct |
46 |
Correct |
7 ms |
856 KB |
Output is correct |
47 |
Correct |
7 ms |
844 KB |
Output is correct |
48 |
Correct |
9 ms |
852 KB |
Output is correct |
49 |
Correct |
8 ms |
828 KB |
Output is correct |
50 |
Correct |
8 ms |
844 KB |
Output is correct |
51 |
Correct |
6 ms |
844 KB |
Output is correct |
52 |
Correct |
9 ms |
844 KB |
Output is correct |
53 |
Correct |
6 ms |
844 KB |
Output is correct |
54 |
Correct |
7 ms |
852 KB |
Output is correct |
55 |
Correct |
7 ms |
844 KB |
Output is correct |
56 |
Correct |
7 ms |
852 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 |
844 KB |
Output is correct |
60 |
Correct |
6 ms |
848 KB |
Output is correct |
61 |
Correct |
6 ms |
844 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
399 ms |
27756 KB |
Output is correct |
2 |
Correct |
363 ms |
27760 KB |
Output is correct |
3 |
Correct |
510 ms |
27700 KB |
Output is correct |
4 |
Incorrect |
498 ms |
27952 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
265 ms |
27816 KB |
Output is correct |
2 |
Correct |
397 ms |
27708 KB |
Output is correct |
3 |
Correct |
466 ms |
27752 KB |
Output is correct |
4 |
Correct |
437 ms |
27688 KB |
Output is correct |
5 |
Correct |
392 ms |
27752 KB |
Output is correct |
6 |
Correct |
463 ms |
27688 KB |
Output is correct |
7 |
Correct |
267 ms |
27688 KB |
Output is correct |
8 |
Correct |
282 ms |
27736 KB |
Output is correct |
9 |
Correct |
294 ms |
27732 KB |
Output is correct |
10 |
Correct |
339 ms |
27684 KB |
Output is correct |
11 |
Correct |
399 ms |
27688 KB |
Output is correct |
12 |
Correct |
379 ms |
27676 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
204 KB |
Output is correct |
2 |
Correct |
1 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 |
0 ms |
204 KB |
Output is correct |
6 |
Correct |
1 ms |
204 KB |
Output is correct |
7 |
Correct |
1 ms |
204 KB |
Output is correct |
8 |
Correct |
0 ms |
204 KB |
Output is correct |
9 |
Correct |
0 ms |
204 KB |
Output is correct |
10 |
Correct |
1 ms |
204 KB |
Output is correct |
11 |
Correct |
0 ms |
204 KB |
Output is correct |
12 |
Correct |
1 ms |
204 KB |
Output is correct |
13 |
Correct |
0 ms |
204 KB |
Output is correct |
14 |
Correct |
0 ms |
204 KB |
Output is correct |
15 |
Correct |
1 ms |
204 KB |
Output is correct |
16 |
Correct |
1 ms |
204 KB |
Output is correct |
17 |
Correct |
1 ms |
204 KB |
Output is correct |
18 |
Correct |
1 ms |
204 KB |
Output is correct |
19 |
Correct |
1 ms |
204 KB |
Output is correct |
20 |
Correct |
1 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 |
1 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 |
9 ms |
856 KB |
Output is correct |
42 |
Correct |
7 ms |
844 KB |
Output is correct |
43 |
Correct |
9 ms |
844 KB |
Output is correct |
44 |
Correct |
7 ms |
844 KB |
Output is correct |
45 |
Correct |
7 ms |
848 KB |
Output is correct |
46 |
Correct |
7 ms |
856 KB |
Output is correct |
47 |
Correct |
7 ms |
844 KB |
Output is correct |
48 |
Correct |
9 ms |
852 KB |
Output is correct |
49 |
Correct |
8 ms |
828 KB |
Output is correct |
50 |
Correct |
8 ms |
844 KB |
Output is correct |
51 |
Correct |
6 ms |
844 KB |
Output is correct |
52 |
Correct |
9 ms |
844 KB |
Output is correct |
53 |
Correct |
6 ms |
844 KB |
Output is correct |
54 |
Correct |
7 ms |
852 KB |
Output is correct |
55 |
Correct |
7 ms |
844 KB |
Output is correct |
56 |
Correct |
7 ms |
852 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 |
844 KB |
Output is correct |
60 |
Correct |
6 ms |
848 KB |
Output is correct |
61 |
Correct |
6 ms |
844 KB |
Output is correct |
62 |
Correct |
399 ms |
27756 KB |
Output is correct |
63 |
Correct |
363 ms |
27760 KB |
Output is correct |
64 |
Correct |
510 ms |
27700 KB |
Output is correct |
65 |
Incorrect |
498 ms |
27952 KB |
Output isn't correct |
66 |
Halted |
0 ms |
0 KB |
- |