이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include"bits/stdc++.h"
using namespace std;
#define ll long long
#define endl "\n"
#define fastio ios_base::sync_with_stdio(false)
#define inf LLONG_MAX
const int lmt=5e5+5;
array<ll,3>t[lmt];
int main(){
fastio;
int n;
cin>>n;
for(int i=0;i<=n;i++){
t[i][0]=-inf;
}
ll pre[n+1],dp[n+1],ans[n+1];
pre[0]=0;
for(int i=1;i<=n;i++){
ll x;
cin>>x;
pre[i]=pre[i-1]+x;
}
set<array<ll,3>>s;
for(int i=1;i<=n;i++){
auto it=s.lower_bound({pre[n]-pre[i],-inf,-inf});
if(it==s.end()){
dp[i]=pre[i],ans[i]=1;
//t.insert({dp[i],-i,pre[n]-pre[i]-dp[i]});
int ii=(int)ans[i];
if(pre[n]-pre[i]-dp[i]>t[ii][0]){
s.erase({t[ii][0],t[ii][1],t[ii][2]});
t[ii][0]=pre[n]-pre[i]-dp[i],t[ii][1]=-i,t[ii][2]=dp[i];
s.insert({pre[n]-pre[i]-dp[i],-i,dp[i]});
}
}else{
int idx=-(*it)[1];
dp[i]=pre[i]-pre[idx],ans[i]=ans[idx]+1;
/*while(!t.empty()){
it=t.end();
it--;
if(dp[i]<(*it)[0]){
s.erase({ (*it)[2], (*it)[1], (*it)[0] });
t.erase(it);
}else break;
}*/
int ii=(int)ans[i];
if(pre[n]-pre[i]-dp[i]>t[ii][0]){
s.erase({t[ii][0],t[ii][1],t[ii][2]});
t[ii][0]=pre[n]-pre[i]-dp[i],t[ii][1]=-i,t[ii][2]=dp[i];
s.insert({pre[n]-pre[i]-dp[i],-i,dp[i]});
}
//t.insert({dp[i],-i,pre[n]-pre[i]-dp[i]});
}
//cout<<pre[n]-pre[i]-dp[i]<<" "<<ans[i]<<" "<<dp[i]<<endl;
}
cout<<ans[n]<<endl;
return 0;
}
# | 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... |