/* Author : Mychecksdead */
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define MOD (1000000000+7)
#define MOD1 (998244353)
#define pb push_back
#define all(x) x.begin(), x.end()
#define en cout << '\n'
#define ff first
#define ss second
#define pii pair<int,int>
#define vi vector<int>
const int N = 2e6+100, M = 1e5+10, K = 52, MX = 30;
int n, d, a[N], T[N], S[N];
void build(int l, int r, int k){
if(l == r){
T[k] = 0;
S[k] = MOD;
return;
}
int mid = l+r>>1;
build(l, mid, k<<1);
build(mid+1, r, k<<1|1);
T[k] = -MOD;
S[k] = MOD;
}
void upd(int l, int r, int p, int k, int val, int idx){
if(l == r){
if(val == 0) T[k] = val;
else T[k] = max(T[k], val);
S[k] = idx;
return;
}
int mid = l+r>>1;
if(p <= mid) upd(l, mid, p, k<<1, val, idx);
else upd(mid+1, r, p, k<<1|1, val, idx);
T[k] = max(T[k<<1], T[k<<1|1]);
S[k] = min(S[k<<1], S[k<<1|1]);
}
int get_min(int l, int r, int k, int lim){
if(l == r){
return l;
}
int mid = l+r>>1;
if(S[k<<1] < lim){
return get_min(l, mid, k<<1, lim);
}
return get_min(mid + 1, r, k<<1|1, lim);
}
int get(int l, int r, int ql, int qr, int k){
if(ql > r || l > qr) return 0;
if(ql <= l && r <= qr) return T[k];
int mid = l+r>>1;
return max(get(l, mid, ql, qr, k<<1), get(mid+1, r, ql, qr, k<<1|1));
}
void solve(){
cin >> n >> d;
vi val;
for(int i = 1; i <= n; ++i){
cin >> a[i];
val.pb(a[i]);
}
sort(all(val));
val.erase(unique(all(val)), val.end());
for(int i = 1; i <= n; ++i){
a[i] = lower_bound(all(val), a[i]) - val.begin() + 1;
}
build(1, n, 1);
for(int i = 1; i <= n; ++i){
int lim = i - d;
while(S[1] < lim){
int pos = get_min(1, n, 1, lim);
upd(1, n, pos, 1, 0, MOD);
}
int mx = max(1, get(1, n, 1, a[i] - 1, 1) + 1);
upd(1, n, a[i], 1, mx, i);
}
cout << T[1];
}
int main(){
cin.tie(0); ios::sync_with_stdio(0);
int tt = 1, aa;
// freopen("in.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
while(tt--){
solve();
en;
}
cerr<<"time taken : "<<(float)clock()/CLOCKS_PER_SEC<<" seconds\n";
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |