Submission #342588

#	Time	Username	Problem	Language	Result	Execution time	Memory
342588		SeDunion	Bigger segments (IZhO19_segments)	C++17	13 / 100	3 ms	896 KiB

segments

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

//
//
int a[N], p[N];

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

using pll = pair<ll,ll>;

map<ll,pll> mp;

const ll INF = 1e17;
const ll HALF = INF / 2;

void upd(ll a, pll b) {
	a += HALF;
	while (a < INF) {
		mp[a] = max(mp[a], b);
		a |= a + 1;
	}
}

pll get(ll a) {
	a += HALF;
	pll b = {-1, -1};
	while (a >= 0) {
		if (mp.count(a)) b = max(b, mp[a]);
		a &= a + 1;
		a--;
	}
	return b;
}

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));
		j++;
		mx = max(mx, s + 1);
		upd(sum(j, i) - sum(i + 1, n), {s + 1, i});
		//cout << i << " " << s << " " << j << " " << sum(j, i) - sum(i + 1, n) << "\n";
	}
	cout << mx;
}

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