Submission #683211

#	Time	Username	Problem	Language	Result	Execution time	Memory
683211		NK_	Financial Report (JOI21_financial)	C++17	100 / 100	968 ms	32856 KiB

Main

#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;
}

• Subtask 1: 14 / 14
• Subtask 2: 14 / 14
• Subtask 3: 20 / 20
• Subtask 4: 12 / 12
• Subtask 5: 5 / 5
• Subtask 6: 35 / 35