Submission #268616

#TimeUsernameProblemLanguageResultExecution timeMemory
268616Osama_AlkhodairyBigger segments (IZhO19_segments)C++17
100 / 100
590 ms37116 KiB
#include <bits/stdc++.h> using namespace std; #define finish(x) return cout << x << endl, 0 #define ll long long const int N = 500001; const ll INF = 1e18; int n; vector <int> a; ll sum[N], dp[N], tree[4 * N], lazy[4 * N]; void push(int l, int r, int node){ tree[node] += lazy[node]; if(l != r){ lazy[2 * node] += lazy[node]; lazy[2 * node + 1] += lazy[node]; } lazy[node] = 0; } void update(int l, int r, int node, int s, int e, ll v){ if(r < l) return; push(l, r, node); if(r < s || l > e) return; if(s <= l && r <= e){ lazy[node] += v; push(l, r, node); return; } int mid = (l + r) / 2; update(l, mid, 2 * node, s, e, v); update(mid + 1, r, 2 * node + 1, s, e, v); tree[node] = min(tree[2 * node], tree[2 * node + 1]); } int query(int l, int r, int node, int p){ if(r < l || l > p) return -1; push(l, r, node); if(r <= p && tree[node] > 0) return -1; if(l == r) return l; int mid = (l + r) / 2; int ret = query(mid + 1, r, 2 * node + 1, p); if(ret != -1) return ret; return query(l, mid, 2 * node, p); } ll get_sum(int l, int r){ return sum[r] - sum[l - 1]; } int main(){ ios_base::sync_with_stdio(0); cin.tie(0); for(int i = 0 ; i < 4 * N ; i++){ tree[i] = INF; } cin >> n; a.resize(n + 1); for(int i = 1 ; i <= n ; i++){ cin >> a[i]; } for(int i = 1 ; i <= n ; i++){ sum[i] = sum[i - 1] + a[i]; } update(0, n, 1, 0, 0, -INF); vector <int> ans(n + 1); for(int i = 1 ; i <= n ; i++){ update(0, n, 1, 0, i - 1, -a[i]); int idx = query(0, n, 1, i - 1); ans[i] = ans[idx] + 1; update(0, n, 1, i, i, -INF + get_sum(idx + 1, i)); } cout << ans[n] << endl; }
#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...