#include <bits/stdc++.h>
#include <ext/rope>
#include <random>
#include <chrono>
#include <ext/pb_ds/assoc_container.hpp>
#define file ""
#define all(x) x.begin(), x.end()
#define sc second
#define fr first
#define pb push_back
#define mp make_pair
#define pss pair<line*, line*>
#define pptreap pair<treap*, treap*>
using namespace std;
using namespace __gnu_cxx;
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
const ll inf = 1e16;
const int MOD = 1e9 + 7;
const int dx[] = {+1, -1, 0, 0};
const int dy[] = {0, 0, +1, -1};
int const N = 7e6;
struct treap {
ll x, y;
pii mx;
treap *l, *r;
treap(ll new_x, int new_mx, int pos) {
x = new_x;
y = (rand() << 15) | rand();
mx = {new_mx, pos};
l = r = nullptr;
}
};
pii getmx(treap *a) {
if (a == nullptr)
return {-1e9, -1e9};
return a -> mx;
}
void update(treap *&a) {
a->mx = max(a->mx, max(getmx(a->l), getmx(a->r)));
}
treap* merge(treap *t1, treap *t2) {
if (t1 == nullptr)
return t2;
if (t2 == nullptr)
return t1;
if (t1->y > t2->y) {
t1->r = merge(t1->r, t2);
update(t1);
return t1;
}
else {
t2->l = merge(t1, t2->l);
update(t2);
return t2;
}
}
pptreap split(treap *t, ll k) {
if (t == nullptr)
return mp(nullptr, nullptr);
if (t->x <= k) {
pptreap cnt = split(t->r, k);
t->r = cnt.fr;
update(t);
return mp(t, cnt.sc);
}
else {
pptreap cnt = split(t->l, k);
t->l = cnt.sc;
update(t);
return mp(cnt.fr, t);
}
}
int main() {
ios_base :: sync_with_stdio(false);
cin.tie(nullptr);
srand(time(NULL));
int n;
cin >> n;
vector<int> a(n + 1);
for (int i = 1; i <= n; i++)
cin >> a[i];
vector<ll> dp(n + 1), sum(n + 1), pref(n + 1);
for (int i = 1; i <= n; i++)
pref[i] = pref[i - 1] + a[i];
treap* t = new treap (0, 0, 0);
for (int i = 1; i <= n; i++) {
pptreap k = split (t, pref[i]);
pii pos = getmx(k.fr);
t = merge(k.fr, k.sc);
dp[i] = pos.fr + 1;
sum[i] = pref[i] - pref[pos.sc];
treap* nw = new treap (sum[i] + pref[i], dp[i], i);
k = split(t, sum[i] + pref[i]);
t = merge(merge(k.fr, nw), k.sc);
}
cout << dp[n];
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
384 KB |
Output is correct |
2 |
Incorrect |
4 ms |
384 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
384 KB |
Output is correct |
2 |
Incorrect |
4 ms |
384 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
384 KB |
Output is correct |
2 |
Incorrect |
4 ms |
384 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
384 KB |
Output is correct |
2 |
Incorrect |
4 ms |
384 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
384 KB |
Output is correct |
2 |
Incorrect |
4 ms |
384 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |