#include <bits/stdc++.h>
#define ll long long
#define vi vector<ll>
#define vvi vector<vi>
#define pp pair<ll, ll>
#define vp vector<pp>
#define inf 2000000000
using namespace std;
vi Itree;
void init(ll n){
while(n & (n - 1)) n++;
Itree.resize(2*n, 0);
}
void update(ll ind, ll val){
ind += Itree.size() / 2;
Itree[ind] = val;
while(ind > 1){
ind /= 2;
Itree[ind] = max(Itree[ind * 2], Itree[2*ind + 1]);
}
}
ll get2(ll u, ll l, ll r, ll a, ll b){
if(l == a && r == b){;
return Itree[u];
}
ll s = (a + b) / 2;
if(s >= r){
return get2(2*u, l, r, a, s);
}else if(s <= l){
return get2(2*u + 1, l, r, s, b);
}else{
return max(get2(2*u, l, s, a, s), get2(2*u + 1, s, r, s, b));
}
}
ll get(ll l, ll r){
return get2(1, l, r, 0, Itree.size() / 2);
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
ll n, d;
cin >> n >> d;
vi A(n, 0);
vp B(n);
vi pos(n), left(n);
for(int i = 0; i < n; i++){
cin >> A[i];
B[i] = {A[i], i};
}
sort(B.begin(), B.end());
init(n);
left[0] = -1;
for(int i = 0; i < n; i++){
pos[B[i].second] = i;
if(i > 0){
if(B[i].first > B[i - 1].first) left[i] = i;
else left[i] = left[i - 1];
}
}
multiset<ll> ms;
vi minD(n, inf);
for(int i = 0; i < d; i++){
ms.insert(A[i]);
}
for(int i = d; i <= n; i++){
minD[i - d] = *ms.begin();
ms.erase(ms.find(A[i - d]));
if(i < n) ms.insert(A[i]);
}
set<pp> active;
vi dp(n, 0);
ll ans = 0;
for(int i = 0; i < n; i++){
while(i > d && active.size() > 0 && (*active.begin()).first < minD[i - d]){
pp deact = *active.begin();
active.erase(active.begin());
update(pos[deact.second], 0);
}
ll x = 0;
if(left[pos[i]] != -1){
x = get(0, left[pos[i]]);
}
dp[i] = 1 + x;
update(pos[i], dp[i]);
if(i >= d) active.insert({A[i - d], i - d});
ans = max(ans, dp[i]);
}
cout << ans << '\n';
}
# | 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... |