제출 #1170797

#제출 시각아이디문제언어결과실행 시간메모리
1170797nguyenkhangninh99Bouquet (EGOI24_bouquet)C++20
100 / 100
122 ms31156 KiB
#include <bits/stdc++.h> using namespace std; #define int long long const int maxn = 2e5 + 5; int st[4 * maxn]; void update(int id, int l, int r, int i, int val){ if (l > i || r < i || l > r) return; if (l == r){ st[id] = max(st[id], val); return; } int mid = (l + r) / 2; update(2 * id, l, mid, i, val); update(2 * id + 1, mid + 1, r, i, val); st[id] = max(st[2 * id], st[2 * id + 1]); } int get(int id, int l, int r, int x, int y){ if(l > y || r < x) return 0; if(l >= x && r <= y) return st[id]; int mid = (l + r) / 2; return max(get(2 * id, l, mid, x, y), get(2 * id + 1, mid + 1, r, x , y)); } signed main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); int n; cin >> n; vector<int> a(n + 1), b(n + 1), sweep1[n + 2], sweep2[n + 2]; for(int i = 1; i <= n; i++){ cin >> a[i] >> b[i]; sweep1[min(i + b[i], n) + 1].push_back(i); sweep2[i].push_back(max(1ll, i - a[i]) - 1); } vector<int> dp(n + 1, 1); for(int i = 1; i <= n; i++){ for(int j: sweep1[i]) update(1, 1, n, j, dp[j]); for(int j: sweep2[i]) dp[i] = max(dp[i], get(1, 1, n, 1, j) + 1); } cout << *max_element(dp.begin(), dp.end()); }
#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...