Submission #1107914

#	Time	Username	Problem	Language	Result	Execution time	Memory
1107914		alex_2008	Bigger segments (IZhO19_segments)	C++14	100 / 100	200 ms	36476 KiB

segments

#include <bits/stdc++.h>
#define ff first
#define ss second
typedef long long ll;
using namespace std;
const int N = 5e5 + 10;
const ll INF = 2e18 + 10;
ll pref[N];
pair <ll, ll> dp[N];
ll dpp[N];
ll tree[4 * N];
int n;
void upd(int v, int tl, int tr, int pos, ll val) {
	if (tl == tr) {
		tree[v] = val;
		return;
	}
	int tm = (tl + tr) / 2;
	if (pos <= tm) upd(2 * v, tl, tm, pos, val);
	else upd(2 * v + 1, tm + 1, tr, pos, val);
	tree[v] = min(tree[2 * v], tree[2 * v + 1]);
}
int get(ll p) {
	int v = 1, tl = 1, tr = n + 1;
	while (tl != tr) {
		int tm = (tl + tr) / 2;
		if (tree[2 * v + 1] <= p) {
			v = 2 * v + 1;
			tl = tm + 1;
		}
		else {
			v = 2 * v;
			tr = tm;
		}
	}
	return tl;
}
int main() {
	cin >> n;
	for (int i = 1; i <= 4 * n + 4; i++) {
		tree[i] = INF;
	}
	for (int i = 1; i <= n; i++) {
		cin >> pref[i];
		pref[i] += pref[i - 1];
	}
	dp[0] = { 0, 0 };
	dpp[0] = 0;
	upd(1, 1, n + 1, 0 + 1, dpp[0]);
	for (int i = 1; i <= n; i++) {
		int ind = get(pref[i]) - 1;
		dp[i] = { dp[ind].first + 1, pref[i] - pref[ind] };
		dpp[i] = dp[i].ss + pref[i];
		upd(1, 1, n + 1, i + 1, dpp[i]);
	}
	cout << dp[n].ff << "\n";
}

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