Submission #681412

#	Time	Username	Problem	Language	Result	Execution time	Memory
681412		GusterGoose27	Potatoes and fertilizers (LMIO19_bulves)	C++11	100 / 100	487 ms	144052 KiB

bulves

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

#define int long long

const int MAXN = 5e5;
const ll inf = 1e18;
int n;
int vals[MAXN];
ll pre[MAXN];
int ben[MAXN];

class stree {
public:
	int lp, rp;
	stree *l = nullptr;
	stree *r = nullptr;
	pii mx;
	int lz = 0;
	stree(int lv, int rv) {
		lp = lv;
		rp = rv;
		if (lp < rp) {
			int m = (lp+rp)/2;
			l = new stree(lp, m);
			r = new stree(m+1, rp);
			mx = max(l->mx, r->mx);
		}
		else {
			mx = pii(ben[lp], lp);
		}
	}
	void add_to(int v) {
		lz += v;
		mx.first += v;
	}
	void push() {
		if (l) {
			l->add_to(lz);
			r->add_to(lz);
		}
		lz = 0;
	}
	void upd(int lv, int rv, int v) {
		if (lp > rv || rp < lv) return;
		if (lp >= lv && rp <= rv) {
			return add_to(v);
		}
		push();
		l->upd(lv, rv, v);
		r->upd(lv, rv, v);
		mx = max(l->mx, r->mx);
	}
	pii get_mx(int lv, int rv) {
		if (lp > rv || rp < lv) return pii(-1, -1);
		if (lp >= lv && rp <= rv) return mx;
		push();
		return max(l->get_mx(lv, rv), r->get_mx(lv, rv));
	}
};

stree *mx_tree;

class stree2 {
public:
	int lp, rp;
	stree2 *l = nullptr;
	stree2 *r = nullptr;
	ll mn;
	ll sub = 0;
	stree2(int lv, int rv) {
		lp = lv;
		rp = rv;
		if (lp < rp) {
			int m = (lp+rp)/2;
			l = new stree2(lp, m);
			r = new stree2(m+1, rp);
			mn = min(l->mn, r->mn);
		}
		else {
			if (pre[lp] <= 0) mn = inf;
			else mn = pre[lp];
		}
	}
	void erase() {
		if (mn) return;
		if (lp == rp) {
			mn = inf;
			mx_tree->upd(0, lp, -2);
			return;
		}
		push();
		l->erase();
		r->erase();
		mn = min(l->mn, r->mn);
	}
	void add_to(int v) {
		mn += v;
		sub += v;
		if (mn == 0) {
			erase();
		}
	}
	void push() {
		if (l) {
			l->add_to(sub);
			r->add_to(sub);
		}
		sub = 0;
	}
	void upd(int lv, int rv, int v) {
		if (lp > rv || rp < lv) return;
		if (lp >= lv && rp <= rv) {
			add_to(v);
			return;
		}
		push();
		l->upd(lv, rv, v);
		r->upd(lv, rv, v);
		mn = min(l->mn, r->mn);
	}
	ll query(int lv, int rv) {
		if (lp > rv || rp < lv) return inf;
		if (lp >= lv && rp <= rv) return mn;
		push();
		return min(l->query(lv, rv), r->query(lv, rv));
	}
};

stree2 *beat_tree;

signed main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	cin >> n;
	ll ans = 0;
	for (int i = 0; i < n; i++) {
		int x, y; cin >> x >> y;
		vals[i] = x-y;
		pre[i] += vals[i];
		if (i < n-1) pre[i+1] = pre[i];
		ans += (pre[i] < 0) ? (-pre[i]) : pre[i];
	}
	for (int i = n-1; i >= 0; i--) {
		if (pre[i] <= 0) ben[i]--;
		else ben[i]++;
		if (i) ben[i-1] = ben[i];
	}
	mx_tree = new stree(0, n-1);
	beat_tree = new stree2(0, n-1);
	pii bst = mx_tree->get_mx(0, n-1);
	ll rem = pre[n-1];
	while (bst.first && rem) {
		ll lim = beat_tree->query(bst.second, n-1);
		lim = min(lim, rem);
		ans -= lim*bst.first;
		beat_tree->upd(bst.second, n-1, -lim);
		bst = mx_tree->get_mx(0, n-1);
		rem -= lim;
	}
	cout << ans << "\n";
}

• Subtask 1: 24 / 24
• Subtask 2: 10 / 10
• Subtask 3: 20 / 20
• Subtask 4: 10 / 10
• Subtask 5: 36 / 36