Submission #1187985

#TimeUsernameProblemLanguageResultExecution timeMemory
1187985esomerBouquet (EGOI24_bouquet)C++20
100 / 100
80 ms14920 KiB
#include <bits/stdc++.h> using namespace std; struct segTree { vector<int> v; int sz; void init (int n) { sz = 1; while (sz < n) sz *= 2; v.assign(2 * sz, 0); } void set(int i, int val, int x, int lx, int rx) { if (rx - lx == 1) { v[x] = max(v[x], val); return; } int m = (lx + rx) / 2; if (i < m) set(i, val, 2 * x + 1, lx, m); else set(i, val, 2 * x + 2, m, rx); v[x] = max(v[2 * x + 1], v[2 * x + 2]); } void set(int i, int val) { set(i, val, 0, 0, sz); } int calc(int l, int r, int x, int lx, int rx) { if (lx >= l && rx <= r) return v[x]; else if (lx >= r || rx <= l) return 0; int m = (lx + rx) / 2; return max(calc(l, r, 2 * x + 1, lx, m), calc(l, r, 2 * x + 2, m, rx)); } int calc(int l, int r) { return calc(l, r, 0, 0, sz); } }; int main() { ios_base::sync_with_stdio(0); cin.tie(0); int N; cin >> N; vector<int> l(N), r(N); for (int i = 0; i < N; i++) cin >> l[i] >> r[i]; segTree st; st.init(N); vector<vector<pair<int, int>>> add(N+1); int ans = 0; for (int i = 0; i < N; i++) { for (pair<int, int> pr : add[i]) st.set(pr.first, pr.second); int mx = st.calc(0, i - l[i]); ans = max(ans, mx + 1); add[min(N, i + r[i] + 1)].push_back({i, mx+1}); } cout << ans << "\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...