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 int long long
using namespace std;
const int N = (int)1e6 + 5;
const int INF = (int)1e18;
int a[N];
int tree[N * 4], lz[N * 4];
int pref[N];
int dp[N];
void mk(int &a, int other) {
if (!a) {
a = other;
return;
}
if (dp[a - 1] == dp[other - 1]) {
a = max(a, other);
}
if (dp[a - 1] < dp[other - 1]) {
a = other;
}
}
int get_sum(int l, int r) {
return pref[r] - pref[l - 1];
}
void push(int v, int tl, int tr) {
if (!lz[v]) {
return;
}
if (tl != tr) {
mk(lz[v + v], lz[v]);
mk(lz[v + v + 1], lz[v]);
} else {
int x = lz[v];
if (dp[x - 1] + 1 == dp[tl]) {
tree[v] = max(tree[v], lz[v]);
}
if (dp[x - 1] + 1 > dp[tl]) {
tree[v] = x;
dp[tl] = dp[x - 1] + 1;
}
}
}
void upd(int l, int r, int val, int v = 1, int tl = 1, int tr = N) {
push(v, tl, tr);
if (l <= tl && tr <= r) {
lz[v] = val;
push(v, tl, tr);
return;
}
if (l > tr || tl > r) {
return;
}
int mid = tl + tr >> 1;
upd(l, r, val, v + v, tl, mid);
upd(l, r, val, v + v + 1, mid + 1, tr);
}
int get(int pos, int v = 1, int tl = 1, int tr = N) {
push(v, tl, tr);
if (tl == tr) {
return tree[v];
}
int mid = tl + tr >> 1;
if (pos <= mid) {
return get(pos, v + v, tl, mid);
} else {
return get(pos, v + v + 1, mid + 1, tr);
}
}
void build(int v, int tl, int tr) {
if (tl == tr) {
tree[v] = 1;
dp[tl] = 1;
return;
}
int mid = tl + tr >> 1;
build(v + v, tl, mid);
build(v + v + 1, mid + 1, tr);
}
main() {
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
scanf("%lld", &a[i]);
pref[i] = pref[i - 1] + a[i];
}
build(1, 1, n);
for (int i = 1; i <= n; i++) {
int best = get(i);
int l = i, r = n + 1;
while (r - l > 1) {
int mid = l + r >> 1;
if (get_sum(i + 1, mid) >= get_sum(best, i)) {
r = mid;
} else {
l = mid;
}
}
if (r <= n) {
upd(r, n, i + 1);
}
}
cout << dp[n];
}
Compilation message (stderr)
segments.cpp: In function 'void upd(long long int, long long int, long long int, long long int, long long int, long long int)':
segments.cpp:58:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid = tl + tr >> 1;
~~~^~~~
segments.cpp: In function 'long long int get(long long int, long long int, long long int, long long int)':
segments.cpp:68:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid = tl + tr >> 1;
~~~^~~~
segments.cpp: In function 'void build(long long int, long long int, long long int)':
segments.cpp:82:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid = tl + tr >> 1;
~~~^~~~
segments.cpp: At global scope:
segments.cpp:87:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
main() {
^
segments.cpp: In function 'int main()':
segments.cpp:101:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid = l + r >> 1;
~~^~~
segments.cpp:91:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld", &a[i]);
~~~~~^~~~~~~~~~~~~~~
# | 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... |