Submission #641601

#	Time	Username	Problem	Language	Result	Execution time	Memory
641601		andreast12	Bigger segments (IZhO19_segments)	C++17	100 / 100	149 ms	19264 KiB

segments

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fi first
#define se second
#define pb push_back
const int mod=998244353, maxn=5e5+5;
int n, a, dp[maxn], prv;
ll pf[maxn], tree[4*maxn], inf=1e18;

void build(int now, int tl, int tr) {
	if(tl==tr) {
		tree[now]=(tl)?inf:0;
		return;
	}
	int mid=(tl+tr)/2;
	build(now*2, tl, mid);
	build(now*2+1, mid+1, tr);
	tree[now]=min(tree[now*2], tree[now*2+1]);
}

int query(int now, int tl, int tr, ll val) {
	if(tl==tr) return tl;
	int mid=(tl+tr)/2;
	if(tree[now*2+1]<=val) return query(now*2+1, mid+1, tr, val);
	return query(now*2, tl, mid, val);
}

void update(int now, int tl, int tr, int pos, ll val) {
	if(tl==tr) {
		tree[now]=val;
		return;
	}
	int mid=(tl+tr)/2;
	if(pos<=mid) update(now*2, tl, mid, pos, val);
	else update(now*2+1, mid+1, tr, pos, val);
	tree[now]=min(tree[now*2], tree[now*2+1]);
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	cin >> n;
	build(1, 0, n);
	for(int i=1; i<=n; i++) {
		cin >> a;
		pf[i]=pf[i-1]+a;
		prv=query(1, 0, n, pf[i]);
		dp[i]=dp[prv]+1;
		// cout << i << ": " << prv << ' ' << dp[i] << '\n';
		update(1, 0, n, i, pf[i]*2-pf[prv]);
	}
	cout << dp[n] << '\n';
}

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