Submission #541612

#	Time	Username	Problem	Language	Result	Execution time	Memory
541612		xuliu	Financial Report (JOI21_financial)	C++17	100 / 100	499 ms	29896 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#define ll long long 
#define ld long double 
#define debug if(0)

struct segtree {
	int size;
	vector<int> seg;
	void init(int n) {
		size = 1;
		while(size < n) size <<= 1;
		seg.assign(2*size+2, 0);
	}
	void set(int x, int v) {
		x += size;
		seg[x] = v; x>>=1;
		while(x) {
			seg[x] = max(seg[2*x], seg[2*x+1]);
			x>>=1;
		}
	}
	int query(int l, int r, int x, int lx, int rx) {
		if(l <= lx && r >= rx) return seg[x];
		if(l > rx || r < lx) return 0;
		int m = (lx+rx)/2;
		return max(query(l, r, 2*x, lx, m), query(l, r, 2*x+1, m+1, rx));
	}
	int query(int l, int r) { return query(l, r, 1, 0, size-1); }
};

struct Dsu {
	static const int N = 3e5 + 4;
	int tab[N], cnt[N], mn[N];
	Dsu() {
		memset(cnt, 0, sizeof cnt);
		for(int i=0; i<N; i++) { tab[i] = mn[i] = i; }
	}
	int Find(int x) {
		if(tab[x] == x) return tab[x];
		return tab[x] = Find(tab[x]);
	}
	void unite(int a, int b) {
		int fa = Find(a), fb = Find(b);
		if(fa == fb) return;
		if(cnt[fa] < cnt[fb]) {
			tab[fa] = fb;
			cnt[fb] += cnt[fa];
			mn[fb] = min(mn[fa], mn[fb]);
		}
		else {
			tab[fb] = fa;
			cnt[fa] += cnt[fb];
			mn[fa] = min(mn[fa], mn[fb]);
		}
	}
	int getmn(int x) { return mn[Find(x)]; }
};

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	int n, d; cin>>n>>d;
	segtree st; st.init(n+1);
	Dsu dsu;
	vector<int> a(n), dp(n+1, 0);
	set<int> used;
	vector<pair<int, int>> ev(n);
	for(int i=0; i<n; i++) {
		cin>>a[i];
		ev[i] = {a[i], -(i+1)};
	}
	sort(ev.begin(), ev.end());
	for(auto e : ev) {
		int v, id; tie(v, id) = e;
		id *= (-1);
		auto it = used.lower_bound(id);
		if(it != used.end()) {
			int ii = *it;
			if(abs(id-ii) <= d) dsu.unite(id, ii);
		}
		if(it != used.begin()) {
			--it; int ii = *it;
			if(abs(id-ii) <= d) dsu.unite(id, ii);
		}
		used.insert(id);
		dp[id] = st.query(dsu.getmn(id), id) + 1;
		st.set(id, dp[id]);
		debug cerr<<"dp["<<id<<"] = st.getmin("<<dsu.getmn(id)<<", "<<id<<")_+ 1 = "<<dp[id]<<"\n";
	}
	cout<<st.query(1, n)<<"\n";
}

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