Submission #342608

#	Time	Username	Problem	Language	Result	Execution time	Memory
342608		SeDunion	Bigger segments (IZhO19_segments)	C++17	73 / 100	559 ms	262148 KiB

segments

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 5e5 + 55;

ll a[N], p[N];

ll sum(int l, int r) {
	return p[r] - p[l - 1];
}

using pll = pair<ll,ll>;

const ll INF = 6e14; // 1e9 * 5e5

int L[N * 100], R[N * 100], sz;
pll t[N * 100];

void upd(ll pos, pll val, ll l = -INF, ll r = INF, int v = 0) {
	//cout << v << " " << L[v] << " " << R[v] << endl;;
	t[v] = max(t[v], val);
	if (r - l == 1) {
		return;
	}
	ll m = (l + r) / 2;
	if (pos < m) {
		if (L[v] == 0) L[v] = ++sz;
		upd(pos, val, l, m, L[v]);
	} else {
		if (R[v] == 0) R[v] = ++sz;
		upd(pos, val, m, r, R[v]);
	}
}

pll get(ll Q, ll l = -INF, ll r = INF, int v = 0) {
	if (r <= Q) return t[v];
	if (Q <= l) return {-1, -1};
	ll m = (l + r) / 2;
	pll res = {-1, -1};
	if (L[v]) res = get(Q, l, m, L[v]);
	if (R[v]) res = max(res, get(Q, m, r, R[v]));
	return res;
}

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 >> a[i];
		p[i] = a[i] + p[i - 1];
	}
	ll mx = 1;
	upd(-sum(1, n), {0, 0});
	for (int i = 1 ; i <= n ; ++ i) {
		auto [s, j] = get(-sum(i + 1, n) + 1);
		j++;
		mx = max(mx, s + 1);
		upd(sum(j, i) - sum(i + 1, n), {s + 1, i});
	}
	cout << mx;
}

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