Submission #420302

#	Time	Username	Problem	Language	Result	Execution time	Memory
420302		IOrtroiii	Financial Report (JOI21_financial)	C++17	100 / 100	1179 ms	47856 KiB

Main

#include <bits/stdc++.h>
 
using namespace std;
 
int main() {
	ios_base::sync_with_stdio(false); cin.tie(nullptr);
 
	int N, D; cin >> N >> D;
	vector<int> A(N); for (int &a : A) cin >> a;
	
	vector<int> ord(N); iota(ord.begin(), ord.end(), 0);
	sort(ord.begin(), ord.end(), [&](const int &i, const int &j) { 
		return make_pair(A[i], -i) < make_pair(A[j], -j); 
	});
	int S = 1;
	while (S < N) S *= 2;
	vector<int> loc(N);
	for (int i = 0; i < N; ++i) loc[ord[i]] = i;
 
	struct Node {
		int best = 0;
		int pref = 0;
		int suff = 0;
		bool all = false;
	};
 
	auto merge = [&](Node l, Node r) {
		Node ans;
		ans.all = l.all & r.all;
		ans.best = max({l.best, r.best, l.suff + r.pref});
		ans.pref = l.all ? l.pref + r.pref : l.pref;
		ans.suff = r.all ? r.suff + l.suff : r.suff;
		return ans;
	};
 
	vector<Node> tree0(2 * S);
	auto modify0 = [&](int p) {
		tree0[p += S] = {1, 1, 1, true};
		p /= 2;
		while (p > 0) {
			tree0[p] = merge(tree0[2 * p], tree0[2 * p + 1]);
			p /= 2;
		}	
	};
 
	auto query0 = [&](int l, int r) {
		Node ansl{};
		Node ansr{};
		for (l += S, r += S; l <= r; l /= 2, r /= 2) {
			if (l % 2) ansl = merge(ansl, tree0[l++]);
			if (r % 2 == 0) ansr = merge(tree0[r--], ansr);
		}
		return merge(ansl, ansr).best;
	};
 
	vector<vector<int>> evts(N);
	reverse(ord.begin(), ord.end());
	vector<vector<int>> prvs(N); 
	for (int i : ord) {
		int lo = i, hi = N - 1;
		while (lo < hi) {
			int mi = (lo + hi) / 2;
			if (query0(i, mi) >= D) hi = mi;
			else lo = mi + 1;
		}
		evts[lo].push_back(i);
		modify0(i);
	}
 	
	vector<int> tree1(2 * S);
	auto modify1 = [&](int p, int v) {
		tree1[p += S] = v;
		p /= 2;
		while (p > 0) {
			tree1[p] = max(tree1[2 * p], tree1[2 * p + 1]);
			p /= 2;
		}
	};
	auto query1 = [&](int l, int r) {
		int ans = 0;
		for (l += S, r += S; l <= r; l /= 2, r /= 2) {
			if (l % 2) ans = max(ans, tree1[l++]);
			if (r % 2 == 0) ans = max(ans, tree1[r--]);
		}
		return ans;
	};
 
	int ans = 0;
	for (int i = 0; i < N; ++i) {
		int dp = query1(0, loc[i]) + 1;
		ans = max(ans, dp);
		modify1(loc[i], dp);
		for (int j : evts[i]) {
			modify1(loc[j], 0);
		}
	}
	cout << ans << '\n';
	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