제출 #342593

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
342593		SeDunion	Bigger segments (IZhO19_segments)	C++17	0 / 100	1 ms	364 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>;

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

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