#include <bits/stdc++.h>
using namespace std;
using ll = long long;
template<class T> bool cmin(T &i, T j) { return i > j ? i=j,true:false; }
template<class T> bool cmax(T &i, T j) { return i < j ? i=j,true:false; }
constexpr int nax = 300300;
int n,d;
int a[nax];
int b[nax];
int dp[nax];
int st[4*nax];
multiset<int> s[nax];
void upd(int p,int x,int u=1,int tl=0,int tr=nax) {
if (tl == tr) {
st[u] = x;
return;
}
int mid=(tl+tr)/2;
if (p <= mid) {
upd(p,x,2*u,tl,mid);
} else {
upd(p,x,2*u+1,mid+1,tr);
}
st[u] = max(st[2*u],st[2*u+1]);
}
int qry(int l,int r,int u=1,int tl=0,int tr=nax) {
if (l > r) { return 0; }
if (l == tl && r == tr) {
return st[u];
}
int mid=(tl+tr)/2;
return max(qry(l,min(r,mid),2*u,tl,mid),qry(max(mid+1,l),r,2*u+1,mid+1,tr));
}
int main() {
cin >> n >> d;
for (int i=0;i<n;i++) {
cin >> a[i];
b[i] = a[i];
}
sort(b,b+n);
for (int i=0;i<n;i++) {
a[i] = lower_bound(b,b+n,a[i])-b;
}
int mx = 0;
auto rmn = [&](int l,int r) {
int R = nax;
for (;l<=r;l++) {
cmin(R,a[l]);
}
return R;
};
for (int i=0;i<n;i++) {
if (i > d) {
int w = a[i-d-1];
if (rmn(i-d,i) > w) {
auto it = s[w].find(dp[i-d-1]);
assert(it!=s[w].end());
s[w].erase(it);
upd(w,(s[w].empty() ? 0 : *s[w].rbegin()));
// cout << "erased " << i-d-1 << endl;
} else {
// cout << "didnt erase " << i-d-1 << endl;
}
}
int w = a[i];
int c = qry(0,w-1)+1;
s[w].insert(c);
upd(w,*s[w].rbegin());
dp[i] = c;
cmax(mx,dp[i]);
// cout << c << endl;
}
cout << mx << endl;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
19036 KB |
Output is correct |
2 |
Correct |
4 ms |
19036 KB |
Output is correct |
3 |
Correct |
5 ms |
19036 KB |
Output is correct |
4 |
Correct |
4 ms |
19036 KB |
Output is correct |
5 |
Correct |
4 ms |
19036 KB |
Output is correct |
6 |
Correct |
5 ms |
16988 KB |
Output is correct |
7 |
Correct |
4 ms |
19036 KB |
Output is correct |
8 |
Correct |
4 ms |
19036 KB |
Output is correct |
9 |
Correct |
3 ms |
16988 KB |
Output is correct |
10 |
Correct |
4 ms |
16988 KB |
Output is correct |
11 |
Correct |
4 ms |
16992 KB |
Output is correct |
12 |
Correct |
4 ms |
19036 KB |
Output is correct |
13 |
Correct |
4 ms |
19036 KB |
Output is correct |
14 |
Correct |
4 ms |
19036 KB |
Output is correct |
15 |
Correct |
4 ms |
16988 KB |
Output is correct |
16 |
Correct |
4 ms |
17240 KB |
Output is correct |
17 |
Correct |
5 ms |
19036 KB |
Output is correct |
18 |
Correct |
4 ms |
16988 KB |
Output is correct |
19 |
Correct |
5 ms |
16988 KB |
Output is correct |
20 |
Correct |
4 ms |
16988 KB |
Output is correct |
21 |
Correct |
4 ms |
16988 KB |
Output is correct |
22 |
Correct |
4 ms |
16988 KB |
Output is correct |
23 |
Correct |
4 ms |
19036 KB |
Output is correct |
24 |
Correct |
4 ms |
19036 KB |
Output is correct |
25 |
Correct |
4 ms |
19036 KB |
Output is correct |
26 |
Correct |
4 ms |
19036 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
19036 KB |
Output is correct |
2 |
Correct |
4 ms |
19036 KB |
Output is correct |
3 |
Correct |
5 ms |
19036 KB |
Output is correct |
4 |
Correct |
4 ms |
19036 KB |
Output is correct |
5 |
Correct |
4 ms |
19036 KB |
Output is correct |
6 |
Correct |
5 ms |
16988 KB |
Output is correct |
7 |
Correct |
4 ms |
19036 KB |
Output is correct |
8 |
Correct |
4 ms |
19036 KB |
Output is correct |
9 |
Correct |
3 ms |
16988 KB |
Output is correct |
10 |
Correct |
4 ms |
16988 KB |
Output is correct |
11 |
Correct |
4 ms |
16992 KB |
Output is correct |
12 |
Correct |
4 ms |
19036 KB |
Output is correct |
13 |
Correct |
4 ms |
19036 KB |
Output is correct |
14 |
Correct |
4 ms |
19036 KB |
Output is correct |
15 |
Correct |
4 ms |
16988 KB |
Output is correct |
16 |
Correct |
4 ms |
17240 KB |
Output is correct |
17 |
Correct |
5 ms |
19036 KB |
Output is correct |
18 |
Correct |
4 ms |
16988 KB |
Output is correct |
19 |
Correct |
5 ms |
16988 KB |
Output is correct |
20 |
Correct |
4 ms |
16988 KB |
Output is correct |
21 |
Correct |
4 ms |
16988 KB |
Output is correct |
22 |
Correct |
4 ms |
16988 KB |
Output is correct |
23 |
Correct |
4 ms |
19036 KB |
Output is correct |
24 |
Correct |
4 ms |
19036 KB |
Output is correct |
25 |
Correct |
4 ms |
19036 KB |
Output is correct |
26 |
Correct |
4 ms |
19036 KB |
Output is correct |
27 |
Incorrect |
4 ms |
16984 KB |
Output isn't correct |
28 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
19036 KB |
Output is correct |
2 |
Correct |
4 ms |
19036 KB |
Output is correct |
3 |
Correct |
5 ms |
19036 KB |
Output is correct |
4 |
Correct |
4 ms |
19036 KB |
Output is correct |
5 |
Correct |
4 ms |
19036 KB |
Output is correct |
6 |
Correct |
5 ms |
16988 KB |
Output is correct |
7 |
Correct |
4 ms |
19036 KB |
Output is correct |
8 |
Correct |
4 ms |
19036 KB |
Output is correct |
9 |
Correct |
3 ms |
16988 KB |
Output is correct |
10 |
Correct |
4 ms |
16988 KB |
Output is correct |
11 |
Correct |
4 ms |
16992 KB |
Output is correct |
12 |
Correct |
4 ms |
19036 KB |
Output is correct |
13 |
Correct |
4 ms |
19036 KB |
Output is correct |
14 |
Correct |
4 ms |
19036 KB |
Output is correct |
15 |
Correct |
4 ms |
16988 KB |
Output is correct |
16 |
Correct |
4 ms |
17240 KB |
Output is correct |
17 |
Correct |
5 ms |
19036 KB |
Output is correct |
18 |
Correct |
4 ms |
16988 KB |
Output is correct |
19 |
Correct |
5 ms |
16988 KB |
Output is correct |
20 |
Correct |
4 ms |
16988 KB |
Output is correct |
21 |
Correct |
4 ms |
16988 KB |
Output is correct |
22 |
Correct |
4 ms |
16988 KB |
Output is correct |
23 |
Correct |
4 ms |
19036 KB |
Output is correct |
24 |
Correct |
4 ms |
19036 KB |
Output is correct |
25 |
Correct |
4 ms |
19036 KB |
Output is correct |
26 |
Correct |
4 ms |
19036 KB |
Output is correct |
27 |
Incorrect |
4 ms |
16984 KB |
Output isn't correct |
28 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
183 ms |
34736 KB |
Output is correct |
2 |
Correct |
213 ms |
29008 KB |
Output is correct |
3 |
Incorrect |
312 ms |
33876 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
190 ms |
34644 KB |
Output is correct |
2 |
Correct |
270 ms |
33328 KB |
Output is correct |
3 |
Correct |
330 ms |
35924 KB |
Output is correct |
4 |
Correct |
320 ms |
36176 KB |
Output is correct |
5 |
Correct |
290 ms |
36208 KB |
Output is correct |
6 |
Correct |
320 ms |
36180 KB |
Output is correct |
7 |
Correct |
194 ms |
36932 KB |
Output is correct |
8 |
Correct |
191 ms |
36736 KB |
Output is correct |
9 |
Correct |
204 ms |
36620 KB |
Output is correct |
10 |
Correct |
284 ms |
36980 KB |
Output is correct |
11 |
Correct |
317 ms |
36628 KB |
Output is correct |
12 |
Correct |
293 ms |
36164 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
19036 KB |
Output is correct |
2 |
Correct |
4 ms |
19036 KB |
Output is correct |
3 |
Correct |
5 ms |
19036 KB |
Output is correct |
4 |
Correct |
4 ms |
19036 KB |
Output is correct |
5 |
Correct |
4 ms |
19036 KB |
Output is correct |
6 |
Correct |
5 ms |
16988 KB |
Output is correct |
7 |
Correct |
4 ms |
19036 KB |
Output is correct |
8 |
Correct |
4 ms |
19036 KB |
Output is correct |
9 |
Correct |
3 ms |
16988 KB |
Output is correct |
10 |
Correct |
4 ms |
16988 KB |
Output is correct |
11 |
Correct |
4 ms |
16992 KB |
Output is correct |
12 |
Correct |
4 ms |
19036 KB |
Output is correct |
13 |
Correct |
4 ms |
19036 KB |
Output is correct |
14 |
Correct |
4 ms |
19036 KB |
Output is correct |
15 |
Correct |
4 ms |
16988 KB |
Output is correct |
16 |
Correct |
4 ms |
17240 KB |
Output is correct |
17 |
Correct |
5 ms |
19036 KB |
Output is correct |
18 |
Correct |
4 ms |
16988 KB |
Output is correct |
19 |
Correct |
5 ms |
16988 KB |
Output is correct |
20 |
Correct |
4 ms |
16988 KB |
Output is correct |
21 |
Correct |
4 ms |
16988 KB |
Output is correct |
22 |
Correct |
4 ms |
16988 KB |
Output is correct |
23 |
Correct |
4 ms |
19036 KB |
Output is correct |
24 |
Correct |
4 ms |
19036 KB |
Output is correct |
25 |
Correct |
4 ms |
19036 KB |
Output is correct |
26 |
Correct |
4 ms |
19036 KB |
Output is correct |
27 |
Incorrect |
4 ms |
16984 KB |
Output isn't correct |
28 |
Halted |
0 ms |
0 KB |
- |