#include <bits/stdc++.h>
using namespace std;
const int MX=3e5+5;
int dp[MX], R[MX];
struct segtree {
pair<int,int> t[4*MX];
void update(int v, int l, int r, int pos, pair<int,int> val) {
if(l>pos||r<pos) return;
if(l==r) {
t[v]=val;
return;
}
int mid=(l+r)>>1;
update(v*2+0,l,mid+0,pos,val);
update(v*2+1,mid+1,r,pos,val);
t[v]=max(t[v*2+0],t[v*2+1]);
}
pair<int,int> query(int v, int l, int r, int ql, int qr) {
if(qr<l||r<ql) return make_pair(-1,-1);
if(ql<=l&&qr>=r) return t[v];
int mid=(l+r)>>1;
return max(query(v*2+0,l,mid+0,ql,qr),
query(v*2+1,mid+1,r,ql,qr));
}
void reset() {
for(int i=0;i<4*MX;i++) {
t[i]=make_pair(-1,-1);
}
}
} st;
int rev[MX];
struct DSU {
int par[MX];
int find(int v) {
return par[v]==v?v:par[v]=find(par[v]);
}
bool merge(int u, int v) { // v itu yang lebih gede
u=find(u),v=find(v);
if(u==v) return 0;
par[u]=v;
return 1;
}
void prep() {
for(int i=0;i<MX;i++) par[i]=i;
}
} ds;
int solveChallange(int N, int D, std::vector<int> H) {
st.reset();
vector<pair<int,int>> ord;
vector<int> P(N);
for(int i=0;i<N;i++) {
ord.push_back({H[i],-i});
}
sort(ord.begin(),ord.end());
int cnt=1;
for(auto [h,id]:ord) {
id=-id;
P[id]=cnt++;
rev[P[id]]=id; // dapetin posisi dia
}
ds.prep();
set<int> pt;
for(int i=1;i<=N;i++) {
int p=rev[i];
auto it=pt.lower_bound(p);
if(it!=pt.end()&&(*it)-p<=D) ds.merge(p,*it);
if(it!=pt.begin()) {
it--;
if(p-(*it)<=D)
ds.merge(*it,p);
}
pt.insert(p);
R[p]=min(N-1,ds.find(p)+D);
}
for(int i=0;i<N;i++) {
while(true) {
auto [V,p]=st.query(1,1,N,1,P[i]-1);
if(p==-1) break;
if(R[p]<i) {
st.update(1,1,N,P[p],make_pair(-1,-1));
continue;
}
dp[i]=V+1;
break;
}
dp[i]=max(dp[i],1);
st.update(1,1,N,P[i],make_pair(dp[i],i));
}
return *max_element(dp,dp+N);
}
int main() {
int N, D;
std::vector<int> H;
scanf("%d %d", &N, &D);
H.resize(N);
for (auto &elem : H) {
scanf("%d", &elem);
}
int answer = solveChallange(N, D, H);
printf("%d\n", answer);
}
Compilation message
Main.cpp: In function 'int main()':
Main.cpp:114:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
114 | scanf("%d %d", &N, &D);
| ~~~~~^~~~~~~~~~~~~~~~~
Main.cpp:117:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
117 | scanf("%d", &elem);
| ~~~~~^~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
12892 KB |
Output is correct |
2 |
Correct |
3 ms |
12892 KB |
Output is correct |
3 |
Correct |
3 ms |
12892 KB |
Output is correct |
4 |
Correct |
3 ms |
12892 KB |
Output is correct |
5 |
Correct |
3 ms |
12892 KB |
Output is correct |
6 |
Correct |
3 ms |
13144 KB |
Output is correct |
7 |
Correct |
3 ms |
12892 KB |
Output is correct |
8 |
Correct |
3 ms |
12888 KB |
Output is correct |
9 |
Correct |
3 ms |
12892 KB |
Output is correct |
10 |
Correct |
3 ms |
12892 KB |
Output is correct |
11 |
Correct |
3 ms |
12888 KB |
Output is correct |
12 |
Correct |
3 ms |
12892 KB |
Output is correct |
13 |
Correct |
3 ms |
12892 KB |
Output is correct |
14 |
Correct |
3 ms |
12684 KB |
Output is correct |
15 |
Correct |
3 ms |
12748 KB |
Output is correct |
16 |
Correct |
3 ms |
12888 KB |
Output is correct |
17 |
Correct |
3 ms |
12844 KB |
Output is correct |
18 |
Correct |
3 ms |
12892 KB |
Output is correct |
19 |
Correct |
3 ms |
12892 KB |
Output is correct |
20 |
Correct |
3 ms |
12892 KB |
Output is correct |
21 |
Correct |
3 ms |
12888 KB |
Output is correct |
22 |
Correct |
3 ms |
12892 KB |
Output is correct |
23 |
Correct |
3 ms |
12892 KB |
Output is correct |
24 |
Correct |
3 ms |
12892 KB |
Output is correct |
25 |
Correct |
3 ms |
12892 KB |
Output is correct |
26 |
Correct |
3 ms |
12892 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
12892 KB |
Output is correct |
2 |
Correct |
3 ms |
12892 KB |
Output is correct |
3 |
Correct |
3 ms |
12892 KB |
Output is correct |
4 |
Correct |
3 ms |
12892 KB |
Output is correct |
5 |
Correct |
3 ms |
12892 KB |
Output is correct |
6 |
Correct |
3 ms |
13144 KB |
Output is correct |
7 |
Correct |
3 ms |
12892 KB |
Output is correct |
8 |
Correct |
3 ms |
12888 KB |
Output is correct |
9 |
Correct |
3 ms |
12892 KB |
Output is correct |
10 |
Correct |
3 ms |
12892 KB |
Output is correct |
11 |
Correct |
3 ms |
12888 KB |
Output is correct |
12 |
Correct |
3 ms |
12892 KB |
Output is correct |
13 |
Correct |
3 ms |
12892 KB |
Output is correct |
14 |
Correct |
3 ms |
12684 KB |
Output is correct |
15 |
Correct |
3 ms |
12748 KB |
Output is correct |
16 |
Correct |
3 ms |
12888 KB |
Output is correct |
17 |
Correct |
3 ms |
12844 KB |
Output is correct |
18 |
Correct |
3 ms |
12892 KB |
Output is correct |
19 |
Correct |
3 ms |
12892 KB |
Output is correct |
20 |
Correct |
3 ms |
12892 KB |
Output is correct |
21 |
Correct |
3 ms |
12888 KB |
Output is correct |
22 |
Correct |
3 ms |
12892 KB |
Output is correct |
23 |
Correct |
3 ms |
12892 KB |
Output is correct |
24 |
Correct |
3 ms |
12892 KB |
Output is correct |
25 |
Correct |
3 ms |
12892 KB |
Output is correct |
26 |
Correct |
3 ms |
12892 KB |
Output is correct |
27 |
Correct |
3 ms |
12892 KB |
Output is correct |
28 |
Correct |
3 ms |
12904 KB |
Output is correct |
29 |
Correct |
3 ms |
12892 KB |
Output is correct |
30 |
Correct |
3 ms |
12888 KB |
Output is correct |
31 |
Correct |
3 ms |
12892 KB |
Output is correct |
32 |
Correct |
3 ms |
12892 KB |
Output is correct |
33 |
Correct |
3 ms |
12892 KB |
Output is correct |
34 |
Correct |
3 ms |
12892 KB |
Output is correct |
35 |
Correct |
3 ms |
12784 KB |
Output is correct |
36 |
Correct |
3 ms |
12892 KB |
Output is correct |
37 |
Correct |
3 ms |
12892 KB |
Output is correct |
38 |
Correct |
3 ms |
12892 KB |
Output is correct |
39 |
Correct |
3 ms |
12888 KB |
Output is correct |
40 |
Correct |
3 ms |
12892 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
12892 KB |
Output is correct |
2 |
Correct |
3 ms |
12892 KB |
Output is correct |
3 |
Correct |
3 ms |
12892 KB |
Output is correct |
4 |
Correct |
3 ms |
12892 KB |
Output is correct |
5 |
Correct |
3 ms |
12892 KB |
Output is correct |
6 |
Correct |
3 ms |
13144 KB |
Output is correct |
7 |
Correct |
3 ms |
12892 KB |
Output is correct |
8 |
Correct |
3 ms |
12888 KB |
Output is correct |
9 |
Correct |
3 ms |
12892 KB |
Output is correct |
10 |
Correct |
3 ms |
12892 KB |
Output is correct |
11 |
Correct |
3 ms |
12888 KB |
Output is correct |
12 |
Correct |
3 ms |
12892 KB |
Output is correct |
13 |
Correct |
3 ms |
12892 KB |
Output is correct |
14 |
Correct |
3 ms |
12684 KB |
Output is correct |
15 |
Correct |
3 ms |
12748 KB |
Output is correct |
16 |
Correct |
3 ms |
12888 KB |
Output is correct |
17 |
Correct |
3 ms |
12844 KB |
Output is correct |
18 |
Correct |
3 ms |
12892 KB |
Output is correct |
19 |
Correct |
3 ms |
12892 KB |
Output is correct |
20 |
Correct |
3 ms |
12892 KB |
Output is correct |
21 |
Correct |
3 ms |
12888 KB |
Output is correct |
22 |
Correct |
3 ms |
12892 KB |
Output is correct |
23 |
Correct |
3 ms |
12892 KB |
Output is correct |
24 |
Correct |
3 ms |
12892 KB |
Output is correct |
25 |
Correct |
3 ms |
12892 KB |
Output is correct |
26 |
Correct |
3 ms |
12892 KB |
Output is correct |
27 |
Correct |
3 ms |
12892 KB |
Output is correct |
28 |
Correct |
3 ms |
12904 KB |
Output is correct |
29 |
Correct |
3 ms |
12892 KB |
Output is correct |
30 |
Correct |
3 ms |
12888 KB |
Output is correct |
31 |
Correct |
3 ms |
12892 KB |
Output is correct |
32 |
Correct |
3 ms |
12892 KB |
Output is correct |
33 |
Correct |
3 ms |
12892 KB |
Output is correct |
34 |
Correct |
3 ms |
12892 KB |
Output is correct |
35 |
Correct |
3 ms |
12784 KB |
Output is correct |
36 |
Correct |
3 ms |
12892 KB |
Output is correct |
37 |
Correct |
3 ms |
12892 KB |
Output is correct |
38 |
Correct |
3 ms |
12892 KB |
Output is correct |
39 |
Correct |
3 ms |
12888 KB |
Output is correct |
40 |
Correct |
3 ms |
12892 KB |
Output is correct |
41 |
Correct |
9 ms |
13148 KB |
Output is correct |
42 |
Correct |
9 ms |
13404 KB |
Output is correct |
43 |
Correct |
8 ms |
13252 KB |
Output is correct |
44 |
Correct |
7 ms |
13404 KB |
Output is correct |
45 |
Correct |
7 ms |
13508 KB |
Output is correct |
46 |
Correct |
7 ms |
13404 KB |
Output is correct |
47 |
Correct |
8 ms |
13216 KB |
Output is correct |
48 |
Correct |
8 ms |
13400 KB |
Output is correct |
49 |
Correct |
9 ms |
13404 KB |
Output is correct |
50 |
Correct |
8 ms |
13400 KB |
Output is correct |
51 |
Correct |
8 ms |
13404 KB |
Output is correct |
52 |
Correct |
9 ms |
13404 KB |
Output is correct |
53 |
Correct |
7 ms |
13436 KB |
Output is correct |
54 |
Correct |
8 ms |
13404 KB |
Output is correct |
55 |
Correct |
7 ms |
13272 KB |
Output is correct |
56 |
Correct |
7 ms |
13404 KB |
Output is correct |
57 |
Correct |
7 ms |
13280 KB |
Output is correct |
58 |
Correct |
6 ms |
13404 KB |
Output is correct |
59 |
Correct |
5 ms |
13404 KB |
Output is correct |
60 |
Correct |
6 ms |
13400 KB |
Output is correct |
61 |
Correct |
6 ms |
13404 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
188 ms |
34696 KB |
Output is correct |
2 |
Correct |
249 ms |
36032 KB |
Output is correct |
3 |
Correct |
330 ms |
35000 KB |
Output is correct |
4 |
Correct |
391 ms |
38388 KB |
Output is correct |
5 |
Correct |
350 ms |
38072 KB |
Output is correct |
6 |
Correct |
378 ms |
38332 KB |
Output is correct |
7 |
Correct |
167 ms |
37352 KB |
Output is correct |
8 |
Correct |
168 ms |
37208 KB |
Output is correct |
9 |
Correct |
214 ms |
39104 KB |
Output is correct |
10 |
Correct |
179 ms |
38148 KB |
Output is correct |
11 |
Correct |
331 ms |
37904 KB |
Output is correct |
12 |
Correct |
352 ms |
37592 KB |
Output is correct |
13 |
Correct |
348 ms |
37340 KB |
Output is correct |
14 |
Correct |
381 ms |
37396 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
173 ms |
35260 KB |
Output is correct |
2 |
Correct |
246 ms |
35584 KB |
Output is correct |
3 |
Correct |
338 ms |
34392 KB |
Output is correct |
4 |
Correct |
330 ms |
34260 KB |
Output is correct |
5 |
Correct |
269 ms |
35352 KB |
Output is correct |
6 |
Correct |
313 ms |
34432 KB |
Output is correct |
7 |
Correct |
171 ms |
34492 KB |
Output is correct |
8 |
Correct |
169 ms |
34668 KB |
Output is correct |
9 |
Correct |
171 ms |
34504 KB |
Output is correct |
10 |
Correct |
243 ms |
36032 KB |
Output is correct |
11 |
Correct |
305 ms |
35404 KB |
Output is correct |
12 |
Correct |
260 ms |
34504 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
12892 KB |
Output is correct |
2 |
Correct |
3 ms |
12892 KB |
Output is correct |
3 |
Correct |
3 ms |
12892 KB |
Output is correct |
4 |
Correct |
3 ms |
12892 KB |
Output is correct |
5 |
Correct |
3 ms |
12892 KB |
Output is correct |
6 |
Correct |
3 ms |
13144 KB |
Output is correct |
7 |
Correct |
3 ms |
12892 KB |
Output is correct |
8 |
Correct |
3 ms |
12888 KB |
Output is correct |
9 |
Correct |
3 ms |
12892 KB |
Output is correct |
10 |
Correct |
3 ms |
12892 KB |
Output is correct |
11 |
Correct |
3 ms |
12888 KB |
Output is correct |
12 |
Correct |
3 ms |
12892 KB |
Output is correct |
13 |
Correct |
3 ms |
12892 KB |
Output is correct |
14 |
Correct |
3 ms |
12684 KB |
Output is correct |
15 |
Correct |
3 ms |
12748 KB |
Output is correct |
16 |
Correct |
3 ms |
12888 KB |
Output is correct |
17 |
Correct |
3 ms |
12844 KB |
Output is correct |
18 |
Correct |
3 ms |
12892 KB |
Output is correct |
19 |
Correct |
3 ms |
12892 KB |
Output is correct |
20 |
Correct |
3 ms |
12892 KB |
Output is correct |
21 |
Correct |
3 ms |
12888 KB |
Output is correct |
22 |
Correct |
3 ms |
12892 KB |
Output is correct |
23 |
Correct |
3 ms |
12892 KB |
Output is correct |
24 |
Correct |
3 ms |
12892 KB |
Output is correct |
25 |
Correct |
3 ms |
12892 KB |
Output is correct |
26 |
Correct |
3 ms |
12892 KB |
Output is correct |
27 |
Correct |
3 ms |
12892 KB |
Output is correct |
28 |
Correct |
3 ms |
12904 KB |
Output is correct |
29 |
Correct |
3 ms |
12892 KB |
Output is correct |
30 |
Correct |
3 ms |
12888 KB |
Output is correct |
31 |
Correct |
3 ms |
12892 KB |
Output is correct |
32 |
Correct |
3 ms |
12892 KB |
Output is correct |
33 |
Correct |
3 ms |
12892 KB |
Output is correct |
34 |
Correct |
3 ms |
12892 KB |
Output is correct |
35 |
Correct |
3 ms |
12784 KB |
Output is correct |
36 |
Correct |
3 ms |
12892 KB |
Output is correct |
37 |
Correct |
3 ms |
12892 KB |
Output is correct |
38 |
Correct |
3 ms |
12892 KB |
Output is correct |
39 |
Correct |
3 ms |
12888 KB |
Output is correct |
40 |
Correct |
3 ms |
12892 KB |
Output is correct |
41 |
Correct |
9 ms |
13148 KB |
Output is correct |
42 |
Correct |
9 ms |
13404 KB |
Output is correct |
43 |
Correct |
8 ms |
13252 KB |
Output is correct |
44 |
Correct |
7 ms |
13404 KB |
Output is correct |
45 |
Correct |
7 ms |
13508 KB |
Output is correct |
46 |
Correct |
7 ms |
13404 KB |
Output is correct |
47 |
Correct |
8 ms |
13216 KB |
Output is correct |
48 |
Correct |
8 ms |
13400 KB |
Output is correct |
49 |
Correct |
9 ms |
13404 KB |
Output is correct |
50 |
Correct |
8 ms |
13400 KB |
Output is correct |
51 |
Correct |
8 ms |
13404 KB |
Output is correct |
52 |
Correct |
9 ms |
13404 KB |
Output is correct |
53 |
Correct |
7 ms |
13436 KB |
Output is correct |
54 |
Correct |
8 ms |
13404 KB |
Output is correct |
55 |
Correct |
7 ms |
13272 KB |
Output is correct |
56 |
Correct |
7 ms |
13404 KB |
Output is correct |
57 |
Correct |
7 ms |
13280 KB |
Output is correct |
58 |
Correct |
6 ms |
13404 KB |
Output is correct |
59 |
Correct |
5 ms |
13404 KB |
Output is correct |
60 |
Correct |
6 ms |
13400 KB |
Output is correct |
61 |
Correct |
6 ms |
13404 KB |
Output is correct |
62 |
Correct |
188 ms |
34696 KB |
Output is correct |
63 |
Correct |
249 ms |
36032 KB |
Output is correct |
64 |
Correct |
330 ms |
35000 KB |
Output is correct |
65 |
Correct |
391 ms |
38388 KB |
Output is correct |
66 |
Correct |
350 ms |
38072 KB |
Output is correct |
67 |
Correct |
378 ms |
38332 KB |
Output is correct |
68 |
Correct |
167 ms |
37352 KB |
Output is correct |
69 |
Correct |
168 ms |
37208 KB |
Output is correct |
70 |
Correct |
214 ms |
39104 KB |
Output is correct |
71 |
Correct |
179 ms |
38148 KB |
Output is correct |
72 |
Correct |
331 ms |
37904 KB |
Output is correct |
73 |
Correct |
352 ms |
37592 KB |
Output is correct |
74 |
Correct |
348 ms |
37340 KB |
Output is correct |
75 |
Correct |
381 ms |
37396 KB |
Output is correct |
76 |
Correct |
173 ms |
35260 KB |
Output is correct |
77 |
Correct |
246 ms |
35584 KB |
Output is correct |
78 |
Correct |
338 ms |
34392 KB |
Output is correct |
79 |
Correct |
330 ms |
34260 KB |
Output is correct |
80 |
Correct |
269 ms |
35352 KB |
Output is correct |
81 |
Correct |
313 ms |
34432 KB |
Output is correct |
82 |
Correct |
171 ms |
34492 KB |
Output is correct |
83 |
Correct |
169 ms |
34668 KB |
Output is correct |
84 |
Correct |
171 ms |
34504 KB |
Output is correct |
85 |
Correct |
243 ms |
36032 KB |
Output is correct |
86 |
Correct |
305 ms |
35404 KB |
Output is correct |
87 |
Correct |
260 ms |
34504 KB |
Output is correct |
88 |
Correct |
385 ms |
38344 KB |
Output is correct |
89 |
Correct |
399 ms |
38636 KB |
Output is correct |
90 |
Correct |
361 ms |
37440 KB |
Output is correct |
91 |
Correct |
321 ms |
39092 KB |
Output is correct |
92 |
Correct |
242 ms |
37732 KB |
Output is correct |
93 |
Correct |
283 ms |
38844 KB |
Output is correct |
94 |
Correct |
309 ms |
38452 KB |
Output is correct |
95 |
Correct |
355 ms |
37732 KB |
Output is correct |
96 |
Correct |
399 ms |
38636 KB |
Output is correct |
97 |
Correct |
371 ms |
37936 KB |
Output is correct |
98 |
Correct |
349 ms |
37788 KB |
Output is correct |
99 |
Correct |
322 ms |
37412 KB |
Output is correct |
100 |
Correct |
292 ms |
38064 KB |
Output is correct |
101 |
Correct |
229 ms |
38332 KB |
Output is correct |
102 |
Correct |
261 ms |
38688 KB |
Output is correct |
103 |
Correct |
267 ms |
37740 KB |
Output is correct |
104 |
Correct |
292 ms |
38240 KB |
Output is correct |
105 |
Correct |
256 ms |
37664 KB |
Output is correct |
106 |
Correct |
217 ms |
37440 KB |
Output is correct |
107 |
Correct |
279 ms |
38164 KB |
Output is correct |
108 |
Correct |
293 ms |
37556 KB |
Output is correct |
109 |
Correct |
287 ms |
38460 KB |
Output is correct |
110 |
Correct |
358 ms |
37820 KB |
Output is correct |
111 |
Correct |
344 ms |
38556 KB |
Output is correct |
112 |
Correct |
238 ms |
38348 KB |
Output is correct |
113 |
Correct |
346 ms |
38060 KB |
Output is correct |
114 |
Correct |
338 ms |
38728 KB |
Output is correct |
115 |
Correct |
168 ms |
38192 KB |
Output is correct |
116 |
Correct |
171 ms |
38332 KB |
Output is correct |
117 |
Correct |
221 ms |
37528 KB |
Output is correct |
118 |
Correct |
220 ms |
38240 KB |
Output is correct |
119 |
Correct |
206 ms |
37928 KB |
Output is correct |
120 |
Correct |
205 ms |
38328 KB |
Output is correct |