oj.uz

Submission #551580

# Submission time Handle Problem Language Result Execution time Memory
551580 2022-04-21T05:21:01 Z skittles1412 Ants and Sugar (JOI22_sugar) C++17
6 / 100
 4000 ms 125392 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};
	}
};

vector<TNode> heap {TNode::def()};

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

void reserve() {
	while (heap.size() + 10000 > heap.capacity()) {
		heap.reserve(heap.capacity() * 2);
	}
}

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) {
		o = sz(heap);
		heap.push_back(TNode::def());
	}
	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) {
	reserve();
	update(root, -maxa, maxa, l, r, x);
}

void solve() {
	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 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 452 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 30 ms 784 KB Output is correct
7 Correct 21 ms 836 KB Output is correct
8 Correct 13 ms 760 KB Output is correct
9 Correct 12 ms 708 KB Output is correct
10 Correct 50 ms 14260 KB Output is correct
11 Correct 64 ms 28860 KB Output is correct
12 Correct 57 ms 28884 KB Output is correct
13 Correct 58 ms 28828 KB Output is correct
14 Correct 79 ms 28784 KB Output is correct
15 Correct 78 ms 28820 KB Output is correct
16 Correct 34 ms 13412 KB Output is correct
17 Correct 54 ms 13392 KB Output is correct
18 Correct 34 ms 13416 KB Output is correct
19 Correct 58 ms 28892 KB Output is correct
20 Correct 39 ms 13388 KB Output is correct
21 Correct 57 ms 14556 KB Output is correct
22 Correct 36 ms 13364 KB Output is correct
23 Correct 55 ms 14292 KB Output is correct
24 Correct 31 ms 13472 KB Output is correct
25 Correct 89 ms 28856 KB Output is correct

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Execution timed out 4080 ms 67052 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 452 KB Output is correct
2 Correct 2355 ms 61340 KB Output is correct
3 Correct 3210 ms 63448 KB Output is correct
4 Execution timed out 4086 ms 125392 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 452 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 30 ms 784 KB Output is correct
7 Correct 21 ms 836 KB Output is correct
8 Correct 13 ms 760 KB Output is correct
9 Correct 12 ms 708 KB Output is correct
10 Correct 50 ms 14260 KB Output is correct
11 Correct 64 ms 28860 KB Output is correct
12 Correct 57 ms 28884 KB Output is correct
13 Correct 58 ms 28828 KB Output is correct
14 Correct 79 ms 28784 KB Output is correct
15 Correct 78 ms 28820 KB Output is correct
16 Correct 34 ms 13412 KB Output is correct
17 Correct 54 ms 13392 KB Output is correct
18 Correct 34 ms 13416 KB Output is correct
19 Correct 58 ms 28892 KB Output is correct
20 Correct 39 ms 13388 KB Output is correct
21 Correct 57 ms 14556 KB Output is correct
22 Correct 36 ms 13364 KB Output is correct
23 Correct 55 ms 14292 KB Output is correct
24 Correct 31 ms 13472 KB Output is correct
25 Correct 89 ms 28856 KB Output is correct
26 Correct 1 ms 340 KB Output is correct
27 Correct 1 ms 340 KB Output is correct
28 Correct 1 ms 340 KB Output is correct
29 Execution timed out 4080 ms 67052 KB Time limit exceeded
30 Halted 0 ms 0 KB -