#include <bits/stdc++.h>
using namespace std;
#define sf scanf
#define pf printf
#define fi first
#define se second
#define pb push_back
#define INF 1023456789
#define all(x) x.begin(),x.end()
typedef pair<int,int> ii;
int n,d,p[300005],dp[300005],mn[300005],rt[300005];
deque<ii> dq;
vector<ii> v;
struct node{
int s,e,m,v;
node *l,*r;
node (int _s,int _e){
s=_s;e=_e;m=(s+e)/2;v=0;
if(s!=e)l=new node(s,m),r=new node(m+1,e);
}
void up(int x,int nv){
if(s==x&&e==x){ v=nv;return; }
if(x<=m)l->up(x,nv);
else r->up(x,nv);
v=max(l->v,r->v);
}
int qry(int x,int y){
if(s==x&&e==y)return v;
if(y<=m)return l->qry(x,y);
if(x>m)return r->qry(x,y);
return max(l->qry(x,m),r->qry(m+1,y));
}
}*root;
int main(){
sf("%d%d",&n,&d);
for(int i=0;i<n;++i){
sf("%d",&p[i]);
while(!dq.empty()&&dq.back().fi>=p[i])dq.pop_back();
dq.push_back(ii(p[i],i));
while(dq.front().se<=i-d)dq.pop_front();
if(i>=d-1)mn[i]=dq.front().fi;
else mn[i]=INF;
}
root=new node(0,n-1);
while(!dq.empty())dq.pop_back();
for(int i=n-1;i>=0;--i){
while(!dq.empty()&&dq.front().fi<mn[i])dq.pop_front();
dq.push_front(ii(mn[i],i));
//if this is i+d, binary search to find p[i-d]
if(i-d<0)break;
if(dq.empty())rt[i-d]=n-1;
else{
int lo=0,hi=dq.size()-1,mid,res=n-1;
while(lo<=hi){
mid=(lo+hi)/2;
if(dq[mid].fi<=p[i-d])lo=mid+1;
else{
res=dq[mid].se;hi=mid-1;
}
}
rt[i-d]=res;
}
}
/*
for(int i=0;i<n;++i)pf("%d ",mn[i]);
pf("\n");
for(int i=0;i<n;++i)pf("%d ",rt[i]);
pf("\n");
*/
for(int i=0;i<n;++i){
v.pb(ii(p[i],-i));
}
//sort in descending p[i]
sort(all(v),greater<ii>());
for(int j=0;j<n;++j){
int i=-v[j].se;
if(i+d>n-1){//can take anything after it
dp[i]=root->qry(i,n-1)+1;
root->up(i,dp[i]);
continue;
}
dp[i]=root->qry(i,rt[i])+1;
root->up(i,dp[i]);
}
int ans=0;
for(int i=0;i<n;++i){
ans=max(ans,dp[i]);
}
pf("%d\n",ans);
}
/*
7 1
100 600 600 200 300 500 500
*/
Compilation message
Main.cpp: In function 'int main()':
Main.cpp:39:4: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
39 | sf("%d%d",&n,&d);
| ^
Main.cpp:41:5: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
41 | sf("%d",&p[i]);
| ^
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
0 ms |
204 KB |
Output is correct |
3 |
Correct |
1 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 |
0 ms |
216 KB |
Output is correct |
7 |
Correct |
0 ms |
204 KB |
Output is correct |
8 |
Correct |
1 ms |
204 KB |
Output is correct |
9 |
Correct |
1 ms |
204 KB |
Output is correct |
10 |
Correct |
1 ms |
204 KB |
Output is correct |
11 |
Correct |
1 ms |
204 KB |
Output is correct |
12 |
Correct |
1 ms |
292 KB |
Output is correct |
13 |
Correct |
1 ms |
204 KB |
Output is correct |
14 |
Correct |
1 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 |
0 ms |
204 KB |
Output is correct |
22 |
Correct |
0 ms |
204 KB |
Output is correct |
23 |
Correct |
0 ms |
204 KB |
Output is correct |
24 |
Correct |
1 ms |
204 KB |
Output is correct |
25 |
Correct |
1 ms |
204 KB |
Output is correct |
26 |
Correct |
1 ms |
204 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
0 ms |
204 KB |
Output is correct |
3 |
Correct |
1 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 |
0 ms |
216 KB |
Output is correct |
7 |
Correct |
0 ms |
204 KB |
Output is correct |
8 |
Correct |
1 ms |
204 KB |
Output is correct |
9 |
Correct |
1 ms |
204 KB |
Output is correct |
10 |
Correct |
1 ms |
204 KB |
Output is correct |
11 |
Correct |
1 ms |
204 KB |
Output is correct |
12 |
Correct |
1 ms |
292 KB |
Output is correct |
13 |
Correct |
1 ms |
204 KB |
Output is correct |
14 |
Correct |
1 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 |
0 ms |
204 KB |
Output is correct |
22 |
Correct |
0 ms |
204 KB |
Output is correct |
23 |
Correct |
0 ms |
204 KB |
Output is correct |
24 |
Correct |
1 ms |
204 KB |
Output is correct |
25 |
Correct |
1 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 |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
0 ms |
204 KB |
Output is correct |
3 |
Correct |
1 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 |
0 ms |
216 KB |
Output is correct |
7 |
Correct |
0 ms |
204 KB |
Output is correct |
8 |
Correct |
1 ms |
204 KB |
Output is correct |
9 |
Correct |
1 ms |
204 KB |
Output is correct |
10 |
Correct |
1 ms |
204 KB |
Output is correct |
11 |
Correct |
1 ms |
204 KB |
Output is correct |
12 |
Correct |
1 ms |
292 KB |
Output is correct |
13 |
Correct |
1 ms |
204 KB |
Output is correct |
14 |
Correct |
1 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 |
0 ms |
204 KB |
Output is correct |
22 |
Correct |
0 ms |
204 KB |
Output is correct |
23 |
Correct |
0 ms |
204 KB |
Output is correct |
24 |
Correct |
1 ms |
204 KB |
Output is correct |
25 |
Correct |
1 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 |
5 ms |
1100 KB |
Output is correct |
42 |
Correct |
5 ms |
1100 KB |
Output is correct |
43 |
Correct |
5 ms |
1100 KB |
Output is correct |
44 |
Correct |
4 ms |
1100 KB |
Output is correct |
45 |
Correct |
5 ms |
1100 KB |
Output is correct |
46 |
Correct |
5 ms |
1100 KB |
Output is correct |
47 |
Correct |
5 ms |
1100 KB |
Output is correct |
48 |
Correct |
5 ms |
1100 KB |
Output is correct |
49 |
Correct |
5 ms |
1100 KB |
Output is correct |
50 |
Correct |
5 ms |
1220 KB |
Output is correct |
51 |
Correct |
4 ms |
1100 KB |
Output is correct |
52 |
Correct |
5 ms |
1100 KB |
Output is correct |
53 |
Correct |
4 ms |
1228 KB |
Output is correct |
54 |
Correct |
5 ms |
1228 KB |
Output is correct |
55 |
Correct |
5 ms |
1100 KB |
Output is correct |
56 |
Correct |
5 ms |
1100 KB |
Output is correct |
57 |
Correct |
5 ms |
1100 KB |
Output is correct |
58 |
Correct |
3 ms |
1152 KB |
Output is correct |
59 |
Correct |
3 ms |
1100 KB |
Output is correct |
60 |
Correct |
4 ms |
1100 KB |
Output is correct |
61 |
Correct |
6 ms |
1228 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
163 ms |
38708 KB |
Output is correct |
2 |
Correct |
210 ms |
36496 KB |
Output is correct |
3 |
Correct |
351 ms |
36212 KB |
Output is correct |
4 |
Correct |
346 ms |
36168 KB |
Output is correct |
5 |
Correct |
265 ms |
36156 KB |
Output is correct |
6 |
Correct |
337 ms |
36236 KB |
Output is correct |
7 |
Correct |
162 ms |
38484 KB |
Output is correct |
8 |
Correct |
153 ms |
36120 KB |
Output is correct |
9 |
Correct |
177 ms |
37776 KB |
Output is correct |
10 |
Correct |
153 ms |
36196 KB |
Output is correct |
11 |
Correct |
225 ms |
36132 KB |
Output is correct |
12 |
Correct |
243 ms |
36112 KB |
Output is correct |
13 |
Correct |
282 ms |
36148 KB |
Output is correct |
14 |
Correct |
336 ms |
36168 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
181 ms |
35028 KB |
Output is correct |
2 |
Correct |
272 ms |
34976 KB |
Output is correct |
3 |
Correct |
311 ms |
35004 KB |
Output is correct |
4 |
Correct |
321 ms |
34984 KB |
Output is correct |
5 |
Correct |
259 ms |
35040 KB |
Output is correct |
6 |
Correct |
302 ms |
35016 KB |
Output is correct |
7 |
Correct |
150 ms |
37392 KB |
Output is correct |
8 |
Correct |
140 ms |
35076 KB |
Output is correct |
9 |
Correct |
201 ms |
35020 KB |
Output is correct |
10 |
Correct |
211 ms |
34876 KB |
Output is correct |
11 |
Correct |
293 ms |
35000 KB |
Output is correct |
12 |
Correct |
210 ms |
34956 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
0 ms |
204 KB |
Output is correct |
3 |
Correct |
1 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 |
0 ms |
216 KB |
Output is correct |
7 |
Correct |
0 ms |
204 KB |
Output is correct |
8 |
Correct |
1 ms |
204 KB |
Output is correct |
9 |
Correct |
1 ms |
204 KB |
Output is correct |
10 |
Correct |
1 ms |
204 KB |
Output is correct |
11 |
Correct |
1 ms |
204 KB |
Output is correct |
12 |
Correct |
1 ms |
292 KB |
Output is correct |
13 |
Correct |
1 ms |
204 KB |
Output is correct |
14 |
Correct |
1 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 |
0 ms |
204 KB |
Output is correct |
22 |
Correct |
0 ms |
204 KB |
Output is correct |
23 |
Correct |
0 ms |
204 KB |
Output is correct |
24 |
Correct |
1 ms |
204 KB |
Output is correct |
25 |
Correct |
1 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 |
5 ms |
1100 KB |
Output is correct |
42 |
Correct |
5 ms |
1100 KB |
Output is correct |
43 |
Correct |
5 ms |
1100 KB |
Output is correct |
44 |
Correct |
4 ms |
1100 KB |
Output is correct |
45 |
Correct |
5 ms |
1100 KB |
Output is correct |
46 |
Correct |
5 ms |
1100 KB |
Output is correct |
47 |
Correct |
5 ms |
1100 KB |
Output is correct |
48 |
Correct |
5 ms |
1100 KB |
Output is correct |
49 |
Correct |
5 ms |
1100 KB |
Output is correct |
50 |
Correct |
5 ms |
1220 KB |
Output is correct |
51 |
Correct |
4 ms |
1100 KB |
Output is correct |
52 |
Correct |
5 ms |
1100 KB |
Output is correct |
53 |
Correct |
4 ms |
1228 KB |
Output is correct |
54 |
Correct |
5 ms |
1228 KB |
Output is correct |
55 |
Correct |
5 ms |
1100 KB |
Output is correct |
56 |
Correct |
5 ms |
1100 KB |
Output is correct |
57 |
Correct |
5 ms |
1100 KB |
Output is correct |
58 |
Correct |
3 ms |
1152 KB |
Output is correct |
59 |
Correct |
3 ms |
1100 KB |
Output is correct |
60 |
Correct |
4 ms |
1100 KB |
Output is correct |
61 |
Correct |
6 ms |
1228 KB |
Output is correct |
62 |
Correct |
163 ms |
38708 KB |
Output is correct |
63 |
Correct |
210 ms |
36496 KB |
Output is correct |
64 |
Correct |
351 ms |
36212 KB |
Output is correct |
65 |
Correct |
346 ms |
36168 KB |
Output is correct |
66 |
Correct |
265 ms |
36156 KB |
Output is correct |
67 |
Correct |
337 ms |
36236 KB |
Output is correct |
68 |
Correct |
162 ms |
38484 KB |
Output is correct |
69 |
Correct |
153 ms |
36120 KB |
Output is correct |
70 |
Correct |
177 ms |
37776 KB |
Output is correct |
71 |
Correct |
153 ms |
36196 KB |
Output is correct |
72 |
Correct |
225 ms |
36132 KB |
Output is correct |
73 |
Correct |
243 ms |
36112 KB |
Output is correct |
74 |
Correct |
282 ms |
36148 KB |
Output is correct |
75 |
Correct |
336 ms |
36168 KB |
Output is correct |
76 |
Correct |
181 ms |
35028 KB |
Output is correct |
77 |
Correct |
272 ms |
34976 KB |
Output is correct |
78 |
Correct |
311 ms |
35004 KB |
Output is correct |
79 |
Correct |
321 ms |
34984 KB |
Output is correct |
80 |
Correct |
259 ms |
35040 KB |
Output is correct |
81 |
Correct |
302 ms |
35016 KB |
Output is correct |
82 |
Correct |
150 ms |
37392 KB |
Output is correct |
83 |
Correct |
140 ms |
35076 KB |
Output is correct |
84 |
Correct |
201 ms |
35020 KB |
Output is correct |
85 |
Correct |
211 ms |
34876 KB |
Output is correct |
86 |
Correct |
293 ms |
35000 KB |
Output is correct |
87 |
Correct |
210 ms |
34956 KB |
Output is correct |
88 |
Correct |
383 ms |
36128 KB |
Output is correct |
89 |
Correct |
412 ms |
36300 KB |
Output is correct |
90 |
Correct |
375 ms |
36148 KB |
Output is correct |
91 |
Correct |
336 ms |
36248 KB |
Output is correct |
92 |
Correct |
277 ms |
38672 KB |
Output is correct |
93 |
Correct |
359 ms |
36992 KB |
Output is correct |
94 |
Correct |
326 ms |
36128 KB |
Output is correct |
95 |
Correct |
314 ms |
36148 KB |
Output is correct |
96 |
Correct |
338 ms |
36348 KB |
Output is correct |
97 |
Correct |
374 ms |
36240 KB |
Output is correct |
98 |
Correct |
337 ms |
36348 KB |
Output is correct |
99 |
Correct |
346 ms |
36148 KB |
Output is correct |
100 |
Correct |
337 ms |
36172 KB |
Output is correct |
101 |
Correct |
175 ms |
37588 KB |
Output is correct |
102 |
Correct |
198 ms |
37816 KB |
Output is correct |
103 |
Correct |
225 ms |
38132 KB |
Output is correct |
104 |
Correct |
248 ms |
38456 KB |
Output is correct |
105 |
Correct |
284 ms |
38420 KB |
Output is correct |
106 |
Correct |
207 ms |
36208 KB |
Output is correct |
107 |
Correct |
224 ms |
36144 KB |
Output is correct |
108 |
Correct |
304 ms |
36272 KB |
Output is correct |
109 |
Correct |
245 ms |
36280 KB |
Output is correct |
110 |
Correct |
353 ms |
36156 KB |
Output is correct |
111 |
Correct |
315 ms |
36148 KB |
Output is correct |
112 |
Correct |
217 ms |
36204 KB |
Output is correct |
113 |
Correct |
297 ms |
36268 KB |
Output is correct |
114 |
Correct |
317 ms |
36300 KB |
Output is correct |
115 |
Correct |
136 ms |
35012 KB |
Output is correct |
116 |
Correct |
136 ms |
35004 KB |
Output is correct |
117 |
Correct |
165 ms |
36684 KB |
Output is correct |
118 |
Correct |
195 ms |
36804 KB |
Output is correct |
119 |
Correct |
227 ms |
36172 KB |
Output is correct |
120 |
Correct |
239 ms |
38604 KB |
Output is correct |