Submission #172976

#TimeUsernameProblemLanguageResultExecution timeMemory
172976LinusTorvaldsFanBigger segments (IZhO19_segments)C++14
37 / 100
292 ms124324 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; struct Node{ pair<int,int>val; ll l, r; Node*left; Node*right; Node(ll _l, ll _r) { val={0,0}; l=_l; r=_r; left=nullptr; right=nullptr; } }; pair<int,int>get_val(Node *root){ if(root==nullptr)return make_pair(0,0); return root->val; } void update(Node *root, ll p, int x, int y) { if(root->l==p && root->r==p){ root->val=max(make_pair(x,y),root->val); return; } ll m=(root->l+root->r)/2; if(root->l<=p&&p<=m){ if(root->left==nullptr){ root->left=new Node(root->l,m); } update(root->left,p,x,y); } if(m+1<=p&&p<=root->r){ if(root->right==nullptr){ root->right=new Node(m+1,root->r); } update(root->right,p,x,y); } root->val=max(get_val(root->left),get_val(root->right)); } pair<int,int> get(Node *root, ll l, ll r){ if(l>root->r || root->l>r) { return {0,0}; } if(l<=root->l && root->r<=r){ return root->val; } pair<int,int> ans={0,0}; if(root->right!=nullptr){ ans=max(ans,get(root->right,l,r)); } if(root->left!=nullptr){ ans=max(ans,get(root->left,l,r)); } return ans; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); int n; cin>>n; vector<int>a(n); for(int i=0;i<n;i++)cin>>a[i]; vector<ll>pr(n+1); for(int i=0;i<n;i++)pr[i+1]=pr[i]+a[i]; vector<int>ans(n); vector<ll> ans_sum(n); ll sum=0; for(int i=0;i<n;i++){ sum+=a[i]; ans_sum[i]=sum; ans[i]=1; } Node *tree=new Node(0,1e13); update(tree,ans_sum[0]+pr[1],ans[0],0); for(int i=1;i<n;i++){ if(n<=100){ for(int j=i-1;j>=0;j--){ if(pr[i+1]>=ans_sum[j]+pr[j+1]){ if(ans[i]<ans[j]+1){ ans[i]=ans[j]+1; ans_sum[i]=pr[i+1]-pr[j+1]; } } } //cout<<ans[i]<<" "; //cout<<ans_sum[i]<<" "; //cout<<endl; } else{ auto t=get(tree,0,pr[i+1]); if(pr[i+1]>=ans_sum[t.second]+pr[t.second+1]){ if(ans[i]<t.first+1){ ans[i]=t.first+1; ans_sum[i]=pr[i+1]-pr[t.second+1]; } } update(tree,ans_sum[i]+pr[i+1],ans[i],i); } //cout<<ans[i]<<" "; //cout<<ans_sum[i]<<" "; //cout<<endl; } cout<<ans[n-1]; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...