oj.uz

Submission #551585

# Submission time Handle Problem Language Result Execution time Memory
551585 2022-04-21T05:52:00 Z skittles1412 Ants and Sugar (JOI22_sugar) C++17
22 / 100
 3396 ms 1048576 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;

	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 < 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(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 < 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};
	}
};

const int maxn = 1 << 19, 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, k;
	cin >> q >> k;
	int arr[q][3];
	for (auto& [a, b, c] : arr) {
		cin >> a >> b >> c;
	}
	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.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 98812 KB Output is correct
2 Correct 67 ms 98808 KB Output is correct
3 Correct 66 ms 98932 KB Output is correct
4 Correct 65 ms 98756 KB Output is correct
5 Correct 68 ms 98700 KB Output is correct
6 Correct 77 ms 98984 KB Output is correct
7 Correct 79 ms 99024 KB Output is correct
8 Correct 72 ms 98944 KB Output is correct
9 Correct 70 ms 98944 KB Output is correct
10 Correct 83 ms 99140 KB Output is correct
11 Correct 85 ms 99248 KB Output is correct
12 Correct 85 ms 99252 KB Output is correct
13 Correct 85 ms 99220 KB Output is correct
14 Correct 89 ms 99332 KB Output is correct
15 Correct 89 ms 99268 KB Output is correct
16 Correct 82 ms 99048 KB Output is correct
17 Correct 79 ms 99048 KB Output is correct
18 Correct 87 ms 99060 KB Output is correct
19 Correct 85 ms 99228 KB Output is correct
20 Correct 78 ms 98984 KB Output is correct
21 Correct 86 ms 99148 KB Output is correct
22 Correct 80 ms 99036 KB Output is correct
23 Correct 88 ms 99244 KB Output is correct
24 Correct 79 ms 99020 KB Output is correct
25 Correct 88 ms 99180 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 98780 KB Output is correct
2 Correct 70 ms 98856 KB Output is correct
3 Correct 71 ms 98808 KB Output is correct
4 Correct 2415 ms 120812 KB Output is correct
5 Correct 1307 ms 111140 KB Output is correct
6 Correct 2884 ms 124604 KB Output is correct
7 Correct 1315 ms 113588 KB Output is correct
8 Correct 3325 ms 130896 KB Output is correct
9 Correct 2588 ms 126660 KB Output is correct
10 Correct 3396 ms 130784 KB Output is correct
11 Correct 2599 ms 126608 KB Output is correct
12 Correct 1227 ms 111172 KB Output is correct
13 Correct 1642 ms 114920 KB Output is correct
14 Correct 2654 ms 123228 KB Output is correct
15 Correct 2631 ms 123272 KB Output is correct

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 98828 KB Output is correct
2 Correct 1242 ms 109176 KB Output is correct
3 Correct 1646 ms 112632 KB Output is correct
4 Correct 2648 ms 122096 KB Output is correct
5 Correct 2597 ms 123404 KB Output is correct
6 Correct 2715 ms 125056 KB Output is correct
7 Correct 270 ms 102224 KB Output is correct
8 Correct 1396 ms 115668 KB Output is correct
9 Correct 2118 ms 121040 KB Output is correct
10 Runtime error 1589 ms 1048576 KB Execution killed with signal 9
11 Halted 0 ms 0 KB -

Subtask #4
0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 98812 KB Output is correct
2 Correct 67 ms 98808 KB Output is correct
3 Correct 66 ms 98932 KB Output is correct
4 Correct 65 ms 98756 KB Output is correct
5 Correct 68 ms 98700 KB Output is correct
6 Correct 77 ms 98984 KB Output is correct
7 Correct 79 ms 99024 KB Output is correct
8 Correct 72 ms 98944 KB Output is correct
9 Correct 70 ms 98944 KB Output is correct
10 Correct 83 ms 99140 KB Output is correct
11 Correct 85 ms 99248 KB Output is correct
12 Correct 85 ms 99252 KB Output is correct
13 Correct 85 ms 99220 KB Output is correct
14 Correct 89 ms 99332 KB Output is correct
15 Correct 89 ms 99268 KB Output is correct
16 Correct 82 ms 99048 KB Output is correct
17 Correct 79 ms 99048 KB Output is correct
18 Correct 87 ms 99060 KB Output is correct
19 Correct 85 ms 99228 KB Output is correct
20 Correct 78 ms 98984 KB Output is correct
21 Correct 86 ms 99148 KB Output is correct
22 Correct 80 ms 99036 KB Output is correct
23 Correct 88 ms 99244 KB Output is correct
24 Correct 79 ms 99020 KB Output is correct
25 Correct 88 ms 99180 KB Output is correct
26 Correct 66 ms 98780 KB Output is correct
27 Correct 70 ms 98856 KB Output is correct
28 Correct 71 ms 98808 KB Output is correct
29 Correct 2415 ms 120812 KB Output is correct
30 Correct 1307 ms 111140 KB Output is correct
31 Correct 2884 ms 124604 KB Output is correct
32 Correct 1315 ms 113588 KB Output is correct
33 Correct 3325 ms 130896 KB Output is correct
34 Correct 2588 ms 126660 KB Output is correct
35 Correct 3396 ms 130784 KB Output is correct
36 Correct 2599 ms 126608 KB Output is correct
37 Correct 1227 ms 111172 KB Output is correct
38 Correct 1642 ms 114920 KB Output is correct
39 Correct 2654 ms 123228 KB Output is correct
40 Correct 2631 ms 123272 KB Output is correct
41 Correct 67 ms 98828 KB Output is correct
42 Correct 1242 ms 109176 KB Output is correct
43 Correct 1646 ms 112632 KB Output is correct
44 Correct 2648 ms 122096 KB Output is correct
45 Correct 2597 ms 123404 KB Output is correct
46 Correct 2715 ms 125056 KB Output is correct
47 Correct 270 ms 102224 KB Output is correct
48 Correct 1396 ms 115668 KB Output is correct
49 Correct 2118 ms 121040 KB Output is correct
50 Runtime error 1589 ms 1048576 KB Execution killed with signal 9
51 Halted 0 ms 0 KB -