제출 #1127764

#제출 시각아이디문제언어결과실행 시간메모리
1127764VMaksimoski008Bigger segments (IZhO19_segments)C++17
100 / 100
213 ms16076 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; using pii = pair<int, int>; struct fenwick { int n; vector<pii> tree; fenwick(int _n) : n(_n+10), tree(_n+50) {} void update(int p, int v, int p2) { for(p++; p<n; p+=p&-p) tree[p] = max(tree[p], { v, p2 }); } pii query(int p) { pii ans = { 0, 0 }; for(p++; p; p-=p&-p) ans = max(ans, tree[p]); return ans; } }; signed main() { int n; cin >> n; vector<ll> pref(n+1), dp(n+1), last(n+1); for(int i=1; i<=n; i++) cin >> pref[i]; for(int i=1; i<=n; i++) pref[i] += pref[i-1]; pref.push_back(1e18); fenwick fwt(n); for(int i=1; i<=n; i++) { auto [v, p] = fwt.query(i); dp[i] = v + 1; last[i] = p; ll V = 2 * pref[i] - pref[p]; int pos = lower_bound(pref.begin(), pref.end(), V) - pref.begin(); fwt.update(pos, dp[i], i); } cout << dp[n] << '\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...