Submission #551593

#	Time	Username	Problem	Language	Result	Execution time	Memory
551593		skittles1412	Ants and Sugar (JOI22_sugar)	C++17	100 / 100	3420 ms	339256 KiB

sugar

#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2")

#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())

namespace IO {

char buf[1 << 20];
int bind, bend;

char nc() {
	if (bind == bend) {
		bend = int(fread(buf, 1, sizeof(buf), stdin));
		bind = 0; 
	}
	return buf[bind++];
}

int ni() {
	int ans = 0;
	char c;
	while ((c = nc()) >= '0') {
		ans = ans * 10 + c - '0';
	}
	return ans;
}

}  // namespace IO

using IO::ni;

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

	Node() : v(Node::def().v) {}

	Node(bool) : v {} {}

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

	static Node inf() {
		Node ans(true);
		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 < 2; 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};
	}
};

const int maxn = 1 << 21, tmaxn = maxn << 1;

Node v[tmaxn];
Lazy lazy[tmaxn];

void update(int o, int l, int r, int ql, int qr, const Lazy& x) {
	int mid = (l + r) / 2, lc = o * 2, rc = lc + 1;
	if (ql <= l && r <= qr) {
		lazy[o] += x;
	} else {
		if (ql <= mid) {
			update(lc, l, mid, ql, qr, x);
		}
		if (mid < qr) {
			update(rc, mid + 1, r, ql, qr, x);
		}
	}
	if (l == r) {
		v[o] = lazy[o].apply(Node::def());
	} else {
		v[o] = lazy[o].apply(v[lc] + v[rc]);
	}
}

void update(int l, int r, const Lazy& x) {
	dbg(l, r, x.ax, x.bx);
	update(1, 0, maxn - 1, l, r, x);
}

void solve() {
	int q = ni(), k = ni();
	int arr[q][3];
	for (auto& [a, b, c] : arr) {
		a = ni();
		b = ni();
		c = ni();
	}
	vector<int> comp;
	for (auto& [t, ind, _x] : arr) {
		if (t == 1) {
			comp.push_back(ind);
		} else {
			comp.push_back(ind + k);
			comp.push_back(ind - k);
			comp.push_back(ind + k - 1);
		}
	}
	sort(begin(comp), end(comp));
	comp.erase(unique(begin(comp), end(comp)), comp.end());
	auto cg = [&](int x) -> int {
		return int(lower_bound(begin(comp), end(comp), x) - comp.begin());
	};
	long ants = 0;
	for (auto& [t, ind, x] : arr) {
		if (t == 1) {
			ants += x;
			update(cg(ind), maxn - 1, {x, 0});
		} else {
			update(cg(ind + k), maxn - 1, {-x, 0});
			update(cg(ind - k), cg(ind + k - 1), {0, -x});
		}
		auto& n = v[1];
		long ans = 0;
		for (auto& a : n.v) {
			ans = max({ans, a[0][0], a[1][0]});
		}
		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: 16 / 16
• Subtask 3: 26 / 26
• Subtask 4: 52 / 52