Submission #338963

#	Time	Username	Problem	Language	Result	Execution time	Memory
338963		nandonathaniel	Bigger segments (IZhO19_segments)	C++14	100 / 100	196 ms	19436 KiB

segments

#include<bits/stdc++.h>
using namespace std;
const int MAXN=500005;
const long long INF=1e18;

long long pref[MAXN],tree[4*MAXN];
int dp[MAXN];

void build(int now,int L,int R){
	if(L==R){
		tree[now]=INF;
		return;
	}
	int mid=(L+R)/2;
	build(2*now,L,mid);
	build(2*now+1,mid+1,R);
	tree[now]=min(tree[2*now],tree[2*now+1]);
}
 
void update(int now,int L,int R,int pos,long long val){
	if(L==R){
		tree[now]=val;
		return;
	}
	int mid=(L+R)/2;
	if(pos<=mid)update(2*now,L,mid,pos,val);
	else update(2*now+1,mid+1,R,pos,val);
	tree[now]=min(tree[2*now],tree[2*now+1]);
}

int query(int now,int L,int R,long long val){
	if(L==R)return L;
	int mid=(L+R)/2;
	if(tree[2*now+1]<=val)return query(2*now+1,mid+1,R,val);
	else return query(2*now,L,mid,val);
}
 
int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int n;
	cin >> n;
	for(int i=1;i<=n;i++){
		cin >> pref[i];
		pref[i]+=pref[i-1];
	}
	build(1,1,n);
	//dp[i] brp segment maksimum yang dpt dibuat dari 1...i
	//dp[i] non decreasing
	for(int i=1;i<=n;i++){
		int prv;
		if(tree[1]>pref[i])prv=0;
		else{
			//find rightmost idx such that <=pref[i]
			prv=query(1,1,n,pref[i]);
		}
		dp[i]=dp[prv]+1;
		update(1,1,n,i,2*pref[i]-pref[prv]);
	}
	cout << dp[n] << '\n';
	return 0;
}

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