Submission #1167428

#	Time	Username	Problem	Language	Result	Execution time	Memory
1167428		uranhishig	Bouquet (EGOI24_bouquet)	C++17	8 / 100	59 ms	5096 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define all(a) (a).begin(),(a).end()
#define rep(i, n) for(int i = 0; i < (n); i++)
#define rep1(i, n) for(int i = 1; i <= (n); i++)

const int mx = 8e5 + 9;
bool b1 = true;
bool b2 = true;
bool b4 = true;

int s[mx];

void update(int i, int L, int R, int k, int v) {
	if (L == R) {
		s[i] = v;
		return;
	}
	int M = (L + R) / 2;
	int x = 2 * i + 1, y = x + 1;
	if (k <= M) update(x, L, M, k, v);
	else update(y, M + 1, R, k, v);
	s[i] = max(s[x], s[y]);
	return;
}

int query(int i, int L, int R, int l, int r) {
	if (L == l && r == R) {
		return s[i];
	}
	int M = (L + R) / 2;
	int x = 2 * i + 1, y = x + 1;
	if (r <= M) return query(x, L, M, l, r);
	else if (M + 1 <= l) return query(y, M + 1, R, l, r);
	else return max(query(x, L, M, l, M) , query(y, M + 1, R, M + 1, r));
}

signed main() {
	int n; cin >> n;
	vector<int> l(n);
	vector<int> r(n);

	for (int i = 0; i < n; i++) {
		cin >> l[i] >> r[i];
		if (r[i] != 0) {
			b2 = false;
		}
		if (l[i] != r[0]) {
			b1 = false;
		}
		if(r[i] != r[0]) {
			b1 = false;
		}
		if (r[i] > 2) {
			b4 = false;
		}
		if (l[i] > 2) {
			b4 = false;
		}
	}
	int dp[n + 1];
	for (int i = 0; i <= n; i++) {
		dp[i] = 0;
		if(l[i] <= i && n - i <= r[i]) dp[i] = 1;
	}
	int ans = 0;
	
	//subtask 1
	if (b1) {
		cout << (l[0] + n)/(l[0] + 1);
		return 0;
	}

	//subtask 3
	if (n <= 1000) {
		
		for (int i = 1; i < n; i++) {
			for (int j = 0; j < i - l[i]; j++) {
				if (r[j] < i - j) {
					dp[i] = max(dp[i], dp[j] + 1);
				}
			}
			ans = max(dp[i], ans);
		}
		cout << ans << endl;
		return 0;
	}

	//subtask 4
	if (b4) {
		for (int i = 1; i < n; i++) {
			for (int j = max(0ll, i - l[i] - 10) ; j < i - l[i]; j++) {
				if (r[j] < i - j) {
					dp[i] = max(dp[i], dp[j] + 1);
				}
			}
			ans = max(dp[i], ans);
		}
		cout << ans << endl;
		return 0;
	}
	
	// subtask 2
	if (b2) {
		for (int i = 0; i < n; i++) {
			if (i - l[i] < 0) dp[i] = 0;
			else if (i - l[i] == 0) dp[i] = 1;
			else dp[i] = query(0, 0, n - 1, 0, i - l[i] - 1) + 1;
			if (dp[i] > 0) update(0, 0, n - 1, i, dp[i]);
			ans = max(ans, dp[i]);
		}
		cout << ans << endl;
		return 0;
	}
	//subtask 5
	cout << ans << endl;
	return 0;
}

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