#include <bits/stdc++.h>
#define F first
#define S second
using namespace std;
const int N = 5e5 + 5;
const long long M = (long long)1e15;
int n,a[N];
long long pref[N];
pair<long long,long long> dp[N];
int slow(){
for(int i = 1; i <= n; i++) pref[i] = pref[i - 1] + a[i];
dp[1] = {1,a[1]};
for(int i = 2; i <= n; i++){
dp[i] = {dp[i - 1].F,dp[i - 1].S + a[i]};
for(int j = i - 1; j >= 1; j--){
if(pref[i] - pref[j] >= dp[j].S && dp[i].F <= dp[j].F + 1){
dp[i] = {dp[j].F + 1,pref[i] - pref[j]};
break;
}
}
}
return dp[n].F;
}
map< long long,pair<long long,long long> > t;
void upd(long long pos,pair<long long,long long> val,long long v = 1,long long tl = 1,long long tr = M){
if(tl == tr){
t[v] = val;
return;
}
long long tm = tl + tr >> 1;
if(pos <= tm) upd(pos,val,v + v,tl,tm);
else upd(pos,val,v + v + 1,tm + 1,tr);
t[v] = max(t[v + v],t[v + v + 1]);
}
pair<long long,long long> get(long long l,long long r,long long v = 1,long long tl = 1,long long tr = M){
if(l <= tl && tr <= r) return t[v];
if(tl > r || tr < l) return {0,0};
long long tm = tl + tr >> 1;
return max(get(l,r,v + v,tl,tm),get(l,r,v + v + 1,tm + 1,tr));
}
int fast(){
for(int i = 1; i <= n; i++) pref[i] = pref[i - 1] + a[i],dp[i] = {0,0};
dp[1] = {1,a[1]};
upd(pref[1] + dp[1].S,{dp[1].F,1});
// update in position pref[i] + dp[i].second -> {dp[i].first,postition}
for(int i = 2; i <= n; i++){
dp[i] = {dp[i - 1].F,dp[i - 1].S + a[i]};
pair<long long,long long> cur = get(1,pref[i]);
cerr << cur.F << " " << cur.S << endl;
if(cur.F > 0) dp[i] = {cur.F + 1,pref[i] - pref[cur.S]};
upd(pref[i] + dp[i].S,{dp[i].F,i});
}
return dp[n].F;
}
int main(){
ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin >> n;
for(int i = 1; i <= n; i++) cin >> a[i];
/*
cout << "Exact Solution,SLOW " << slow() << endl;
cout << "Not Exact,FAST " << fast();
*/
cout << fast();
return 0;
}
Compilation message
segments.cpp: In function 'void upd(long long int, std::pair<long long int, long long int>, long long int, long long int, long long int)':
segments.cpp:39:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
long long tm = tl + tr >> 1;
~~~^~~~
segments.cpp: In function 'std::pair<long long int, long long int> get(long long int, long long int, long long int, long long int, long long int)':
segments.cpp:48:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
long long tm = tl + tr >> 1;
~~~^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
