Submission #1189302

#TimeUsernameProblemLanguageResultExecution timeMemory
1189302NomioBouquet (EGOI24_bouquet)C++20
100 / 100
97 ms20384 KiB
#include<bits/stdc++.h> #define meta int tm = tl + (tr - tl) / 2, x = (i << 1) + 1, y = x + 1 using namespace std; using ll = long long; const int maxn = 2e5 + 5; int st[maxn * 4] {}; void update(int i, int tl, int tr, int pos, int val) { if(tl == tr) { st[i] = val; return; } meta; if(pos <= tm) update(x, tl, tm, pos, val); else update(y, tm + 1, tr, pos, val); st[i] = max(st[x], st[y]); } int query(int i, int tl, int tr, int l, int r) { if(l <= tl && tr <= r) return st[i]; if(l > tr || tl > r) return 0; meta; if(r <= tm) return query(x, tl, tm, l, r); else if(l > tm) return query(y, tm + 1, tr, l, r); else return max(query(x, tl, tm, l, tm), query(y, tm + 1, tr, tm + 1, r)); } int main() { ios::sync_with_stdio(0); cin.tie(0); int n; cin >> n; vector<int> l(n + 1), r(n + 1); vector<int> v[n * 2 + 1], dp(n + 1, 0); for(int i = 1; i <= n; i++) { cin >> l[i] >> r[i]; v[i + r[i] + 1].push_back(i); } for(int i = 1; i <= n; i++) { for(int x : v[i]) { update(0, 0, n, x, dp[x]); } int r = max(0, i - l[i] - 1); int X = query(0, 0, n, 0, r); dp[i] = X + 1; } cout << *max_element(dp.begin(), dp.end()) << '\n'; return 0; }
#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...