This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#define nl '\n'
const int INF = 1e9+10;
struct Seg {
const int ID = INF; int comb(int a, int b) { return min(a, b); }
vector<int> seg, lazy; int n;
void init(int N) {
n = 1; while(n < N) n *= 2;
seg.assign(2*n, ID);
lazy.assign(2*n, ID);
}
void pull(int p) { seg[p] = comb(seg[2*p], seg[2*p+1]); }
void push(int x, int L, int R) {
if (lazy[x] == ID) return;
// cout << "LAZY: " << lazy[x] << " " << x << " " << L << " " << R << nl;
seg[x] = lazy[x];
// cout << seg[x] << nl;
if (L != R) for(int i = 0; i < 2; i++) lazy[2*x+i] = lazy[x];
lazy[x] = ID;
}
void upd(int l, int r, int v, int x, int L, int R) {
push(x, L, R); if (r < L || R < l) return;
if (l <= L && R <= r) {
lazy[x] = v;
push(x, L, R);
return;
}
int M = (L+R)/2;
upd(l, r, v, 2*x, L, M);
upd(l, r, v, 2*x+1, M+1, R);
pull(x);
}
int query(int l, int r, int x, int L, int R) {
push(x, L, R); if (r < L || R < l) return ID;
if (l <= L && R <= r) return seg[x];
int M = (L+R)/2;
return comb(query(l, r, 2*x, L, M), query(l, r, 2*x+1, M+1, R));
}
int get() { return seg[1]; };
void upd(int l, int r, int v) { upd(l, r, v, 1, 0, n-1); }
// void set(int p, int v) { set(p, v, 1, 0, n-1); }
int query(int l, int r) { return query(l, r, 1, 0, n-1); }
};
int main() {
cin.tie(0)->sync_with_stdio(0);
int N, K; cin >> N >> K;
vector<int> A(N); for(auto &x : A) cin >> x;
int M = -1;
{
map<int, int> mp; int cur = 0;
for(auto x : A) mp[x]++;
for(auto &p : mp) p.second = cur++;
for(auto &x : A) x = mp[x];
M = cur;
}
Seg st; st.init(N);
for(int i = 0; i < N; i++) st.upd(i, i, A[i]);
Seg dp; dp.init(M); dp.upd(0, M-1, 0);
for(int i = 0; i < N; i++) {
int best = max(0, -dp.query(0, A[i]-1)) + 1;
best = max(best, -dp.query(A[i], A[i]));
dp.upd(A[i], A[i], -best);
int mn = st.query(max(0, i-K+1), i);
dp.upd(0, mn-1, 0);
}
cout << -dp.query(A.back(), M-1) << nl;
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... |