Submission #333181

#	Time	Username	Problem	Language	Result	Execution time	Memory
333181		emaborevkovic	Bigger segments (IZhO19_segments)	C++17	100 / 100	620 ms	44524 KiB

segments

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
#define pb push_back
#define mp make_pair
#define ff first
#define ss second

const int N = 5*1e5+11;
int n, off = 1;
ll a[N], b[N], z[N], ak[N];
ll t[4*N], lazy[4*N];

void clear (int x) {
	t[x] += lazy[x];
	if (x < off) {
		lazy[x*2] += lazy[x];
		lazy[x*2+1] += lazy[x];
	}
	lazy[x] = 0;
}

ll update(int cf, int ct, int lf, int lt, ll c, int node) {
	clear(node);
	if (cf > lt || ct < lf) return t[node];
	if (cf >= lf && ct <= lt) {
		lazy[node] += c;
		clear(node);
		return t[node];
	}
	int mid = (cf+ct)/2;
	update(cf, mid, lf, lt, c, node*2);
	update(mid+1, ct, lf, lt, c, node*2+1);
	return t[node] = max(t[node*2], t[node*2+1]);
}

int upit(int cf, int ct, int node) {
	clear(node); 
	if (cf != ct) {
		clear(node*2); 
		clear(node*2+1);
	}
	int mid = (cf+ct)/2;
	if (cf == ct) return cf;
	if (t[node*2+1] >= 0) return upit(mid+1, ct, node*2+1);
	return upit(cf, mid, node*2);
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> n;
	while (off < n+1) off *= 2;
	for (int i=0;i<n;i++) {
		cin >> a[i];
		ak[i] = a[i];
		if (i > 0) ak[i] += ak[i-1];
	}
	memset(t, -1, sizeof t);
	b[0] = a[0]; z[0] = -1;
	update(0, off-1, 0, 0, a[0]+1, 1);
	for (int i=1;i<n;i++) {
		update(0, off-1, i, i, -b[i-1]+1, 1);
		update(0, off-1, 0, i, a[i], 1);
		int pos = upit(0, off-1, 1);
		z[i] = pos-1;
		b[i] = ak[i];
		if (pos > 0) b[i] -= ak[pos-1];
	}
	int br = 0;
	int x = n-1;
	while (x >= 0) {
		br++;
		x = z[x];
	}
	cout << br;
	return 0;
}

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