#include <bits/stdc++.h>
#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;
int
const N = 7e6;
struct treap {
ll x, y;
pii mx, val;
treap *l, *r;
treap(ll new_x, ll new_mx, ll pos) {
x = new_x;
y = (rand() << 15) | rand();
mx = {new_mx, pos};
val = {new_mx, pos};
l = r = nullptr;
}
};
pii getmx(treap *a) {
if (a == nullptr)
return {0, 0};
return a->mx;
}
void update(treap *&a) {
a->mx = max(a->val, 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);
}
}
bool exist(treap *t, int pos) {
if (t == nullptr)
return 0;
if (pos < t->x)
return exist(t->l, pos);
if (pos > t->x)
return exist(t->r, pos);
if (pos == t->x)
return 1;
}
void data() {
#ifdef PC
freopen("rofl.in", "r", stdin);
freopen("rofl.out", "w", stdout);
#endif
}
int main() {
data();
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
srand(time(nullptr));
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);
assert(!exist(t, sum[i] + pref[i]));
k = split(t, sum[i] + pref[i]);
t = merge(merge(k.fr, nw), k.sc);
}
cout << dp[n];
return 0;
}
Compilation message
segments.cpp: In function 'bool exist(treap*, int)':
segments.cpp:93:1: warning: control reaches end of non-void function [-Wreturn-type]
}
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
384 KB |
Output is correct |
| 2 |
Correct |
4 ms |
384 KB |
Output is correct |
| 3 |
Correct |
4 ms |
384 KB |
Output is correct |
| 4 |
Correct |
5 ms |
384 KB |
Output is correct |
| 5 |
Correct |
5 ms |
384 KB |
Output is correct |
| 6 |
Correct |
4 ms |
384 KB |
Output is correct |
| 7 |
Correct |
5 ms |
384 KB |
Output is correct |
| 8 |
Correct |
4 ms |
384 KB |
Output is correct |
| 9 |
Runtime error |
6 ms |
640 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 10 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
384 KB |
Output is correct |
| 2 |
Correct |
4 ms |
384 KB |
Output is correct |
| 3 |
Correct |
4 ms |
384 KB |
Output is correct |
| 4 |
Correct |
5 ms |
384 KB |
Output is correct |
| 5 |
Correct |
5 ms |
384 KB |
Output is correct |
| 6 |
Correct |
4 ms |
384 KB |
Output is correct |
| 7 |
Correct |
5 ms |
384 KB |
Output is correct |
| 8 |
Correct |
4 ms |
384 KB |
Output is correct |
| 9 |
Runtime error |
6 ms |
640 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 10 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
384 KB |
Output is correct |
| 2 |
Correct |
4 ms |
384 KB |
Output is correct |
| 3 |
Correct |
4 ms |
384 KB |
Output is correct |
| 4 |
Correct |
5 ms |
384 KB |
Output is correct |
| 5 |
Correct |
5 ms |
384 KB |
Output is correct |
| 6 |
Correct |
4 ms |
384 KB |
Output is correct |
| 7 |
Correct |
5 ms |
384 KB |
Output is correct |
| 8 |
Correct |
4 ms |
384 KB |
Output is correct |
| 9 |
Runtime error |
6 ms |
640 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 10 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
384 KB |
Output is correct |
| 2 |
Correct |
4 ms |
384 KB |
Output is correct |
| 3 |
Correct |
4 ms |
384 KB |
Output is correct |
| 4 |
Correct |
5 ms |
384 KB |
Output is correct |
| 5 |
Correct |
5 ms |
384 KB |
Output is correct |
| 6 |
Correct |
4 ms |
384 KB |
Output is correct |
| 7 |
Correct |
5 ms |
384 KB |
Output is correct |
| 8 |
Correct |
4 ms |
384 KB |
Output is correct |
| 9 |
Runtime error |
6 ms |
640 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 10 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
384 KB |
Output is correct |
| 2 |
Correct |
4 ms |
384 KB |
Output is correct |
| 3 |
Correct |
4 ms |
384 KB |
Output is correct |
| 4 |
Correct |
5 ms |
384 KB |
Output is correct |
| 5 |
Correct |
5 ms |
384 KB |
Output is correct |
| 6 |
Correct |
4 ms |
384 KB |
Output is correct |
| 7 |
Correct |
5 ms |
384 KB |
Output is correct |
| 8 |
Correct |
4 ms |
384 KB |
Output is correct |
| 9 |
Runtime error |
6 ms |
640 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 10 |
Halted |
0 ms |
0 KB |
- |
