#include<bits/stdc++.h>
using namespace std;
#ifdef ONPC
#include"debug.h"
#else
#define debug(...) 42
#endif
#define endl '\n'
#define ll long long
#define pii pair<int,int>
#define F first
#define S second
#define pb push_back
#define sz(a) (int)a.size()
#define all(a) a.begin(),a.end()
template<class T> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }
const int mod = 1e9 + 7;
const int MAXN = 1e6 + 15;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
int dp[MAXN];
const int off = (1<<20);
struct sgt {
#define ls (idx<<1)
#define rs (idx<<1|1)
int t[off<<1];
int unit = 0;
void pull(int idx){
t[idx] = max(t[ls], t[rs]);
}
void update(int idx, int u){
t[idx+=off] = u;
while (idx/=2)
pull(idx);
}
int get(int l, int r, int idx=1, int lo=0, int hi=off){
if (r <= lo || hi <= l)
return unit;
if (l <= lo && hi <= r)
return t[idx];
int mi = (lo+hi)>>1;
return max(get(l, r, ls, lo, mi), get(l, r, rs, mi, hi));
}
} seg;
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
int n, d;
cin >> n >> d;
vector<int> a(n);
vector<int> deco(n);
for (int i = 0; i < n; i++){
cin >> a[i];
deco[i] = a[i];
}
sort(all(deco));
for (int i = 0; i < n; i++){
a[i] = lower_bound(all(deco), a[i]) - deco.begin() + 1;
}
deque<int> dq;
priority_queue<int, vector<int>, greater<int>> pq;
for (int i = 0; i < n; i++){
// delete what you need to delete
while (sz(dq) && a[dq.back()] >= a[i]) dq.pop_back();
dq.push_back(i);
if (i - dq.front() > d){
dq.pop_front();
}
for (int j = 0; j < a[dq.front()]; j++){
seg.update(j, 0);
}
dp[i] = seg.get(0, a[i]) + 1;
seg.update(a[i], dp[i]);
}
cout << *max_element(dp, dp + n);
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
6488 KB |
Output is correct |
| 2 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 3 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 4 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 5 |
Correct |
1 ms |
6612 KB |
Output is correct |
| 6 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 7 |
Correct |
1 ms |
6612 KB |
Output is correct |
| 8 |
Correct |
1 ms |
6488 KB |
Output is correct |
| 9 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 10 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 11 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 12 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 13 |
Correct |
2 ms |
6492 KB |
Output is correct |
| 14 |
Correct |
1 ms |
6620 KB |
Output is correct |
| 15 |
Incorrect |
1 ms |
6492 KB |
Output isn't correct |
| 16 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
6488 KB |
Output is correct |
| 2 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 3 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 4 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 5 |
Correct |
1 ms |
6612 KB |
Output is correct |
| 6 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 7 |
Correct |
1 ms |
6612 KB |
Output is correct |
| 8 |
Correct |
1 ms |
6488 KB |
Output is correct |
| 9 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 10 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 11 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 12 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 13 |
Correct |
2 ms |
6492 KB |
Output is correct |
| 14 |
Correct |
1 ms |
6620 KB |
Output is correct |
| 15 |
Incorrect |
1 ms |
6492 KB |
Output isn't correct |
| 16 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
6488 KB |
Output is correct |
| 2 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 3 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 4 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 5 |
Correct |
1 ms |
6612 KB |
Output is correct |
| 6 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 7 |
Correct |
1 ms |
6612 KB |
Output is correct |
| 8 |
Correct |
1 ms |
6488 KB |
Output is correct |
| 9 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 10 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 11 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 12 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 13 |
Correct |
2 ms |
6492 KB |
Output is correct |
| 14 |
Correct |
1 ms |
6620 KB |
Output is correct |
| 15 |
Incorrect |
1 ms |
6492 KB |
Output isn't correct |
| 16 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
95 ms |
13820 KB |
Output is correct |
| 2 |
Execution timed out |
4067 ms |
13560 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
98 ms |
14160 KB |
Output is correct |
| 2 |
Correct |
237 ms |
15952 KB |
Output is correct |
| 3 |
Correct |
213 ms |
14932 KB |
Output is correct |
| 4 |
Correct |
317 ms |
16060 KB |
Output is correct |
| 5 |
Correct |
435 ms |
16056 KB |
Output is correct |
| 6 |
Correct |
336 ms |
15952 KB |
Output is correct |
| 7 |
Correct |
101 ms |
17240 KB |
Output is correct |
| 8 |
Execution timed out |
4014 ms |
13940 KB |
Time limit exceeded |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
6488 KB |
Output is correct |
| 2 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 3 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 4 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 5 |
Correct |
1 ms |
6612 KB |
Output is correct |
| 6 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 7 |
Correct |
1 ms |
6612 KB |
Output is correct |
| 8 |
Correct |
1 ms |
6488 KB |
Output is correct |
| 9 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 10 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 11 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 12 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 13 |
Correct |
2 ms |
6492 KB |
Output is correct |
| 14 |
Correct |
1 ms |
6620 KB |
Output is correct |
| 15 |
Incorrect |
1 ms |
6492 KB |
Output isn't correct |
| 16 |
Halted |
0 ms |
0 KB |
- |
