Submission #265542

#	Time	Username	Problem	Language	Result	Execution time	Memory
265542		Segtree	Bigger segments (IZhO19_segments)	C++14	100 / 100	88 ms	28884 KiB

segments

#include<iostream>
#include<algorithm>
#include<vector>
#include<fstream>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
#define rep(i,n) for(int i=0;i<n;i++)
#define all(x) x.begin(),x.end()
#define chmin(a,b) a=min(a,b)
#define chmax(a,b) a=max(a,b)
#define N 500010
ll n,a[N],s[N];
ll dp[N],dq[N];
int main(){
	cin.tie(0);
	ios::sync_with_stdio(0);
	cin>>n;
	rep(i,n)cin>>a[i];
	s[0]=0;
	rep(i,n)s[i+1]=s[i]+a[i];
	rep(i,n+1)dp[i]=1e18;
	dp[0]=0;
	dq[0]=0;
	//for(int k=1;k<=n;k++){
		vector<ll> score,place;
		//scoreは単調増加
		for(int i=0;i<=n;i++){
			ll l=-1,r=score.size(),mid;
			while(l<r-1){
				mid=(l+r)>>1;
				if(s[i]>=score[mid])l=mid;
				else r=mid;
			}
			if(l>=0){
				dp[i]=s[i]-s[place[l]];
				dq[i]=dq[place[l]]+1;
			}
			ll sc=dp[i]+s[i];
			while(score.size()>0){
				if(score.back()>=sc){
					score.pop_back();
					place.pop_back();
				}
				else break;
			}
			score.push_back(sc);
			place.push_back(i);
		}
	//}
	cout<<dq[n]<<endl;
}

• Subtask 1: 13 / 13
• Subtask 2: 14 / 14
• Subtask 3: 10 / 10
• Subtask 4: 36 / 36
• Subtask 5: 27 / 27