제출 #1034218

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1034218		juicy	Financial Report (JOI21_financial)	C++17	100 / 100	343 ms	27728 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif

const int N = 3e5 + 5;

int n, d;
int a[N], lab[N], lt[N], dp[N], s[4 * N];

void upd(int i, int x, int id = 1, int l = 1, int r = n) {
	if (l == r) {
		s[id] = x;
		return;
	}
	int md = (l + r) / 2;
	if (i <= md) {
		upd(i, x, id * 2, l, md);
	} else {
		upd(i, x, id * 2 + 1, md + 1, r);
	}
	s[id] = max(s[id * 2], s[id * 2 + 1]);
}

int qry(int u, int v, int id = 1, int l = 1, int r = n) {
	if (u <= l && r <= v) {
		return s[id];
	}
	int md = (l + r) / 2;
	if (v <= md) {
		return qry(u, v, id * 2, l, md);
	}
	if (md < u) {
		return qry(u, v, id * 2 + 1, md + 1, r);
	}
	return max(qry(u, v, id * 2, l, md), qry(u, v, id * 2 + 1, md + 1, r));
}

int get(int u) {
	return lab[u] < 0 ? u : lab[u] = get(lab[u]);
}

bool unite(int u, int v) {
	u = get(u), v = get(v);
	if (u == v) {
		return 0;
	}
	if (lab[u] > lab[v]) {
		swap(u, v);
	}
	lab[u] += lab[v];
	lab[v] = u;
	lt[u] = min(lt[u], lt[v]);
	return 1;
}

int main() {
	ios::sync_with_stdio(false); cin.tie(nullptr);

	cin >> n >> d;
	for (int i = 1; i <= n; ++i) {
		cin >> a[i];
	}
	fill(lab + 1, lab + n + 1, -1);
	iota(lt + 1, lt + n + 1, 1);
	vector<int> ord(n);
	iota(ord.begin(), ord.end(), 1);
	sort(ord.begin(), ord.end(), [&](int u, int v) {
		return a[u] < a[v];
	});
	set<int> st;
	auto add = [&](int x) {
		upd(x, dp[x]);
		auto it = st.insert(x).first;
		if (it != st.begin() && x - *prev(it) <= d) {
			unite(*prev(it), x);
		}
		if (next(it) != st.end() && *next(it) - x <= d) {
			unite(x, *next(it));
		}
	};
	auto lft = [&](int x) {
		auto it = st.lower_bound(x);
		if (it != st.begin() && x - *prev(it) <= d) {
			x = lt[get(*prev(it))];
		}
		return max(1, x - d);
	};
	for (int i = 0; i < n; ) {
		int j = i;
		while (j < n && a[ord[j]] == a[ord[i]]) {
			int p = ord[j], l = lft(p);
			dp[p] = qry(l, p) + 1;
			++j;
		}
		while (i < j) {
			add(ord[i++]);
		}
		i = j;
	}
	cout << *max_element(dp + 1, dp + n + 1);
	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