Submission #1024067

#	Time	Username	Problem	Language	Result	Execution time	Memory
1024067		yellowtoad	Bigger segments (IZhO19_segments)	C++17	100 / 100	230 ms	28588 KiB

segments

#include <iostream>
using namespace std;

long long n, a[500010], sum, dp[500010], p[500010], cnt, pos, node[2000010], ps[500010];
bool done;

void update(int id, int x, int y, int pos, long long val) {
	if (x == y) {
		node[id] = val;
		return;
	}
	int mid = (x+y)/2;
	if (pos <= mid) update(id*2,x,mid,pos,val);
	else update(id*2+1,mid+1,y,pos,val);
	node[id] = min(node[id*2],node[id*2+1]);
}

int find(int id, int x, int y, int pos, long long val) {
	if (pos < x) return pos;
	if (node[id] > val) return pos;
	if (x == y) {
		done = 1;
		return x;
	}
	int mid = (x+y)/2, tmp = find(id*2+1,mid+1,y,pos,val);
	return (done ? tmp : find(id*2,x,mid,pos,val));
}

int main() {
	cin >> n;
	for (int i = 1; i <= n; i++) cin >> a[i];
	for (int i = n; i >= 1; i--) ps[i] = ps[i+1]+a[i];
	update(1,0,n,0,-ps[1]);
	for (int i = 1; i <= n; i++) {
		done = 0;
		p[i] = find(1,0,n,i-1,-ps[i+1]);
		update(1,0,n,i,ps[p[i]+1]-ps[i+1]-ps[i+1]);
	}
	pos = n;
	while (pos > 0) {
		pos = p[pos];
		cnt++;
	}
	cout << cnt << endl;
}

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