Submission #446599

#	Time	Username	Problem	Language	Result	Execution time	Memory
446599		dutch	Financial Report (JOI21_financial)	C++17	100 / 100	759 ms	19212 KiB

Main

#include <bits/stdc++.h>
using namespace std;

const int INF = 2e9, LIM = 3e5;

struct LazySegmentTree{
	const int ID = INF+1;
	vector<int> a, b;
	int n = 1, l, r, v;
	LazySegmentTree(int N){
		while((n+=n) < N);
		a.assign(2*n, ID);
		b.assign(2*n, ID);
	}
	void assign(int x, int lx, int rx){
		if(r<=lx || rx<=l) return;
		if(l<=lx && rx<=r) return void(a[x] = b[x] = v);
		int mx = (lx + rx) / 2;
		if(a[x] != ID){ // propagation
			a[2*x+1] = a[2*x+2] = a[x];
			b[2*x+1] = b[2*x+2] = b[x];
			a[x] = ID;
		}
		assign(2*x+1, lx, mx);
		assign(2*x+2, mx, rx);
		b[x] = min(b[2*x+1], b[2*x+2]);
	}
	void rangeAssign(int L, int R, int V){
		l = L, r = R + 1, v = V;
		assign(0, 0, n);
	}
	int rangeMin(int x, int lx, int rx){
		if(r<=lx || rx<=l) return INF;
		if(l<=lx && rx<=r) return b[x];
		if(a[x] != ID) return a[x];
		int mx = (lx + rx) / 2;
		return min(rangeMin(2*x+1, lx, mx), rangeMin(2*x+2, mx, rx));
	}
	int rangeMin(int L, int R){
		l = L, r = R + 1;
		return rangeMin(0, 0, n);
	}
	int firstMin(int x, int lx, int rx){
		if(b[x] > v) return n;
		if(rx - lx < 2 || a[x] != ID) return a[x] == v ? lx : n;
		int mx = (lx + rx) / 2;
		if(b[2*x+1] <= v) return firstMin(2*x+1, lx, mx);
		else return firstMin(2*x+2, mx, rx);
	}
	int lastMin(int x, int lx, int rx){
		if(b[x] > v) return n;
		if(rx - lx < 2 || a[x] != ID) return a[x] == v ? rx-1 : n;
		int mx = (lx + rx) / 2;
		if(b[2*x+2] <= v) return lastMin(2*x+2, mx, rx);
		else return lastMin(2*x+1, lx, mx);
	}
	array<int, 2> getRange(int V){
		v = V;
		return {firstMin(0, 0, n), lastMin(0, 0, n)};
	}
};

int n, d, a[LIM], C[LIM];

signed main(){
	cin.tie(0)->sync_with_stdio(0);
	cin >> n >> d;
	for(int i=0; i<n; ++i){
		cin >> a[i];
		C[i] = a[i];
	}
	sort(C, C+n);
	for(int i=0; i<n; ++i){
		a[i] = lower_bound(C, C+n, a[i]) - C;
	}

	LazySegmentTree dp(n), last(n);
	int ans = 0;

	for(int i=0; i<n; ++i){
		auto [l, r] = last.getRange(i-d-1);
		dp.rangeAssign(l, r, INF);
		last.rangeAssign(l, r, INF);
		
		int x = 1 + max(0, -dp.rangeMin(0, a[i]-1));
		x = min(-x, dp.rangeMin(a[i], a[i]));
		dp.rangeAssign(a[i], a[i], x);
		last.rangeAssign(a[i], n-1, i);

		ans = max(ans, -x);
	}

	cout << ans;
}

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