Submission #551580

#	Time	Username	Problem	Language	Result	Execution time	Memory
551580		skittles1412	Ants and Sugar (JOI22_sugar)	C++17	6 / 100	4086 ms	125392 KiB

sugar

#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 / 6
• Subtask 2: 0 / 16
• Subtask 3: 0 / 26
• Subtask 4: 0 / 52