#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;
struct segtreeMin {
int t[4*MX];
void update(int v, int l, int r, int pos, 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]=min(t[v*2+0],t[v*2+1]);
}
int query(int v, int l, int r, int ql, int qr) {
if(qr<l||r<ql) return 1e9;
if(ql<=l&&qr>=r) return t[v];
int mid=(l+r)>>1;
return min(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]=1e9;
}
}
} tt;
int _N;
int getPos(int L, int R, int x) {
int l=L,r=R,res=L;
while(l<=r) {
int mid=(l+r)>>1;
if(tt.query(1,0,_N-1,mid,R)<=x) {
res=mid;
l=mid+1;
} else {
r=mid-1;
}
}
return res;
}
bool valid[1000][1000];
int rev[MX];
int solveChallange(int N, int D, std::vector<int> H) {
_N=N;
st.reset();
tt.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;
}
for(int l=0;l<N;l++) tt.update(1,0,N-1,l,P[l]);
for(int l=N-1;l>=0;l--) {
// cari posisi terkanan sehingga min nya itu udah <= x
int p=getPos(l,min(N-1,l+D),P[l]);
R[l]=max(R[min(N-1,l+D)],R[p]);
}
for(int l=0;l<N;l++) {
int lst=l; // last yang <= H[l]
valid[l][l]=1;
for(int r=l+1;r<N;r++) {
if(r-lst<=D) valid[l][r]=valid[l][lst];
if(H[r]<=H[l]) lst=r;
}
for(int r=N-1;r>l;r--) {
if(valid[l][r]) {
R[l]=r;
break;
}
}
for(int r=l;r<=R[l];r++) {
assert(valid[l][r]);
}
}
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:155:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
155 | scanf("%d %d", &N, &D);
| ~~~~~^~~~~~~~~~~~~~~~~
Main.cpp:158:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
158 | scanf("%d", &elem);
| ~~~~~^~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
16728 KB |
Output is correct |
2 |
Correct |
4 ms |
16732 KB |
Output is correct |
3 |
Correct |
3 ms |
16848 KB |
Output is correct |
4 |
Correct |
6 ms |
16732 KB |
Output is correct |
5 |
Correct |
4 ms |
16732 KB |
Output is correct |
6 |
Correct |
3 ms |
16732 KB |
Output is correct |
7 |
Correct |
3 ms |
16732 KB |
Output is correct |
8 |
Correct |
5 ms |
16732 KB |
Output is correct |
9 |
Correct |
3 ms |
16732 KB |
Output is correct |
10 |
Correct |
3 ms |
16732 KB |
Output is correct |
11 |
Correct |
3 ms |
16732 KB |
Output is correct |
12 |
Correct |
3 ms |
16732 KB |
Output is correct |
13 |
Correct |
3 ms |
16728 KB |
Output is correct |
14 |
Correct |
4 ms |
16732 KB |
Output is correct |
15 |
Correct |
4 ms |
16732 KB |
Output is correct |
16 |
Correct |
3 ms |
16728 KB |
Output is correct |
17 |
Correct |
5 ms |
16732 KB |
Output is correct |
18 |
Correct |
4 ms |
17140 KB |
Output is correct |
19 |
Correct |
3 ms |
16732 KB |
Output is correct |
20 |
Correct |
4 ms |
16732 KB |
Output is correct |
21 |
Correct |
3 ms |
16728 KB |
Output is correct |
22 |
Correct |
4 ms |
16732 KB |
Output is correct |
23 |
Correct |
4 ms |
16732 KB |
Output is correct |
24 |
Correct |
3 ms |
16732 KB |
Output is correct |
25 |
Correct |
5 ms |
16732 KB |
Output is correct |
26 |
Correct |
4 ms |
16732 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
16728 KB |
Output is correct |
2 |
Correct |
4 ms |
16732 KB |
Output is correct |
3 |
Correct |
3 ms |
16848 KB |
Output is correct |
4 |
Correct |
6 ms |
16732 KB |
Output is correct |
5 |
Correct |
4 ms |
16732 KB |
Output is correct |
6 |
Correct |
3 ms |
16732 KB |
Output is correct |
7 |
Correct |
3 ms |
16732 KB |
Output is correct |
8 |
Correct |
5 ms |
16732 KB |
Output is correct |
9 |
Correct |
3 ms |
16732 KB |
Output is correct |
10 |
Correct |
3 ms |
16732 KB |
Output is correct |
11 |
Correct |
3 ms |
16732 KB |
Output is correct |
12 |
Correct |
3 ms |
16732 KB |
Output is correct |
13 |
Correct |
3 ms |
16728 KB |
Output is correct |
14 |
Correct |
4 ms |
16732 KB |
Output is correct |
15 |
Correct |
4 ms |
16732 KB |
Output is correct |
16 |
Correct |
3 ms |
16728 KB |
Output is correct |
17 |
Correct |
5 ms |
16732 KB |
Output is correct |
18 |
Correct |
4 ms |
17140 KB |
Output is correct |
19 |
Correct |
3 ms |
16732 KB |
Output is correct |
20 |
Correct |
4 ms |
16732 KB |
Output is correct |
21 |
Correct |
3 ms |
16728 KB |
Output is correct |
22 |
Correct |
4 ms |
16732 KB |
Output is correct |
23 |
Correct |
4 ms |
16732 KB |
Output is correct |
24 |
Correct |
3 ms |
16732 KB |
Output is correct |
25 |
Correct |
5 ms |
16732 KB |
Output is correct |
26 |
Correct |
4 ms |
16732 KB |
Output is correct |
27 |
Correct |
4 ms |
16732 KB |
Output is correct |
28 |
Correct |
4 ms |
16732 KB |
Output is correct |
29 |
Correct |
4 ms |
16732 KB |
Output is correct |
30 |
Correct |
4 ms |
16732 KB |
Output is correct |
31 |
Correct |
4 ms |
16928 KB |
Output is correct |
32 |
Correct |
4 ms |
16732 KB |
Output is correct |
33 |
Correct |
4 ms |
16732 KB |
Output is correct |
34 |
Correct |
4 ms |
16732 KB |
Output is correct |
35 |
Correct |
4 ms |
16728 KB |
Output is correct |
36 |
Correct |
4 ms |
16732 KB |
Output is correct |
37 |
Correct |
4 ms |
16728 KB |
Output is correct |
38 |
Correct |
3 ms |
16732 KB |
Output is correct |
39 |
Correct |
4 ms |
16728 KB |
Output is correct |
40 |
Correct |
4 ms |
16732 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
16728 KB |
Output is correct |
2 |
Correct |
4 ms |
16732 KB |
Output is correct |
3 |
Correct |
3 ms |
16848 KB |
Output is correct |
4 |
Correct |
6 ms |
16732 KB |
Output is correct |
5 |
Correct |
4 ms |
16732 KB |
Output is correct |
6 |
Correct |
3 ms |
16732 KB |
Output is correct |
7 |
Correct |
3 ms |
16732 KB |
Output is correct |
8 |
Correct |
5 ms |
16732 KB |
Output is correct |
9 |
Correct |
3 ms |
16732 KB |
Output is correct |
10 |
Correct |
3 ms |
16732 KB |
Output is correct |
11 |
Correct |
3 ms |
16732 KB |
Output is correct |
12 |
Correct |
3 ms |
16732 KB |
Output is correct |
13 |
Correct |
3 ms |
16728 KB |
Output is correct |
14 |
Correct |
4 ms |
16732 KB |
Output is correct |
15 |
Correct |
4 ms |
16732 KB |
Output is correct |
16 |
Correct |
3 ms |
16728 KB |
Output is correct |
17 |
Correct |
5 ms |
16732 KB |
Output is correct |
18 |
Correct |
4 ms |
17140 KB |
Output is correct |
19 |
Correct |
3 ms |
16732 KB |
Output is correct |
20 |
Correct |
4 ms |
16732 KB |
Output is correct |
21 |
Correct |
3 ms |
16728 KB |
Output is correct |
22 |
Correct |
4 ms |
16732 KB |
Output is correct |
23 |
Correct |
4 ms |
16732 KB |
Output is correct |
24 |
Correct |
3 ms |
16732 KB |
Output is correct |
25 |
Correct |
5 ms |
16732 KB |
Output is correct |
26 |
Correct |
4 ms |
16732 KB |
Output is correct |
27 |
Correct |
4 ms |
16732 KB |
Output is correct |
28 |
Correct |
4 ms |
16732 KB |
Output is correct |
29 |
Correct |
4 ms |
16732 KB |
Output is correct |
30 |
Correct |
4 ms |
16732 KB |
Output is correct |
31 |
Correct |
4 ms |
16928 KB |
Output is correct |
32 |
Correct |
4 ms |
16732 KB |
Output is correct |
33 |
Correct |
4 ms |
16732 KB |
Output is correct |
34 |
Correct |
4 ms |
16732 KB |
Output is correct |
35 |
Correct |
4 ms |
16728 KB |
Output is correct |
36 |
Correct |
4 ms |
16732 KB |
Output is correct |
37 |
Correct |
4 ms |
16728 KB |
Output is correct |
38 |
Correct |
3 ms |
16732 KB |
Output is correct |
39 |
Correct |
4 ms |
16728 KB |
Output is correct |
40 |
Correct |
4 ms |
16732 KB |
Output is correct |
41 |
Runtime error |
46 ms |
34292 KB |
Execution killed with signal 6 |
42 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
4054 ms |
28864 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
4093 ms |
28964 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
16728 KB |
Output is correct |
2 |
Correct |
4 ms |
16732 KB |
Output is correct |
3 |
Correct |
3 ms |
16848 KB |
Output is correct |
4 |
Correct |
6 ms |
16732 KB |
Output is correct |
5 |
Correct |
4 ms |
16732 KB |
Output is correct |
6 |
Correct |
3 ms |
16732 KB |
Output is correct |
7 |
Correct |
3 ms |
16732 KB |
Output is correct |
8 |
Correct |
5 ms |
16732 KB |
Output is correct |
9 |
Correct |
3 ms |
16732 KB |
Output is correct |
10 |
Correct |
3 ms |
16732 KB |
Output is correct |
11 |
Correct |
3 ms |
16732 KB |
Output is correct |
12 |
Correct |
3 ms |
16732 KB |
Output is correct |
13 |
Correct |
3 ms |
16728 KB |
Output is correct |
14 |
Correct |
4 ms |
16732 KB |
Output is correct |
15 |
Correct |
4 ms |
16732 KB |
Output is correct |
16 |
Correct |
3 ms |
16728 KB |
Output is correct |
17 |
Correct |
5 ms |
16732 KB |
Output is correct |
18 |
Correct |
4 ms |
17140 KB |
Output is correct |
19 |
Correct |
3 ms |
16732 KB |
Output is correct |
20 |
Correct |
4 ms |
16732 KB |
Output is correct |
21 |
Correct |
3 ms |
16728 KB |
Output is correct |
22 |
Correct |
4 ms |
16732 KB |
Output is correct |
23 |
Correct |
4 ms |
16732 KB |
Output is correct |
24 |
Correct |
3 ms |
16732 KB |
Output is correct |
25 |
Correct |
5 ms |
16732 KB |
Output is correct |
26 |
Correct |
4 ms |
16732 KB |
Output is correct |
27 |
Correct |
4 ms |
16732 KB |
Output is correct |
28 |
Correct |
4 ms |
16732 KB |
Output is correct |
29 |
Correct |
4 ms |
16732 KB |
Output is correct |
30 |
Correct |
4 ms |
16732 KB |
Output is correct |
31 |
Correct |
4 ms |
16928 KB |
Output is correct |
32 |
Correct |
4 ms |
16732 KB |
Output is correct |
33 |
Correct |
4 ms |
16732 KB |
Output is correct |
34 |
Correct |
4 ms |
16732 KB |
Output is correct |
35 |
Correct |
4 ms |
16728 KB |
Output is correct |
36 |
Correct |
4 ms |
16732 KB |
Output is correct |
37 |
Correct |
4 ms |
16728 KB |
Output is correct |
38 |
Correct |
3 ms |
16732 KB |
Output is correct |
39 |
Correct |
4 ms |
16728 KB |
Output is correct |
40 |
Correct |
4 ms |
16732 KB |
Output is correct |
41 |
Runtime error |
46 ms |
34292 KB |
Execution killed with signal 6 |
42 |
Halted |
0 ms |
0 KB |
- |