Submission #1080273

#	Time	Username	Problem	Language	Result	Execution time	Memory
1080273		wiwiho	Bouquet (EGOI24_bouquet)	C++14	100 / 100	43 ms	15712 KiB

Main

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

#define SZ(v) int(v.size())
#define iter(v) v.begin(), v.end()
#define pb emplace_back
#define ff first
#define ss second

using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

#ifdef zisk
void debug() { cerr << "\n"; }
template<class T, class ... U>
void debug(T a, U... b) {
	cerr << a << " ", debug(b...);
}
template<class T>
void pary(T l, T r){
	while (l != r) cerr << *l << " ", l++;
	cerr << "\n";
}
#else
#define debug(...) void()
#define pary(...) void()
#endif

int lowbit(int x) {
	return x & -x;
}
struct BIT {
	vector<int> bit;
	explicit BIT(int n): bit(n + 1) {}
	void modify(int x, int v) {
		for (; x < SZ(bit); x += lowbit(x))
			bit[x] = max(bit[x], v);
	}
	int query(int x) {
		int ans = 0;
		for (; x > 0; x -= lowbit(x))
			ans = max(ans, bit[x]);
		return ans;
	}
};

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	
	int n;
	cin >> n;

	BIT bit(n);

	vector<int> l(n + 1), r(n + 1);
	for (int i = 1; i <= n; i++)
		cin >> l[i] >> r[i];

	vector<int> dp(n + 1);
	vector<vector<int>> ev(n + 1);
	for (int i = 1; i <= n; i++) {
		for (int j : ev[i]) bit.modify(j, dp[j]);
		dp[i] = bit.query(max(0, i - l[i] - 1)) + 1;
		if (i + r[i] + 1 <= n)
			ev[i + r[i] + 1].pb(i);
	}
	cout << *max_element(iter(dp)) << "\n";

}

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