Submission #1341114

#TimeUsernameProblemLanguageResultExecution timeMemory
1341114aykhnBouquet (EGOI24_bouquet)C++20
100 / 100
98 ms14064 KiB
#include <bits/stdc++.h>
 
using namespace std;

#define inf 0x3F3F3F3F3F3F3F3F
#define int long long
#define bpc __builtin_popcountll

const int mod = 998244353;
const int MXN = 2e5 + 5;

int st[4 * MXN];

void upd(int l, int r, int x, int ind, int val)
{
	if (l == r)
	{
		st[x] = max(st[x], val);
		return;
	}
	int mid = (l + r) >> 1;
	if (ind <= mid) upd(l, mid, 2*x, ind, val);
	else upd(mid + 1, r, 2*x + 1, ind, val);
	st[x] = max(st[2*x], st[2*x + 1]);
}
int get(int l, int r, int x, int lx, int rx)
{
	if (lx > rx) return 0;
	if (l > rx || r < lx) return 0;
	if (l >= lx && r <= rx) return st[x];
	int mid = (l + r) >> 1;
	return max(get(l, mid, 2*x, lx, rx), get(mid + 1, r, 2*x + 1, lx, rx));
}

int n;
vector<array<int, 3>> v;
int dp[MXN], L[MXN], R[MXN];

signed main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> n;
	for (int i = 1; i <= n; i++)
	{
		int l, r;
		cin >> l >> r;
		l = max(1LL, i - l), r = min(n, i + r);
		v.push_back({l, r, i});
		L[i] = l, R[i] = r;
	}
	sort(v.begin(), v.end());
	int j = 1;
	for (array<int, 3> &i : v)
	{
		while (j < i[0]) upd(1, n, 1, R[j], dp[j]), j++;
		dp[i[2]] = get(1, n, 1, 1, i[2] - 1) + 1;
	}
	cout << *max_element(dp, dp + MXN) << '\n';
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...