답안 #681408

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
681408	2023-01-13T03:35:08 Z	GusterGoose27	Potatoes and fertilizers (LMIO19_bulves)	C++11	64 / 100	452 ms	108888 KB

bulves

#include <bits/stdc++.h>

using namespace std;

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

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;

int 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.0 / 24.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	340 KB	Output is correct
2	Correct	1 ms	852 KB	Output is correct
3	Correct	2 ms	980 KB	Output is correct
4	Correct	15 ms	10780 KB	Output is correct
5	Correct	31 ms	21336 KB	Output is correct
6	Correct	82 ms	54548 KB	Output is correct
7	Correct	161 ms	108700 KB	Output is correct
8	Correct	155 ms	106840 KB	Output is correct
9	Correct	148 ms	106160 KB	Output is correct
10	Correct	129 ms	103904 KB	Output is correct
11	Correct	154 ms	103940 KB	Output is correct

Subtask #2

10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	340 KB	Output is correct
2	Correct	1 ms	852 KB	Output is correct
3	Correct	2 ms	980 KB	Output is correct
4	Correct	15 ms	10780 KB	Output is correct
5	Correct	31 ms	21336 KB	Output is correct
6	Correct	82 ms	54548 KB	Output is correct
7	Correct	161 ms	108700 KB	Output is correct
8	Correct	155 ms	106840 KB	Output is correct
9	Correct	148 ms	106160 KB	Output is correct
10	Correct	129 ms	103904 KB	Output is correct
11	Correct	154 ms	103940 KB	Output is correct
12	Correct	43 ms	27336 KB	Output is correct
13	Correct	94 ms	65340 KB	Output is correct
14	Correct	180 ms	108888 KB	Output is correct
15	Correct	139 ms	106860 KB	Output is correct
16	Correct	152 ms	106184 KB	Output is correct
17	Correct	160 ms	103964 KB	Output is correct
18	Correct	2 ms	852 KB	Output is correct

Subtask #3

20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	340 KB	Output is correct
2	Correct	1 ms	852 KB	Output is correct
3	Correct	2 ms	852 KB	Output is correct
4	Correct	1 ms	340 KB	Output is correct
5	Correct	1 ms	468 KB	Output is correct
6	Correct	2 ms	584 KB	Output is correct
7	Correct	3 ms	856 KB	Output is correct
8	Correct	2 ms	852 KB	Output is correct
9	Correct	2 ms	852 KB	Output is correct
10	Correct	1 ms	852 KB	Output is correct

Subtask #4

10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	340 KB	Output is correct
2	Correct	1 ms	852 KB	Output is correct
3	Correct	2 ms	980 KB	Output is correct
4	Correct	1 ms	340 KB	Output is correct
5	Correct	1 ms	468 KB	Output is correct
6	Correct	2 ms	584 KB	Output is correct
7	Correct	3 ms	856 KB	Output is correct
8	Correct	2 ms	852 KB	Output is correct
9	Correct	2 ms	852 KB	Output is correct
10	Correct	1 ms	852 KB	Output is correct
11	Correct	2 ms	852 KB	Output is correct
12	Correct	2 ms	724 KB	Output is correct
13	Correct	2 ms	980 KB	Output is correct
14	Correct	2 ms	980 KB	Output is correct
15	Correct	2 ms	980 KB	Output is correct
16	Correct	2 ms	980 KB	Output is correct
17	Correct	2 ms	848 KB	Output is correct
18	Correct	2 ms	980 KB	Output is correct

Subtask #5

0 / 36.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	340 KB	Output is correct
2	Correct	1 ms	852 KB	Output is correct
3	Correct	2 ms	980 KB	Output is correct
4	Correct	1 ms	340 KB	Output is correct
5	Correct	1 ms	468 KB	Output is correct
6	Correct	2 ms	584 KB	Output is correct
7	Correct	3 ms	856 KB	Output is correct
8	Correct	2 ms	852 KB	Output is correct
9	Correct	2 ms	852 KB	Output is correct
10	Correct	1 ms	852 KB	Output is correct
11	Correct	15 ms	10780 KB	Output is correct
12	Correct	31 ms	21336 KB	Output is correct
13	Correct	82 ms	54548 KB	Output is correct
14	Correct	161 ms	108700 KB	Output is correct
15	Correct	155 ms	106840 KB	Output is correct
16	Correct	148 ms	106160 KB	Output is correct
17	Correct	129 ms	103904 KB	Output is correct
18	Correct	154 ms	103940 KB	Output is correct
19	Correct	43 ms	27336 KB	Output is correct
20	Correct	94 ms	65340 KB	Output is correct
21	Correct	180 ms	108888 KB	Output is correct
22	Correct	139 ms	106860 KB	Output is correct
23	Correct	152 ms	106184 KB	Output is correct
24	Correct	160 ms	103964 KB	Output is correct
25	Correct	2 ms	724 KB	Output is correct
26	Correct	2 ms	980 KB	Output is correct
27	Correct	2 ms	980 KB	Output is correct
28	Correct	2 ms	980 KB	Output is correct
29	Correct	2 ms	980 KB	Output is correct
30	Correct	2 ms	848 KB	Output is correct
31	Correct	2 ms	980 KB	Output is correct
32	Correct	2 ms	852 KB	Output is correct
33	Correct	87 ms	27388 KB	Output is correct
34	Correct	225 ms	65312 KB	Output is correct
35	Correct	404 ms	108756 KB	Output is correct
36	Correct	452 ms	106396 KB	Output is correct
37	Incorrect	140 ms	106828 KB	Output isn't correct
38	Halted	0 ms	0 KB	-