#include <bits/stdc++.h>
// Author: Kazuki_Will_Win_VOI_8703
#define fi first
#define se second
#define pii pair<int, int>
#define ll long long
#define all(a) a.begin(), a.end()
using namespace std;
const int mn = 3e5 + 5, inf = 1e9;
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
int n, d, a[mn], pre[mn], suf[mn], dp[mn];
int bit[mn << 1], ss;
void push(int val){
ss = val;
}
void add(int u, int val){
while(u <= ss){
bit[u] = max(bit[u], val);
u += (u & -u);
}
}
int get(int u){
int res = 0;
while(u){
res = max(res, bit[u]);
u -= (u & -u);
}
return res;
}
void add1(int u, int val){
while(u <= ss){
bit[u] = min(bit[u], val);
u += (u & -u);
}
}
int get1(int u){
int res = 0;
while(u){
res = min(res, bit[u]);
u -= (u & -u);
}
return res;
}
// Nx: Trước khi đi đến a[i] thì luôn đi từ gần nhất nhỏ hơn nó và cách <= d
int par[mn], sz[mn], min_val[mn], min_pos[mn];
void init(){
for(int i = 1; i <= n; i++){
par[i] = i, sz[i] = 1, min_val[i] = i;
}
}
int find(int u){
if(u == par[u]) return u;
return par[u] = find(par[u]);
}
int get_val(int u){
return min_val[find(u)];
}
void join(int u, int v){
u = find(u), v = find(v);
if(u == v) return;
if(sz[u] < sz[v]) swap(u, v);
sz[u] += sz[v];
par[v] = u, min_val[u] = min(min_val[u], min_val[v]);
}
bool cmp(pii a, pii b){
if(a.fi == b.fi) return a.se > b.se;
return a.fi < b.fi;
}
int st[mn << 2];
void update(int id, int l, int r, int pos, int val){
if(l > pos || r < pos) return;
if(l == r){
st[id] = val;
return;
}
int mid = (l + r) >> 1;
update(id << 1, l, mid, pos, val);
update(id << 1 | 1, mid + 1, r, pos, val);
st[id] = max(st[id << 1], st[id << 1 | 1]);
}
int get(int id, int l, int r, int u, int v){
if(l > v || r < u) return 0;
if(l >= u && r <= v) return st[id];
int mid = (l + r) >> 1;
return max(get(id << 1, l, mid, u, v), get(id << 1 | 1, mid + 1, r, u, v));
}
void solve(){
cin >> n >> d;
vector <int> comp;
for(int i = 1; i <= n; i++){
cin >> a[i];
comp.push_back(a[i]);
}
sort(all(comp));
comp.erase(unique(all(comp)), comp.end());
for(int i = 1; i <= n; i++) a[i] = lower_bound(all(comp), a[i]) - comp.begin() + 1;
ss = comp.size();
for(int i = 1; i <= n; i++){
if(a[i] > 1) pre[i] = get(a[i] - 1);
if(pre[i] == 0 || i - pre[i] > d) pre[i] = i;
add(a[i], i);
}
fill(bit, bit + mn, inf);
for(int i = n; i >= 1; i--){
if(a[i] > 1) suf[i] = get1(a[i] - 1);
if(suf[i] == inf || suf[i] - i > d) suf[i] = i;
add1(a[i], i);
// cout << suf[i] << ' ';
}
// cout << '\n';
vector <pii> Megumi;
for(int i = 1; i <= n; i++) Megumi.push_back({a[i], i});
sort(all(Megumi), cmp);
init();
for(auto [val, pos] : Megumi){
join(pos, pre[pos]);
join(pos, suf[pos]);
min_pos[pos] = get_val(pos);
}
int ans = 0;
for(auto [val, pos] : Megumi){
dp[pos] = get(1, 1, n, min_pos[pos], pos) + 1;
update(1, 1, n, pos, dp[pos]);
ans = max(ans, dp[pos]);
}
cout << ans << '\n';
}
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int t = 1;
// cin >> t;
while(t--) solve();
}
# | 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... |