Submission #1329813

#TimeUsernameProblemLanguageResultExecution timeMemory
1329813viduxBitaro the Brave 2 (JOI25_ho_t2)C++17
0 / 100
593 ms55212 KiB
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vl;
typedef pair<ll, ll> pll;
const ll INF = 1e18;
enum Op { NONE, SET, ADD };
struct Tag { Op op = NONE; ll v = 0; };
struct Seg {
	int n;
	vl t;
	vector<Tag> lz;
	Seg(int sz) {
		n = sz;
		t.resize(4*n);
		lz.resize(4*n);
	}
private:
	void apply(int id, Tag q) {
		if (q.op == SET) {
			lz[id] = q;
			t[id] = q.v;
		}
		if (q.op == ADD) {
			if (lz[id].op != SET) lz[id].op = ADD;
			lz[id].v += q.v;
			t[id] += q.v;
		}
	}
	void push_down(int id) {
		if (lz[id].op == NONE) return;
		apply(id*2, lz[id]);
		apply(id*2+1, lz[id]);
		lz[id] = Tag();
	}
	void update(int id, int l, int r, int ql, int qr, Tag q) {
		if (l >= qr || r <= ql) return;
		if (ql <= l && r <= qr) apply(id, q);
		else {
			push_down(id);
			int m = (l+r)/2;
			update(id*2, l, m, ql, qr, q);
			update(id*2+1, m, r, ql, qr, q);
			t[id] = min(t[id*2], t[id*2+1]);
		}
	}
	ll query(int id, int l, int r, int ql, int qr) {
		if (l >= qr || r <= ql) return INF;
		if (ql <= l && r <= qr) return t[id];
		push_down(id);
		int m = (l+r)/2;
		return min(query(id*2, l, m, ql, qr), query(id*2+1, m, r, ql, qr));
	}
public:
	void update(int l, int r, Tag q) {
		update(1, 0, n, l, r, q);
	}
	ll query(int l, int r) {
		return query(1, 0, n, l, r);
	}
};
int main() {
	ll n; cin >> n;
	vl a(n), b(n);
	for (int i = 0; i < n; i++) cin >> a[i];
	for (int i = 0; i < n; i++) cin >> b[i];
	Seg seg(n);
	for (int i = 0; i < n; i++) seg.update(i+1, n, Tag{ADD, b[i]}), seg.update(i, i+1, Tag{ADD, -a[i]});
	ll ans = max(ans, seg.query(0, n));
	ll all = accumulate(b.begin(), b.end(), 0ll);
	for (int i = 1; i < n; i++) {
		seg.update(i, n, Tag{ADD, -b[i-1]});
		seg.update(0, i-1, Tag{ADD, -b[i-1]});
		seg.update(i-1, i, Tag{SET, all-a[i-1]-b[i-1]});
		ans = max(ans, seg.query(0, n));
	}
	cout << max(-ans, 0ll) << endl;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...