This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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, ll pos, pii new_val) {
if (t == nullptr)
return 0;
if (pos < t->x)
return exist(t->l, pos, new_val);
if (pos > t->x)
return exist(t->r, pos, new_val);
if (pos == t->x) {
t->val = max(t->val, new_val);
t->mx = max(t->mx, t->val);
return 1;
}
update(t);
}
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 < ll > 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);
if (!exist(t, sum[i] + pref[i], mp(dp[i], i))) {
k = split(t, sum[i] + pref[i]);
t = merge(merge(k.fr, nw), k.sc);
}
}
cout << dp[n];
return 0;
}
Compilation message (stderr)
segments.cpp: In function 'bool exist(treap*, ll, pii)':
segments.cpp:96:1: warning: control reaches end of non-void function [-Wreturn-type]
}
^
# | 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... |