oj.uz

Submission #551583

# Submission time Handle Problem Language Result Execution time Memory
551583 2022-04-21T05:24:07 Z skittles1412 Ants and Sugar (JOI22_sugar) C++17
6 / 100
 4000 ms 90300 KB 
#include "bits/extc++.h"

using namespace std;

template <typename T>
void dbgh(const T& t) {
	cerr << t << endl;
}

template <typename T, typename... U>
void dbgh(const T& t, const U&... u) {
	cerr << t << " | ";
	dbgh(u...);
}

#ifdef DEBUG
#define dbg(...)                                           \
	cerr << "L" << __LINE__ << " [" << #__VA_ARGS__ << "]" \
		 << ": ";                                          \
	dbgh(__VA_ARGS__)
#else
#define cerr   \
	if (false) \
	cerr
#define dbg(...)
#endif

#define endl "\n"
#define long int64_t
#define sz(x) int((x).size())

struct Node {
	array<array<array<long, 2>, 2>, 3> v;

	friend Node operator+(const Node& x, const Node& y) {
		Node ans = inf();
		for (int a = 0; a < 3; a++) {
			for (int b = 0; b < 2; b++) {
				for (int c = 0; c < 2; c++) {
					for (int d = 0; d < 3; d++) {
						for (int e = 0; e < 2; e++) {
							auto& cur = ans.v[min(a + d, 2)][b][e];
							cur = max(cur, x.v[a][b][c] + y.v[d][c][e]);
						}
					}
				}
			}
		}
		return ans;
	}

	static Node inf() {
		Node ans {};
		for (auto& a : ans.v) {
			for (auto& b : a) {
				for (auto& c : b) {
					c = -1e18;
				}
			}
		}
		return ans;
	}

	static Node def() {
		Node ans = inf();
		ans.v[0][0][0] = ans.v[0][1][1] = ans.v[0][0][1] = ans.v[1][1][0] = 0;
		return ans;
	}
};

struct Lazy {
	long ax, bx;

	Lazy& operator+=(const Lazy& x) {
		ax += x.ax;
		bx += x.bx;
		return *this;
	}

	friend Lazy operator+(Lazy a, const Lazy& b) {
		return a += b;
	}

	Node apply(Node n) const {
		for (int i = 0; i < 3; i++) {
			for (auto& a : n.v[i]) {
				for (auto& b : a) {
					b += bx * i;
				}
			}
			n.v[i][0][1] -= ax;
			n.v[i][1][0] += ax;
		}
		return n;
	}

	static Lazy identity() {
		return {0, 0};
	}
};

struct TNode {
	Node v;
	Lazy x;
	int lc, rc;

	void maintain();

	static TNode def() {
		return {Node::def(), Lazy::identity(), 0, 0};
	}
} heap[(512 << 20) / sizeof(TNode)];
int hind = 1;

void TNode::maintain() {
	v = x.apply(heap[lc].v + heap[rc].v);
}

int midpoint(int l, int r) {
	long x = long(l) + r;
	if (x < 0) {
		return int((x - 1) / 2);
	}
	return int(x / 2);
}

void update(int& o, int l, int r, int ql, int qr, const Lazy& x) {
	if (!o) {
		heap[hind] = TNode::def();
		o = hind++;
	}
	auto& n = heap[o];
	if (ql <= l && r <= qr) {
		n.x += x;
	} else {
		int mid = midpoint(l, r);
		if (ql <= mid) {
			update(n.lc, l, mid, ql, qr, x);
		}
		if (mid < qr) {
			update(n.rc, mid + 1, r, ql, qr, x);
		}
	}
	n.maintain();
}

const int maxa = 2e9 + 5;

int root;

void update(int l, int r, const Lazy& x) {
	update(root, -maxa, maxa, l, r, x);
}

void solve() {
	heap[0] = TNode::def();
	int q, k;
	cin >> q >> k;
	long ants = 0;
	while (q--) {
		int t, ind, x;
		cin >> t >> ind >> x;
		if (t == 1) {
			ants += x;
			update(ind, maxa, {x, 0});
		} else {
			update(ind + k, maxa, {-x, 0});
			update(ind - k, ind + k - 1, {0, -x});
		}
		auto& n = heap[root].v;
		long ans = 0;
		for (auto& a : n.v) {
			ans = max(ans, a[0][0]);
		}
		dbg(ants, ans);
		cout << ants - ans << endl;
	}
}

int main() {
	cin.tie(nullptr);
	ios_base::sync_with_stdio(false);
	cin.exceptions(ios::failbit);
	solve();
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 22 ms 832 KB Output is correct
7 Correct 21 ms 852 KB Output is correct
8 Correct 13 ms 724 KB Output is correct
9 Correct 10 ms 724 KB Output is correct
10 Correct 43 ms 14256 KB Output is correct
11 Correct 44 ms 15164 KB Output is correct
12 Correct 48 ms 15332 KB Output is correct
13 Correct 50 ms 15184 KB Output is correct
14 Correct 68 ms 20712 KB Output is correct
15 Correct 65 ms 20580 KB Output is correct
16 Correct 29 ms 9756 KB Output is correct
17 Correct 28 ms 9556 KB Output is correct
18 Correct 27 ms 9532 KB Output is correct
19 Correct 44 ms 15052 KB Output is correct
20 Correct 27 ms 9576 KB Output is correct
21 Correct 46 ms 14424 KB Output is correct
22 Correct 26 ms 9532 KB Output is correct
23 Correct 47 ms 14156 KB Output is correct
24 Correct 27 ms 9556 KB Output is correct
25 Correct 51 ms 15268 KB Output is correct

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 3860 ms 64328 KB Output is correct
5 Correct 2270 ms 51092 KB Output is correct
6 Execution timed out 4089 ms 79412 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 2139 ms 42380 KB Output is correct
3 Correct 2946 ms 58556 KB Output is correct
4 Execution timed out 4081 ms 90300 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 22 ms 832 KB Output is correct
7 Correct 21 ms 852 KB Output is correct
8 Correct 13 ms 724 KB Output is correct
9 Correct 10 ms 724 KB Output is correct
10 Correct 43 ms 14256 KB Output is correct
11 Correct 44 ms 15164 KB Output is correct
12 Correct 48 ms 15332 KB Output is correct
13 Correct 50 ms 15184 KB Output is correct
14 Correct 68 ms 20712 KB Output is correct
15 Correct 65 ms 20580 KB Output is correct
16 Correct 29 ms 9756 KB Output is correct
17 Correct 28 ms 9556 KB Output is correct
18 Correct 27 ms 9532 KB Output is correct
19 Correct 44 ms 15052 KB Output is correct
20 Correct 27 ms 9576 KB Output is correct
21 Correct 46 ms 14424 KB Output is correct
22 Correct 26 ms 9532 KB Output is correct
23 Correct 47 ms 14156 KB Output is correct
24 Correct 27 ms 9556 KB Output is correct
25 Correct 51 ms 15268 KB Output is correct
26 Correct 0 ms 212 KB Output is correct
27 Correct 1 ms 212 KB Output is correct
28 Correct 0 ms 212 KB Output is correct
29 Correct 3860 ms 64328 KB Output is correct
30 Correct 2270 ms 51092 KB Output is correct
31 Execution timed out 4089 ms 79412 KB Time limit exceeded
32 Halted 0 ms 0 KB -