/*
⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠃⡀⡀⡀⠠⢄⣠⣴⣼⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣯⢿⣿⣿⣿⣾⣆⡀⡀⢻
⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠟⡀⡀⠄⡐⣰⣷⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡄⣿⣿⣿⣿⣿⣷⡀⠈
⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠉⡀⢀⣔⣷⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠘⣿⣿⣿⣿⣿⣿⡄
⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡿⡀⢀⢢⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡆⣿⣿⣿⣿⣿⣿⣿
⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠟⢀⣦⣿⠰⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⢿⣿⣿⣿⣿⣿⣿
⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠋⡠⣷⣿⡟⢸⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⢸⣿⣿⣿⣿⣿⣿
⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠁⣰⣿⣿⣿⠇⢼⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡿⠈⣿⣿⣿⣿⣿⣿
⣿⣿⣿⣿⣿⣿⣿⣿⣿⠁⣴⣿⣿⣿⣿⡀⢸⣿⣿⡏⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡇⡀⣿⣿⣿⣿⣿⣿
⣿⣿⣿⣿⣿⣿⣿⣿⠁⣼⣿⣿⣿⣿⣿⡀⠐⣿⣿⠁⢿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡟⣿⣿⡀⡆⣿⣿⣿⣿⣿⣿
⣿⣿⣿⣿⣿⣿⣿⡀⣺⣿⣿⣿⣿⣿⣿⡀⡀⢀⢈⡀⠈⢙⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠿⠿⠿⡀⠹⡿⣸⡇⢺⣿⣿⣿⢻⣿
⣿⣿⣿⣿⣿⣿⠁⢰⣿⡅⠻⣿⣿⣿⣿⡀⣿⡀⣿⡀⠐⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣶⣶⠂⡀⣶⢁⣿⣯⢸⣿⣿⠇⢸⣿
⣿⣿⣿⣿⣿⠁⡀⡀⢿⣿⡀⠉⢻⣿⣿⡇⣿⣷⡀⡀⣅⢿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠃⣼⡆⠋⣾⣿⣿⢸⣿⡿⡀⣾⣿
⣿⣿⣿⣿⠃⢠⣮⡀⡀⣈⠃⠘⣦⣴⣦⣤⣾⣿⣿⣶⣿⡈⣿⡀⣿⣿⣿⣿⣿⣿⣿⣿⡿⢀⣾⣿⣁⣾⣿⣿⡟⠸⠋⡤⢀⣿⣿
⣿⣿⣿⠃⢀⣾⣿⡧⠨⠿⠿⢿⣿⣿⣿⣿⣿⣿⣿⣿⣯⣽⡈⡆⠈⣿⣿⣿⣿⣿⡿⠁⣴⣿⣿⣿⣿⣿⣿⣿⣷⠿⢿⡗⢸⣿⠏
⣿⣿⠏⡀⣽⣿⣿⡇⣀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⣿⣄⢸⣄⠻⡿⠟⢁⣴⣿⠁⡀⡀⡀⡀⡀⡀⡀⡀⡀⣀⠅⣿⡟⣠
⣿⠏⡀⢲⣿⣿⣿⠇⣿⣿⡇⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⣿⣿⣿⣿⣿⣷⣴⣿⣿⣿⣿⡀⡀⡀⡀⡀⡀⡀⡀⡀⣿⡿⠘⣁⣾⣿
⠟⡀⢔⣿⣿⣿⣿⠂⣿⣿⠁⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡇⡀⡀⡀⡀⡀⡀⡀⡀⢸⣿⣶⠠⣿⣿⣿
⡀⡀⣺⣿⣿⣿⣿⡀⣿⣿⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⢸⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡀⡀⡀⡀⡀⡀⡀⡀⡀⣿⣿⠇⣼⣿⣿⣿
⡀⡐⣿⣿⣿⣿⣿⡀⣿⣿⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡀⡀⡀⡀⡀⡀⡀⡀⢠⣿⣿⡀⣿⣿⣿⣿
⡀⢿⣿⣿⣿⣿⣿⡂⢿⣿⣷⡀⡀⡀⡀⡀⡀⡀⡀⣴⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡀⡀⡀⡀⡀⡀⡀⢀⣿⣿⡏⢰⣿⣿⣿⣿
⢀⣿⣿⣿⣿⣿⣿⡅⢸⣿⣿⣿⣷⣦⣤⣴⣶⣾⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣦⣀⣀⣀⣤⣶⣿⣿⣿⡀⢼⣿⠫⣿⣿
⢨⣿⣿⣿⣿⣿⣿⡧⠐⣿⣿⣿⣿⣿⣿⣿⠉⡉⠉⣉⣉⠉⣉⣉⢉⠉⢉⡉⠉⠉⠉⠉⠉⠉⢹⣿⣿⣿⣿⣿⡏⡀⣺⡟⢰⣿⣿
⣸⣿⣿⣿⣿⣿⣿⣿⡀⣻⣿⣿⣿⣿⣿⣿⡆⣿⢸⣿⣿⡀⣿⣿⡟⡀⣿⣿⠁⣿⣿⡀⣿⠃⣼⣿⣿⣿⣿⡿⡀⡀⡿⠁⣾⣿⣿
⢺⡟⣿⣿⣿⣿⣿⣿⡀⡀⠻⣿⣿⣿⣿⣿⣿⡈⢸⣿⣿⡀⣿⣿⣷⢸⣿⣿⡀⣿⣿⠰⠋⣴⣿⣿⣿⡿⠋⡀⡀⡀⠁⢠⣿⣿⣿
⠸⡇⠹⣿⣿⣿⣿⣿⣇⡀⡀⡀⠛⢿⣿⣿⣿⣿⣄⠙⡿⢰⣿⣿⣿⢸⣿⣿⠠⡿⠋⣤⣿⣿⣿⠟⠉⡀⡀⡀⡀⡀⡀⣿⣿⣿⣿
⡀⠈⡀⠙⢿⣿⣿⣿⣿⡀⡀⡀⡀⡀⡀⣈⠉⠛⠿⢿⣶⣤⣉⣙⢉⣉⣉⣁⣤⠾⠛⠋⠉⡀⡀⡀⡀⡀⢀⣠⣤⣴⠴⠷⠶⠚⠋
⡀⡀⢰⣷⣄⡀⠛⠿⣿⣷⡀⣆⡀⡀⡀⠘⣿⣿⣿⣶⠖⣀⠲⣶⣶⣶⣶⠆⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⢀⡀⡀⡀⢈⠉⠉⠉⠉
⡀⡀⡪⣿⣿⣧⡀⢠⣤⣀⡁⡀⡀⡀⡀⣆⠈⠿⠛⣠⣿⣿⣦⠈⢿⣿⡟⢠⡀⡀⡀⡀⡀⡀⡀⡀⢽⣿⠿⡿⣿⣿⢿⡿⣿⣿⣿
⣀⡀⠱⣿⣿⣿⡀⣿⣿⣿⠟⡀⡀⡀⡀⣿⣿⣿⣿⣿⣿⣿⣿⣿⣦⣤⣴⣿⠇⡀⡀⡀⣄⡀⡠⡆⠘⣿⢸⣗⣥⣿⣿⣿⣰⣴⣬
⠋⢠⣦⡀⡹⠻⣷⡟⠛⠁⡀⡀⡀⡀⡀⡀⡀⠉⠉⠋⠙⠛⠛⠛⠛⠛⠉⠉⡀⡀⡀⡀⢹⣦⠘⢿⡀⣿⡎⣾⣿⣫⡶⣾⡿⣽⣭
*/
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
#define synchronize {ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);}
#define debug(...) fprintf(stderr, __VA_ARGS__), fflush(stderr)
#define time__(d) for(long blockTime = 0; (blockTime == 0 ? (blockTime=clock()) != 0 : false); debug("%s time : %.4fs", d, (double)(clock() - blockTime) / CLOCKS_PER_SEC))
#define ll long long
#define ld long double
#define ull unsigned long long
#define pii pair <int, int>
#define pli pair <ll, int>
#define pil pair <int, ll>
#define pll pair <ll, ll>
#define vvi vector <vector <int>>
#define all(v) (v).begin(), (v).end()
#define __builtin_popcount __builtin_popcountll
#define fi first
#define se second
template<class X, class Y>
bool maximize(X &x, const Y &y) {
if (x < y) {
x = y;
return true;
}
else return false;
}
template <class X, class Y>
bool minimize(X &x, Y y) {
if (x > y) {
x = y;
return true;
}
return false;
}
const int nmax = 5e5 + 5;
const ll mod = 1e9 + 7;
const ll inf = 1e18;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll rngesus(ll l, ll r) {
return uniform_int_distribution <long long>(l, r)(rng);
}
/** END OF TEMPLATE **/
struct seg_tree {
int n;
vector <ll> tree;
void set(int _n) {
this->n = _n;
tree.resize(4 * n + 5, inf);
}
void update(int id, int l, int r, int idx, ll val) {
if (idx > r || idx < l) return;
if (l == r) {
tree[id] = val;
return;
}
int mid = (l + r) >> 1;
update(2 * id, l, mid, idx, val);
update(2 * id + 1, mid + 1, r, idx, val);
tree[id] = min(tree[2 * id], tree[2 * id + 1]);
}
ll query(int id, int l, int r, int u, int v) {
if (u > r || v < l) return inf;
if (u <= l && r <= v) return tree[id];
int mid = (l + r) >> 1;
ll tl = query(2 * id, l, mid, u, v);
ll tr = query(2 * id + 1, mid + 1, r, u, v);
return min(tl, tr);
}
void update(int idx, ll val) { update(1, 0, n, idx, val); }
ll query(int l, int r) { return query(1, 0, n, l, r); }
};
ll n, a[nmax], ps[nmax];
pll f[nmax];
seg_tree seg;
int main() {
synchronize;
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
ps[i] = ps[i - 1] + a[i];
}
seg.set(n);
f[0] = {0, 0};
seg.update(0, 0);
for (int i = 1; i <= n; i++) {
int j;
int l = 0, r = i - 1;
while (l <= r) {
int mid = (l + r) >> 1;
if (seg.query(mid, i - 1) <= ps[i]) {
l = mid + 1;
j = mid;
}
else r = mid - 1;
}
if (f[j].se <= ps[i] - ps[j]) {
f[i].fi = f[j].fi + 1;
f[i].se = ps[i] - ps[j];
}
seg.update(i, ps[i] + f[i].se);
}
cout << f[n].fi;
return (0 ^ 0);
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |