#include <bits/stdc++.h> using namespace std; #define FOR(i, a, b) for(int i = a; i <= b; i++) #define FOD(i, a, b) for(int i = a; i >= b; i--) #define fi first #define se second #define ll long long #define db double #define ii pair<int,int> #define pb push_back #define MASK(i) (1LL << i) #define sq(i) (1LL * (i) * (i)) #define task "task" const ll INF = 1e18; const int inf = 1e9; const int N = 3e5 + 4; int n, d, nv; int a[N]; vector<int> val; deque<ii> dq[N]; void opti(ii &a, ii b) { if(a.fi < b.fi || (a.fi == b.fi && a.se > b.se)) a = b; } struct Smt { int mx[4 * N]; void init() { FOR(i, 1, 4 * nv) mx[i] = -1; } void upd(int id, int l, int r, int pos, int d) { if(pos < l || pos > r) return; if(l == r) { mx[id] = d; return; } int mid = l + r >> 1; upd(id << 1, l, mid, pos, d); upd(id << 1 | 1, mid + 1, r, pos, d); mx[id] = max(mx[id << 1], mx[id << 1 | 1]); } ii get(int id, int l, int r, int u, int v) { if(l > v || r < u) return {-1, inf}; if(l >= u && r <= v) return {mx[id], l}; int mid = l + r >> 1; ii n1 = get(id << 1, l, mid, u, v); ii n2 = get(id << 1 | 1, mid + 1, r, u, v); opti(n1, n2); return n1; } } smt; signed main() { if(fopen(task".inp", "r")) { freopen(task".inp", "r", stdin); freopen(task".out", "w", stdout); } ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n >> d; FOR(i, 1, n) { cin >> a[i]; val.pb(a[i]); } val.pb(-1); sort(val.begin(), val.end()); val.erase(unique(val.begin(), val.end()), val.end()); nv = val.size(); FOR(i, 1, n) a[i] = lower_bound(val.begin(), val.end(), a[i]) - val.begin() + 1; smt.init(); int res = 0; FOR(i, 1, n) { ii tmp = smt.get(1, 1, nv, 1, a[i] - 1); ii best = {1, a[i]}; if(tmp.fi != -1) opti(best, {tmp.fi + 1, a[i]}); tmp = smt.get(1, 1, nv, a[i], nv); if(tmp.fi != -1) opti(best, tmp); // cout << i << ' ' << best.fi << ' ' << best.se << '\n'; while(dq[best.se].size() && dq[best.se].back().fi <= best.fi) dq[best.se].pop_back(); dq[best.se].push_back({best.fi, i}); smt.upd(1, 1, nv, best.se, dq[best.se].front().fi); if(i - d > 0) { while(dq[a[i - d]].size() && dq[a[i - d]].front().se <= i - d) dq[a[i - d]].pop_front(); } if(dq[a[i - d]].size()) smt.upd(1, 1, nv, a[i - d], dq[a[i - d]].front().fi); else smt.upd(1, 1, nv, a[i - d], -1); if(i == n) cout << best.fi << '\n'; } }

Main.cpp: In function 'int main()':
Main.cpp:61:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   61 |         freopen(task".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:62:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   62 |         freopen(task".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~