Submission #539871

#	Time	Username	Problem	Language	Result	Execution time	Memory
539871		rk42745417	Financial Report (JOI21_financial)	C++17	100 / 100	628 ms	25628 KiB

Main

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

#define EmiliaMyWife ios::sync_with_stdio(0); cin.tie(0);
using ll = int64_t;
using ull = uint64_t;
using uint = uint32_t;
using ld = long double;
const int INF = 0x3f3f3f3f;
const ll LINF = ll(4e18) + ll(2e15);
const int MOD = 1e9 + 7;
const double EPS = 1e-9;
static int LamyIsCute = []() {
	EmiliaMyWife
	return 48763;
}();

const int N = 3e5 + 25;
struct segtree {
	int n, arr[N << 1];
	void init(int _n) { n = _n; }
	void edt(int p, int v) {
		for(arr[p += n] = v; p > 1; p >>= 1)
			arr[p >> 1] = max(arr[p], arr[p ^ 1]);
	}
	int que(int l, int r) {
		int res = 0;
		for(l += n, r += n; l < r; l >>= 1, r >>= 1) {
			if(l & 1)
				res = max(res, arr[l++]);
			if(r & 1)
				res = max(res, arr[--r]);
		}
		return res;
	}
} tree;
struct disjoint_set {
	int pa[N], sz[N], mn[N];
	void init(int n) {
		for(int i = 0; i < n; i++)
			pa[i] = i, sz[i] = 1, mn[i] = i;
	}
	int fnd(int x) { return pa[x] == x ? pa[x] : pa[x] = fnd(pa[x]); }
	void uni(int a, int b) {
		if((a = fnd(a)) == (b = fnd(b)))
			return;
		if(sz[a] > sz[b])
			swap(a, b);
		pa[a] = b;
		sz[b] += sz[a];
		mn[b] = min(mn[b], mn[a]);
	}
	inline int que(int x) { return mn[fnd(x)]; }
} dsu;

signed main() {
	int n, d;
	cin >> n >> d;
	vector<int> arr(n);
	for(int &a : arr)
		cin >> a;
	vector<int> ord(n);
	for(int i = 0; i < n; i++)
		ord[i] = i;
	sort(ord.begin(), ord.end(), [&](int a, int b) { return arr[a] == arr[b] ? a > b : arr[a] < arr[b]; });

	tree.init(n);
	dsu.init(n);
	set<int> has;
	for(int i : ord) {
		auto it = has.lower_bound(i);
		if(it != has.end() && *it - i <= d)
			dsu.uni(i, *it);
		if(it != has.begin() && i - *prev(it) <= d)
			dsu.uni(*prev(it), i);
		tree.edt(i, tree.que(dsu.que(i), i) + 1);
		has.insert(i);
	}
	cout << tree.que(0, 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