#include <bits/stdc++.h>
using namespace std;
template<class T> struct Seg { // comb(ID,b) = b
const T ID = 0; T comb(T a, T b) { return max(a,b); }
int n; vector<T> seg;
void init(int _n) { n = _n; seg.assign(2*n,ID); }
void pull(int p) { seg[p] = comb(seg[2*p],seg[2*p+1]); }
void upd(int p, T val) { // set val at position p
seg[p += n] = val; for (p /= 2; p; p /= 2) pull(p); }
T query(int l, int r) { // min on interval [l, r]
if (l > r) return 0;
T ra = ID, rb = ID;
for (l += n, r += n+1; l < r; l /= 2, r /= 2) {
if (l&1) ra = comb(ra,seg[l++]);
if (r&1) rb = comb(seg[--r],rb);
}
return comb(ra,rb);
}
};
Seg<int> st;
int main() {
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
int n,k; cin >> n >> k;
st.init(n+1);
vector<int> A(n); for(auto &a : A) cin >> a;
vector<int> X; for(int i : A) X.push_back(i);
sort(begin(X),end(X));
X.erase(unique(begin(X),end(X)),end(X));
auto index = [&] (int x) {
return (int)(lower_bound(begin(X),end(X),x) - begin(X));
};
// find lds in reverse array to have lis starting at index i
vector<int> dp(n,0);
reverse(begin(A),end(A));
vector<int> lis;
for(int i = 0; i < n; i++) {
int pos = lower_bound(begin(lis),end(lis),-A[i]) - begin(lis);
dp[i] = pos+1;
if (pos == lis.size()) lis.push_back(-A[i]);
else lis[pos]=-A[i];
}
reverse(begin(A),end(A));
reverse(begin(dp),end(dp));
if (k == 0) {
cout << *max_element(begin(dp),end(dp)) << '\n';
return 0;
}
int ans = 0;
for(int i = 0; i < n; i++) {
// check if we can get longer sequence
ans = max(ans,dp[i] + st.query(index(A[i])+1,index(A[i] + k)));
st.upd(index(A[i]) + 1, st.query(1,index(A[i])) + 1);
}
cout << ans << '\n';
}
Compilation message
glo.cpp: In function 'int main()':
glo.cpp:44:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
44 | if (pos == lis.size()) lis.push_back(-A[i]);
| ~~~~^~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
204 KB |
Output is correct |
| 2 |
Correct |
0 ms |
312 KB |
Output is correct |
| 3 |
Correct |
1 ms |
204 KB |
Output is correct |
| 4 |
Correct |
1 ms |
316 KB |
Output is correct |
| 5 |
Correct |
1 ms |
204 KB |
Output is correct |
| 6 |
Correct |
1 ms |
204 KB |
Output is correct |
| 7 |
Correct |
1 ms |
204 KB |
Output is correct |
| 8 |
Correct |
1 ms |
204 KB |
Output is correct |
| 9 |
Correct |
1 ms |
308 KB |
Output is correct |
| 10 |
Correct |
1 ms |
312 KB |
Output is correct |
| 11 |
Correct |
0 ms |
308 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
204 KB |
Output is correct |
| 2 |
Correct |
0 ms |
312 KB |
Output is correct |
| 3 |
Correct |
1 ms |
204 KB |
Output is correct |
| 4 |
Correct |
1 ms |
316 KB |
Output is correct |
| 5 |
Correct |
1 ms |
204 KB |
Output is correct |
| 6 |
Correct |
1 ms |
204 KB |
Output is correct |
| 7 |
Correct |
1 ms |
204 KB |
Output is correct |
| 8 |
Correct |
1 ms |
204 KB |
Output is correct |
| 9 |
Correct |
1 ms |
308 KB |
Output is correct |
| 10 |
Correct |
1 ms |
312 KB |
Output is correct |
| 11 |
Correct |
0 ms |
308 KB |
Output is correct |
| 12 |
Correct |
1 ms |
204 KB |
Output is correct |
| 13 |
Correct |
0 ms |
204 KB |
Output is correct |
| 14 |
Correct |
0 ms |
204 KB |
Output is correct |
| 15 |
Correct |
1 ms |
204 KB |
Output is correct |
| 16 |
Correct |
0 ms |
204 KB |
Output is correct |
| 17 |
Correct |
0 ms |
204 KB |
Output is correct |
| 18 |
Correct |
0 ms |
204 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
204 KB |
Output is correct |
| 2 |
Correct |
0 ms |
312 KB |
Output is correct |
| 3 |
Correct |
1 ms |
204 KB |
Output is correct |
| 4 |
Correct |
1 ms |
316 KB |
Output is correct |
| 5 |
Correct |
1 ms |
204 KB |
Output is correct |
| 6 |
Correct |
1 ms |
204 KB |
Output is correct |
| 7 |
Correct |
1 ms |
204 KB |
Output is correct |
| 8 |
Correct |
1 ms |
204 KB |
Output is correct |
| 9 |
Correct |
1 ms |
308 KB |
Output is correct |
| 10 |
Correct |
1 ms |
312 KB |
Output is correct |
| 11 |
Correct |
0 ms |
308 KB |
Output is correct |
| 12 |
Correct |
1 ms |
204 KB |
Output is correct |
| 13 |
Correct |
0 ms |
204 KB |
Output is correct |
| 14 |
Correct |
0 ms |
204 KB |
Output is correct |
| 15 |
Correct |
1 ms |
204 KB |
Output is correct |
| 16 |
Correct |
0 ms |
204 KB |
Output is correct |
| 17 |
Correct |
0 ms |
204 KB |
Output is correct |
| 18 |
Correct |
0 ms |
204 KB |
Output is correct |
| 19 |
Correct |
1 ms |
332 KB |
Output is correct |
| 20 |
Correct |
1 ms |
332 KB |
Output is correct |
| 21 |
Correct |
1 ms |
332 KB |
Output is correct |
| 22 |
Correct |
1 ms |
324 KB |
Output is correct |
| 23 |
Correct |
1 ms |
332 KB |
Output is correct |
| 24 |
Correct |
1 ms |
332 KB |
Output is correct |
| 25 |
Correct |
2 ms |
332 KB |
Output is correct |
| 26 |
Correct |
1 ms |
332 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
55 ms |
4708 KB |
Output is correct |
| 2 |
Correct |
47 ms |
4492 KB |
Output is correct |
| 3 |
Correct |
44 ms |
4456 KB |
Output is correct |
| 4 |
Correct |
44 ms |
4444 KB |
Output is correct |
| 5 |
Correct |
29 ms |
5228 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
38 ms |
1616 KB |
Output is correct |
| 2 |
Correct |
38 ms |
1780 KB |
Output is correct |
| 3 |
Correct |
38 ms |
2020 KB |
Output is correct |
| 4 |
Correct |
16 ms |
1800 KB |
Output is correct |
| 5 |
Correct |
1 ms |
204 KB |
Output is correct |
| 6 |
Correct |
19 ms |
1712 KB |
Output is correct |
| 7 |
Correct |
29 ms |
1796 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
81 ms |
2784 KB |
Output is correct |
| 2 |
Correct |
79 ms |
2508 KB |
Output is correct |
| 3 |
Correct |
162 ms |
4480 KB |
Output is correct |
| 4 |
Correct |
76 ms |
5272 KB |
Output is correct |
| 5 |
Correct |
49 ms |
3300 KB |
Output is correct |
| 6 |
Correct |
78 ms |
6108 KB |
Output is correct |
| 7 |
Correct |
87 ms |
6700 KB |
Output is correct |
| 8 |
Correct |
62 ms |
3380 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
204 KB |
Output is correct |
| 2 |
Correct |
0 ms |
312 KB |
Output is correct |
| 3 |
Correct |
1 ms |
204 KB |
Output is correct |
| 4 |
Correct |
1 ms |
316 KB |
Output is correct |
| 5 |
Correct |
1 ms |
204 KB |
Output is correct |
| 6 |
Correct |
1 ms |
204 KB |
Output is correct |
| 7 |
Correct |
1 ms |
204 KB |
Output is correct |
| 8 |
Correct |
1 ms |
204 KB |
Output is correct |
| 9 |
Correct |
1 ms |
308 KB |
Output is correct |
| 10 |
Correct |
1 ms |
312 KB |
Output is correct |
| 11 |
Correct |
0 ms |
308 KB |
Output is correct |
| 12 |
Correct |
1 ms |
204 KB |
Output is correct |
| 13 |
Correct |
0 ms |
204 KB |
Output is correct |
| 14 |
Correct |
0 ms |
204 KB |
Output is correct |
| 15 |
Correct |
1 ms |
204 KB |
Output is correct |
| 16 |
Correct |
0 ms |
204 KB |
Output is correct |
| 17 |
Correct |
0 ms |
204 KB |
Output is correct |
| 18 |
Correct |
0 ms |
204 KB |
Output is correct |
| 19 |
Correct |
1 ms |
332 KB |
Output is correct |
| 20 |
Correct |
1 ms |
332 KB |
Output is correct |
| 21 |
Correct |
1 ms |
332 KB |
Output is correct |
| 22 |
Correct |
1 ms |
324 KB |
Output is correct |
| 23 |
Correct |
1 ms |
332 KB |
Output is correct |
| 24 |
Correct |
1 ms |
332 KB |
Output is correct |
| 25 |
Correct |
2 ms |
332 KB |
Output is correct |
| 26 |
Correct |
1 ms |
332 KB |
Output is correct |
| 27 |
Correct |
55 ms |
4708 KB |
Output is correct |
| 28 |
Correct |
47 ms |
4492 KB |
Output is correct |
| 29 |
Correct |
44 ms |
4456 KB |
Output is correct |
| 30 |
Correct |
44 ms |
4444 KB |
Output is correct |
| 31 |
Correct |
29 ms |
5228 KB |
Output is correct |
| 32 |
Correct |
38 ms |
1616 KB |
Output is correct |
| 33 |
Correct |
38 ms |
1780 KB |
Output is correct |
| 34 |
Correct |
38 ms |
2020 KB |
Output is correct |
| 35 |
Correct |
16 ms |
1800 KB |
Output is correct |
| 36 |
Correct |
1 ms |
204 KB |
Output is correct |
| 37 |
Correct |
19 ms |
1712 KB |
Output is correct |
| 38 |
Correct |
29 ms |
1796 KB |
Output is correct |
| 39 |
Correct |
81 ms |
2784 KB |
Output is correct |
| 40 |
Correct |
79 ms |
2508 KB |
Output is correct |
| 41 |
Correct |
162 ms |
4480 KB |
Output is correct |
| 42 |
Correct |
76 ms |
5272 KB |
Output is correct |
| 43 |
Correct |
49 ms |
3300 KB |
Output is correct |
| 44 |
Correct |
78 ms |
6108 KB |
Output is correct |
| 45 |
Correct |
87 ms |
6700 KB |
Output is correct |
| 46 |
Correct |
62 ms |
3380 KB |
Output is correct |
| 47 |
Correct |
80 ms |
3368 KB |
Output is correct |
| 48 |
Correct |
72 ms |
3364 KB |
Output is correct |
| 49 |
Correct |
163 ms |
6344 KB |
Output is correct |
| 50 |
Correct |
73 ms |
6216 KB |
Output is correct |
| 51 |
Correct |
70 ms |
4932 KB |
Output is correct |
| 52 |
Correct |
113 ms |
6404 KB |
Output is correct |
| 53 |
Correct |
82 ms |
6348 KB |
Output is correct |
| 54 |
Correct |
88 ms |
7100 KB |
Output is correct |
| 55 |
Correct |
130 ms |
6216 KB |
Output is correct |
