Submission #1207019

#	Time	Username	Problem	Language	Result	Execution time	Memory
1207019		trimkus	Bouquet (EGOI24_bouquet)	C++20	100 / 100	103 ms	14408 KiB

Main

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


struct Fenwick {
	int n;
	vector<int> bit;
	Fenwick(int n) {
		this->n = n;
		bit = vector<int>(n + 2);
	}
	void update(int i, int delta) {
		i++;
		for (; i <= n + 1; i += i & -i) {
			bit[i] = max(bit[i], delta);
		}
	}
	int query(int i) {
		int res = 0;
		i++;
		for (; i > 0; i -= i & -i) {
			res = max(res, bit[i]);
		}
		return res;
	}
};

int main() {
	int n;
	cin >> n;
	vector<int> l(n + 1), r(n + 1);
	for (int i = 1; i <= n; ++i) {
		cin >> l[i] >> r[i];
	}
	Fenwick tree(n);
	vector<int> dp(n + 2);
	vector<vector<int>> events(n + 2);
	for (int i = 1; i <= n; ++i) {
		for (auto& u : events[i]) {
			tree.update(u, dp[u]);
		}
		int left = max(0, i - l[i] - 1);
		int right = min(n + 1, i + r[i] + 1);
		dp[i] = 1 + tree.query(left);
		events[right].push_back(i);
		//~ cout << dp[i] << " ";
	}
	//~ cout << "\n";
	//~ vector<vector<int>> dp(n + 1, vector<int>(n + 1));
	//~ for (int i = 1; i <= n; ++i) {
		//~ for (int j = 1; j <= n; ++j) {
			//~ dp[i][j] = dp[i - 1][j];
		//~ }
		//~ int left = max(0, i - l[i] - 1);
		//~ for (int j = 0; j <= left; ++j) {
			//~ int right = j + r[j] + 1;
			//~ if (i >= right) {
				//~ dp[i][i] = max(dp[i][i], dp[i - 1][j] + 1);
			//~ }
		//~ }
	//~ }
	int res = 0;
	for (int i = 0; i <= n + 1; ++i) {
		res = max(res, dp[i]);
	}
	cout << res << "\n";
}

• Subtask 1: 8 / 8
• Subtask 2: 16 / 16
• Subtask 3: 28 / 28
• Subtask 4: 18 / 18
• Subtask 5: 30 / 30