Submission #1294989

#	Time	Username	Problem	Language	Result	Execution time	Memory
1294989		azamurai	Bigger segments (IZhO19_segments)	C++20	13 / 100	2 ms	588 KiB

segments

#include <bits/stdc++.h>

#define ll long long
#define mp make_pair
#define fi first 
#define se second 
#define Sz(x) (int)x.size()

using namespace std;

const int N = 5e5 + 5;
const int LOG1 = 47;
const int LOG2 = 17;
const ll MXA = 1e14;

struct tree {
	int l, r, mx, pos;
};

int n, sz = 0, dp[N];
ll last[N], pref[N], a[N];
tree t[100000000];

void newnode() {
    sz++;
    t[sz].l = t[sz].r = 0;
    t[sz].mx = t[sz].pos = 0;
}

void upd(ll pos, int val, int val2, int v = 1, ll tl = 1, ll tr = MXA) {
	if (tl == tr) {
		if (val > t[v].mx) {
			t[v].mx = val;
			t[v].pos = val2;
		}
		return;
	}
	ll mid = (tl + tr) / 2;
	if (pos <= mid) {
		if (t[v].l == 0) {
		    newnode();
		    t[v].l = sz;
		}
		upd(pos, val, val2, t[v].l, tl, mid);
	}
 	else {
		if (t[v].r == 0) {
		    newnode();
		    t[v].r = sz;
		}
		upd(pos, val, val2, t[v].r, mid + 1, tr);
	}
	if (t[t[v].l].mx > t[t[v].r].mx) {
		t[v].mx = t[t[v].l].mx;
		t[v].pos = t[t[v].l].pos;
	}
	else {
		t[v].mx = t[t[v].r].mx;
		t[v].pos = t[t[v].r].pos;
	}
}

pair <int,int> merge(pair<int,int> p1, pair<int,int> p2) {
	if (p1.fi > p2.fi) return p1;
	return p2;
}

pair <int,int> get(ll l, ll r, int v = 1, ll tl = 1, ll tr = MXA) {
	if (tl > r || l > tr || v == 0) return mp(0, 0);
	if (tl >= l && tr <= r) return mp(t[v].mx, t[v].pos);
	ll mid = (tl + tr) / 2;
	return merge(get(l, r, t[v].l, tl, mid), get(l, r, t[v].r, mid + 1, tr));
}

void solve() {
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
		pref[i] = pref[i - 1] + a[i];
	}
	newnode();
	dp[1] = 1;
	last[1] = a[1];
	upd(a[1] + a[1], 1, 1);
	for (int i = 2; i <= n; i++) {
		pair <int,int> p = get(1, pref[i]);
		if (p.se == 0) {
			dp[i] = 1;
			last[i] = pref[i];
		}
		else {
			dp[i] = p.fi + 1;
			last[i] = (pref[i] - pref[p.se]);
		}
		upd(pref[i] + last[i], dp[i], i);
	}
	cout << dp[n];
}

signed main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	int tt = 1;
	// cin >> tt;
	while (tt--) {
		solve();
		cout << '\n';
	}
}

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