Submission #1047368

#TimeUsernameProblemLanguageResultExecution timeMemory
1047368VMaksimoski008Bouquet (EGOI24_bouquet)C++17
100 / 100
409 ms152904 KiB
#include <bits/stdc++.h> using namespace std; struct Node { int mx = 0; Node *l, *r; Node(int val) : mx(val), l(nullptr), r(nullptr) {} Node(Node *l, Node *r) : mx(0), l(l), r(r) { if(l) mx = max(mx, l->mx); if(r) mx = max(mx, r->mx); } }; Node *build(int tl, int tr) { if(tl == tr) return new Node(0); int tm = (tl + tr) / 2; return new Node(build(tl, tm), build(tm+1, tr)); } Node* update(Node *u, int tl, int tr, int p, int v) { if(tl == tr) return new Node(max(u->mx, v)); int tm = (tl + tr) / 2; if(p <= tm) return new Node(update(u->l, tl, tm, p, v), u->r); return new Node(u->l, update(u->r, tm+1, tr, p, v)); } int query(Node *u, int tl, int tr, int l, int r) { if(tl > tr || l > tr || tl > r) return 0; if(l <= tl && tr <= r) return u->mx; int tm = (tl + tr) / 2; return max(query(u->l, tl, tm, l, r), query(u->r, tm+1, tr, l, r)); } signed main() { int n; cin >> n; vector<int> L(n+1), R(n+1), dp(n+1, 1); for(int i=1; i<=n; i++) cin >> L[i] >> R[i]; vector<Node*> roots; roots.push_back(build(1, 2*n)); roots.push_back(update(roots[0], 1, 2*n, 1 + R[1], 1)); for(int i=2; i<=n; i++) { if(i - L[i] - 1 >= 1) dp[i] = query(roots[i-L[i]-1], 1, 2*n, 1, i-1) + 1; roots.push_back(update(roots.back(), 1, 2*n, i + R[i], dp[i])); } 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...