Submission #1204649

#	Time	Username	Problem	Language	Result	Execution time	Memory
1204649		ducksaysquack	Financial Report (JOI21_financial)	C++20	19 / 100	809 ms	52080 KiB

Main

#include <bits/stdc++.h>
#define int long long
#define f first
#define s second
using namespace std;
const int M = 1e18;
template<int e> struct segtree {
	vector<int> v, a;
	void resz(int n, vector<int> w) {v.assign(4*n,e); a = w;}
	void init(int k, int l, int r) {
		if(l > r) return;
		if(l == r) v[k] = a[l];
		else {
			int m = (l+r)/2;
			init(2*k,l,m); init(2*k+1,m+1,r);
			v[k] = min(v[2*k],v[2*k+1]);
		}
	}
	void upd(int k, int l, int r, int p, int x) {
		if(l > r) return;
		if(l == r) {v[k] = x; return;}
		int m = (r+l)/2;
		if(p <= m) upd(2*k,l,m,p,x);
		else upd(2*k+1,m+1,r,p,x);
		v[k] = min(v[2*k],v[2*k+1]);
	}
	int prod(int k, int x, int y, int l, int r) {
		if(l == x && y == r) return v[k];
		if(l > r) return e;
		int m = (x+y)/2;
		return min(prod(2*k,x,m,l,min(m,r)),prod(2*k+1,m+1,y,max(l,m+1),r));
	}
};
signed main() {
	int n, k; cin >> n >> k;
	vector<int> v(n); for(int i=0;i<n;i++) cin >> v[i];
	segtree<M> st, rt, dp; st.resz(n,v); st.init(1,0,n-1);
	vector<int> r(n); for(int i=0;i<n-k+1;i++) r[i] = st.prod(1,0,n-1,i,i+k-1);
	rt.resz(n-k+1,r); rt.init(1,0,n-k);
	for(int i=0;i<n-k;i++) {
		int l = i+1, u = n-k;
		while(l<u) {
			int m = (l+u)/2;
			if(rt.prod(1,0,n-1,i+1,m) > v[i]) u = m;
			else l = m+1;
		}
		r[i] = l;
	}
	for(int i=n-k;i<n;i++) r[i] = n-k;
	vector<pair<int,int>> w; for(int i=0;i<n;i++) w.push_back({-v[i],i});
	sort(begin(w),end(w)); vector<int> d(n,M);
	dp.resz(n,d);
	for(int i=0;i<n;i++) dp.upd(1,0,n-1,w[i].s,-max(-dp.prod(1,0,n-1,w[i].s,r[w[i].s]+k-1),0LL)-1);
	cout << -dp.prod(1,0,n-1,0,n-1);
}

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