#include<bits/stdc++.h>
using namespace std;
const int nmax=3e5+42,inf=1e9+42;
int n,d,inp[nmax];
int dp[nmax];
int tree[3][4*nmax];
int mem_mini[nmax];
void build(int id,int node,int l,int r)
{
if(l==r)
{
if(id==0)tree[id][node]=-inp[l];
else tree[id][node]=mem_mini[l];
return;
}
int av=(l+r)/2;
build(id,node*2,l,av);
build(id,node*2+1,av+1,r);
tree[id][node]=max(tree[id][node*2],tree[id][node*2+1]);
//cout<<id<<" "<<node<<" "<<l<<" "<<r<<" -> "<<tree[id][node]<<endl;
}
bool cmp(int a,int b)
{
if(inp[a]!=inp[b])return inp[a]<inp[b];
return a>b;
}
int query(int id,int node,int l,int r,int lq,int rq)
{
if(l==lq&&r==rq)return tree[id][node];
int av=(l+r)/2;
int ret=-inf;
if(lq<=av)ret=max(ret,query(id,node*2,l,av,lq,min(av,rq)));
if(av<rq)ret=max(ret,query(id,node*2+1,av+1,r,max(av+1,lq),rq));
return ret;
}
void update(int id,int node,int l,int r,int pos,int val)
{
if(l==r)
{
tree[id][node]=val;
return;
}
int av=(l+r)/2;
if(pos<=av)update(id,node*2,l,av,pos,val);
else update(id,node*2+1,av+1,r,pos,val);
tree[id][node]=max(tree[id][node*2],tree[id][node*2+1]);
}
bool can_jump(int l,int r)
{
int lq=l;
int rq=r-d;
//cout<<"can jump "<<l<<" "<<r<<" "<<lq<<" "<<rq<<endl;
if(lq>rq)return 1;
//cout<<"query: "<<query(1,1,1,n,lq,rq)<<endl;
//for(int p=lq;p<=rq;p++)cout<<query(1,1,1,n,p,p)<<" ";cout<<endl;
return query(1,1,1,n,lq,rq)<inp[r];
}
int main()
{
scanf("%i%i",&n,&d);
for(int i=1;i<=n;i++)scanf("%i",&inp[i]);
/*
mt19937 rng(34);
n=12;
d=3;
for(int i=1;i<=n;i++)inp[i]=rng()%n;
*/
//for(int i=1;i<=n;i++)cout<<inp[i]<<" ";cout<<endl;
build(0,1,1,n);
for(int i=1;i<=n-d+1;i++)
mem_mini[i]=-query(0,1,1,n,i,i+d-1);
//for(int i=1;i<=n-d+1;i++)cout<<mem_mini[i]<<" ";cout<<endl;
int SZ_mini=n-d+1;
build(1,1,1,n);
vector<int> order={};
for(int i=1;i<=n;i++)order.push_back(i);
sort(order.begin(),order.end(),cmp);
int outp=0;
for(auto i:order)
{
int ok=i,not_ok=0;
while(ok-not_ok>1)
{
int av=(ok+not_ok)/2;
if(can_jump(av,i))ok=av;
else not_ok=av;
}
dp[i]=query(2,1,1,n,ok,i)+1;
outp=max(outp,dp[i]);
update(2,1,1,n,i,dp[i]);
//cout<<i<<" -> "<<dp[i]<<" ok= "<<ok<<endl;
/*
int is=1;
int cnt=0;
int j;
for(j=i-1;j>=1&&cnt<d;j--)
{
if(inp[i]<=inp[j])cnt++;
else
{
cnt=0;
is=max(is,dp[j]+1);
}
}
cout<<"is= "<<is<<endl;
assert(is==dp[i]);
*/
//for(int j=1;j<=n;j++)cout<<query(2,1,1,n,j,j)<<" ";cout<<endl;
}
printf("%i\n",outp);
return 0;
}
Compilation message
Main.cpp: In function 'int main()':
Main.cpp:109:9: warning: unused variable 'SZ_mini' [-Wunused-variable]
109 | int SZ_mini=n-d+1;
| ^~~~~~~
Main.cpp:88:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
88 | scanf("%i%i",&n,&d);
| ~~~~~^~~~~~~~~~~~~~
Main.cpp:90:31: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
90 | for(int i=1;i<=n;i++)scanf("%i",&inp[i]);
| ~~~~~^~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
332 KB |
Output is correct |
2 |
Correct |
0 ms |
332 KB |
Output is correct |
3 |
Correct |
1 ms |
332 KB |
Output is correct |
4 |
Correct |
1 ms |
332 KB |
Output is correct |
5 |
Correct |
0 ms |
332 KB |
Output is correct |
6 |
Correct |
0 ms |
332 KB |
Output is correct |
7 |
Correct |
0 ms |
332 KB |
Output is correct |
8 |
Correct |
0 ms |
216 KB |
Output is correct |
9 |
Correct |
0 ms |
332 KB |
Output is correct |
10 |
Correct |
0 ms |
332 KB |
Output is correct |
11 |
Correct |
1 ms |
332 KB |
Output is correct |
12 |
Correct |
1 ms |
332 KB |
Output is correct |
13 |
Correct |
1 ms |
332 KB |
Output is correct |
14 |
Correct |
0 ms |
332 KB |
Output is correct |
15 |
Correct |
0 ms |
272 KB |
Output is correct |
16 |
Correct |
1 ms |
332 KB |
Output is correct |
17 |
Correct |
1 ms |
332 KB |
Output is correct |
18 |
Correct |
0 ms |
332 KB |
Output is correct |
19 |
Correct |
0 ms |
332 KB |
Output is correct |
20 |
Correct |
0 ms |
332 KB |
Output is correct |
21 |
Correct |
0 ms |
332 KB |
Output is correct |
22 |
Correct |
0 ms |
332 KB |
Output is correct |
23 |
Correct |
1 ms |
332 KB |
Output is correct |
24 |
Correct |
0 ms |
332 KB |
Output is correct |
25 |
Correct |
1 ms |
332 KB |
Output is correct |
26 |
Correct |
0 ms |
204 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
332 KB |
Output is correct |
2 |
Correct |
0 ms |
332 KB |
Output is correct |
3 |
Correct |
1 ms |
332 KB |
Output is correct |
4 |
Correct |
1 ms |
332 KB |
Output is correct |
5 |
Correct |
0 ms |
332 KB |
Output is correct |
6 |
Correct |
0 ms |
332 KB |
Output is correct |
7 |
Correct |
0 ms |
332 KB |
Output is correct |
8 |
Correct |
0 ms |
216 KB |
Output is correct |
9 |
Correct |
0 ms |
332 KB |
Output is correct |
10 |
Correct |
0 ms |
332 KB |
Output is correct |
11 |
Correct |
1 ms |
332 KB |
Output is correct |
12 |
Correct |
1 ms |
332 KB |
Output is correct |
13 |
Correct |
1 ms |
332 KB |
Output is correct |
14 |
Correct |
0 ms |
332 KB |
Output is correct |
15 |
Correct |
0 ms |
272 KB |
Output is correct |
16 |
Correct |
1 ms |
332 KB |
Output is correct |
17 |
Correct |
1 ms |
332 KB |
Output is correct |
18 |
Correct |
0 ms |
332 KB |
Output is correct |
19 |
Correct |
0 ms |
332 KB |
Output is correct |
20 |
Correct |
0 ms |
332 KB |
Output is correct |
21 |
Correct |
0 ms |
332 KB |
Output is correct |
22 |
Correct |
0 ms |
332 KB |
Output is correct |
23 |
Correct |
1 ms |
332 KB |
Output is correct |
24 |
Correct |
0 ms |
332 KB |
Output is correct |
25 |
Correct |
1 ms |
332 KB |
Output is correct |
26 |
Correct |
0 ms |
204 KB |
Output is correct |
27 |
Correct |
1 ms |
332 KB |
Output is correct |
28 |
Correct |
2 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 |
1 ms |
332 KB |
Output is correct |
2 |
Correct |
0 ms |
332 KB |
Output is correct |
3 |
Correct |
1 ms |
332 KB |
Output is correct |
4 |
Correct |
1 ms |
332 KB |
Output is correct |
5 |
Correct |
0 ms |
332 KB |
Output is correct |
6 |
Correct |
0 ms |
332 KB |
Output is correct |
7 |
Correct |
0 ms |
332 KB |
Output is correct |
8 |
Correct |
0 ms |
216 KB |
Output is correct |
9 |
Correct |
0 ms |
332 KB |
Output is correct |
10 |
Correct |
0 ms |
332 KB |
Output is correct |
11 |
Correct |
1 ms |
332 KB |
Output is correct |
12 |
Correct |
1 ms |
332 KB |
Output is correct |
13 |
Correct |
1 ms |
332 KB |
Output is correct |
14 |
Correct |
0 ms |
332 KB |
Output is correct |
15 |
Correct |
0 ms |
272 KB |
Output is correct |
16 |
Correct |
1 ms |
332 KB |
Output is correct |
17 |
Correct |
1 ms |
332 KB |
Output is correct |
18 |
Correct |
0 ms |
332 KB |
Output is correct |
19 |
Correct |
0 ms |
332 KB |
Output is correct |
20 |
Correct |
0 ms |
332 KB |
Output is correct |
21 |
Correct |
0 ms |
332 KB |
Output is correct |
22 |
Correct |
0 ms |
332 KB |
Output is correct |
23 |
Correct |
1 ms |
332 KB |
Output is correct |
24 |
Correct |
0 ms |
332 KB |
Output is correct |
25 |
Correct |
1 ms |
332 KB |
Output is correct |
26 |
Correct |
0 ms |
204 KB |
Output is correct |
27 |
Correct |
1 ms |
332 KB |
Output is correct |
28 |
Correct |
2 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 |
21 ms |
672 KB |
Output is correct |
42 |
Correct |
21 ms |
680 KB |
Output is correct |
43 |
Correct |
25 ms |
588 KB |
Output is correct |
44 |
Correct |
19 ms |
648 KB |
Output is correct |
45 |
Correct |
22 ms |
588 KB |
Output is correct |
46 |
Correct |
6 ms |
588 KB |
Output is correct |
47 |
Correct |
21 ms |
664 KB |
Output is correct |
48 |
Correct |
22 ms |
668 KB |
Output is correct |
49 |
Correct |
23 ms |
676 KB |
Output is correct |
50 |
Correct |
23 ms |
652 KB |
Output is correct |
51 |
Correct |
20 ms |
604 KB |
Output is correct |
52 |
Correct |
26 ms |
652 KB |
Output is correct |
53 |
Correct |
23 ms |
668 KB |
Output is correct |
54 |
Correct |
22 ms |
620 KB |
Output is correct |
55 |
Correct |
29 ms |
668 KB |
Output is correct |
56 |
Correct |
29 ms |
588 KB |
Output is correct |
57 |
Correct |
29 ms |
676 KB |
Output is correct |
58 |
Correct |
4 ms |
640 KB |
Output is correct |
59 |
Correct |
5 ms |
588 KB |
Output is correct |
60 |
Correct |
24 ms |
664 KB |
Output is correct |
61 |
Correct |
28 ms |
588 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1598 ms |
17324 KB |
Output is correct |
2 |
Correct |
1681 ms |
17512 KB |
Output is correct |
3 |
Correct |
1990 ms |
17316 KB |
Output is correct |
4 |
Correct |
2200 ms |
17480 KB |
Output is correct |
5 |
Correct |
1970 ms |
17432 KB |
Output is correct |
6 |
Correct |
2148 ms |
17368 KB |
Output is correct |
7 |
Correct |
1892 ms |
17400 KB |
Output is correct |
8 |
Correct |
1561 ms |
17404 KB |
Output is correct |
9 |
Correct |
1814 ms |
17364 KB |
Output is correct |
10 |
Correct |
1650 ms |
17432 KB |
Output is correct |
11 |
Correct |
1847 ms |
17420 KB |
Output is correct |
12 |
Correct |
1933 ms |
17332 KB |
Output is correct |
13 |
Correct |
2122 ms |
17484 KB |
Output is correct |
14 |
Correct |
2025 ms |
17332 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
208 ms |
16212 KB |
Output is correct |
2 |
Correct |
271 ms |
16176 KB |
Output is correct |
3 |
Correct |
278 ms |
16336 KB |
Output is correct |
4 |
Correct |
293 ms |
16196 KB |
Output is correct |
5 |
Correct |
291 ms |
16180 KB |
Output is correct |
6 |
Correct |
298 ms |
16176 KB |
Output is correct |
7 |
Correct |
204 ms |
16232 KB |
Output is correct |
8 |
Correct |
214 ms |
16248 KB |
Output is correct |
9 |
Correct |
211 ms |
16188 KB |
Output is correct |
10 |
Correct |
250 ms |
16168 KB |
Output is correct |
11 |
Correct |
295 ms |
16232 KB |
Output is correct |
12 |
Correct |
290 ms |
16156 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
332 KB |
Output is correct |
2 |
Correct |
0 ms |
332 KB |
Output is correct |
3 |
Correct |
1 ms |
332 KB |
Output is correct |
4 |
Correct |
1 ms |
332 KB |
Output is correct |
5 |
Correct |
0 ms |
332 KB |
Output is correct |
6 |
Correct |
0 ms |
332 KB |
Output is correct |
7 |
Correct |
0 ms |
332 KB |
Output is correct |
8 |
Correct |
0 ms |
216 KB |
Output is correct |
9 |
Correct |
0 ms |
332 KB |
Output is correct |
10 |
Correct |
0 ms |
332 KB |
Output is correct |
11 |
Correct |
1 ms |
332 KB |
Output is correct |
12 |
Correct |
1 ms |
332 KB |
Output is correct |
13 |
Correct |
1 ms |
332 KB |
Output is correct |
14 |
Correct |
0 ms |
332 KB |
Output is correct |
15 |
Correct |
0 ms |
272 KB |
Output is correct |
16 |
Correct |
1 ms |
332 KB |
Output is correct |
17 |
Correct |
1 ms |
332 KB |
Output is correct |
18 |
Correct |
0 ms |
332 KB |
Output is correct |
19 |
Correct |
0 ms |
332 KB |
Output is correct |
20 |
Correct |
0 ms |
332 KB |
Output is correct |
21 |
Correct |
0 ms |
332 KB |
Output is correct |
22 |
Correct |
0 ms |
332 KB |
Output is correct |
23 |
Correct |
1 ms |
332 KB |
Output is correct |
24 |
Correct |
0 ms |
332 KB |
Output is correct |
25 |
Correct |
1 ms |
332 KB |
Output is correct |
26 |
Correct |
0 ms |
204 KB |
Output is correct |
27 |
Correct |
1 ms |
332 KB |
Output is correct |
28 |
Correct |
2 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 |
21 ms |
672 KB |
Output is correct |
42 |
Correct |
21 ms |
680 KB |
Output is correct |
43 |
Correct |
25 ms |
588 KB |
Output is correct |
44 |
Correct |
19 ms |
648 KB |
Output is correct |
45 |
Correct |
22 ms |
588 KB |
Output is correct |
46 |
Correct |
6 ms |
588 KB |
Output is correct |
47 |
Correct |
21 ms |
664 KB |
Output is correct |
48 |
Correct |
22 ms |
668 KB |
Output is correct |
49 |
Correct |
23 ms |
676 KB |
Output is correct |
50 |
Correct |
23 ms |
652 KB |
Output is correct |
51 |
Correct |
20 ms |
604 KB |
Output is correct |
52 |
Correct |
26 ms |
652 KB |
Output is correct |
53 |
Correct |
23 ms |
668 KB |
Output is correct |
54 |
Correct |
22 ms |
620 KB |
Output is correct |
55 |
Correct |
29 ms |
668 KB |
Output is correct |
56 |
Correct |
29 ms |
588 KB |
Output is correct |
57 |
Correct |
29 ms |
676 KB |
Output is correct |
58 |
Correct |
4 ms |
640 KB |
Output is correct |
59 |
Correct |
5 ms |
588 KB |
Output is correct |
60 |
Correct |
24 ms |
664 KB |
Output is correct |
61 |
Correct |
28 ms |
588 KB |
Output is correct |
62 |
Correct |
1598 ms |
17324 KB |
Output is correct |
63 |
Correct |
1681 ms |
17512 KB |
Output is correct |
64 |
Correct |
1990 ms |
17316 KB |
Output is correct |
65 |
Correct |
2200 ms |
17480 KB |
Output is correct |
66 |
Correct |
1970 ms |
17432 KB |
Output is correct |
67 |
Correct |
2148 ms |
17368 KB |
Output is correct |
68 |
Correct |
1892 ms |
17400 KB |
Output is correct |
69 |
Correct |
1561 ms |
17404 KB |
Output is correct |
70 |
Correct |
1814 ms |
17364 KB |
Output is correct |
71 |
Correct |
1650 ms |
17432 KB |
Output is correct |
72 |
Correct |
1847 ms |
17420 KB |
Output is correct |
73 |
Correct |
1933 ms |
17332 KB |
Output is correct |
74 |
Correct |
2122 ms |
17484 KB |
Output is correct |
75 |
Correct |
2025 ms |
17332 KB |
Output is correct |
76 |
Correct |
208 ms |
16212 KB |
Output is correct |
77 |
Correct |
271 ms |
16176 KB |
Output is correct |
78 |
Correct |
278 ms |
16336 KB |
Output is correct |
79 |
Correct |
293 ms |
16196 KB |
Output is correct |
80 |
Correct |
291 ms |
16180 KB |
Output is correct |
81 |
Correct |
298 ms |
16176 KB |
Output is correct |
82 |
Correct |
204 ms |
16232 KB |
Output is correct |
83 |
Correct |
214 ms |
16248 KB |
Output is correct |
84 |
Correct |
211 ms |
16188 KB |
Output is correct |
85 |
Correct |
250 ms |
16168 KB |
Output is correct |
86 |
Correct |
295 ms |
16232 KB |
Output is correct |
87 |
Correct |
290 ms |
16156 KB |
Output is correct |
88 |
Correct |
2160 ms |
17516 KB |
Output is correct |
89 |
Correct |
2116 ms |
17412 KB |
Output is correct |
90 |
Correct |
2277 ms |
17440 KB |
Output is correct |
91 |
Correct |
2304 ms |
17408 KB |
Output is correct |
92 |
Correct |
2119 ms |
17432 KB |
Output is correct |
93 |
Correct |
2223 ms |
17380 KB |
Output is correct |
94 |
Correct |
813 ms |
16544 KB |
Output is correct |
95 |
Correct |
1990 ms |
17364 KB |
Output is correct |
96 |
Correct |
2184 ms |
17328 KB |
Output is correct |
97 |
Correct |
2244 ms |
17344 KB |
Output is correct |
98 |
Correct |
2237 ms |
17416 KB |
Output is correct |
99 |
Correct |
2287 ms |
17392 KB |
Output is correct |
100 |
Correct |
2312 ms |
17388 KB |
Output is correct |
101 |
Correct |
1787 ms |
17500 KB |
Output is correct |
102 |
Correct |
1949 ms |
17368 KB |
Output is correct |
103 |
Correct |
2028 ms |
17368 KB |
Output is correct |
104 |
Correct |
2070 ms |
17364 KB |
Output is correct |
105 |
Correct |
2094 ms |
17248 KB |
Output is correct |
106 |
Correct |
1898 ms |
17428 KB |
Output is correct |
107 |
Correct |
2228 ms |
17448 KB |
Output is correct |
108 |
Correct |
2301 ms |
17392 KB |
Output is correct |
109 |
Correct |
2044 ms |
17556 KB |
Output is correct |
110 |
Correct |
2205 ms |
17588 KB |
Output is correct |
111 |
Correct |
2273 ms |
17400 KB |
Output is correct |
112 |
Correct |
2033 ms |
17440 KB |
Output is correct |
113 |
Correct |
2269 ms |
17412 KB |
Output is correct |
114 |
Correct |
2348 ms |
17316 KB |
Output is correct |
115 |
Correct |
205 ms |
16220 KB |
Output is correct |
116 |
Correct |
207 ms |
16240 KB |
Output is correct |
117 |
Correct |
1040 ms |
16816 KB |
Output is correct |
118 |
Correct |
1050 ms |
16872 KB |
Output is correct |
119 |
Correct |
2137 ms |
17328 KB |
Output is correct |
120 |
Correct |
2161 ms |
17384 KB |
Output is correct |