oj.uz

Submission #551586

# Submission time Handle Problem Language Result Execution time Memory
551586 2022-04-21T05:54:54 Z skittles1412 Ants and Sugar (JOI22_sugar) C++17
6 / 100
 4000 ms 449196 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 << 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, 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 274 ms 394264 KB Output is correct
2 Correct 267 ms 394348 KB Output is correct
3 Correct 272 ms 394264 KB Output is correct
4 Correct 267 ms 394368 KB Output is correct
5 Correct 268 ms 394188 KB Output is correct
6 Correct 282 ms 394536 KB Output is correct
7 Correct 279 ms 394532 KB Output is correct
8 Correct 280 ms 394400 KB Output is correct
9 Correct 271 ms 394464 KB Output is correct
10 Correct 292 ms 394736 KB Output is correct
11 Correct 299 ms 394740 KB Output is correct
12 Correct 302 ms 394688 KB Output is correct
13 Correct 308 ms 394756 KB Output is correct
14 Correct 304 ms 394888 KB Output is correct
15 Correct 294 ms 394772 KB Output is correct
16 Correct 286 ms 394608 KB Output is correct
17 Correct 292 ms 394508 KB Output is correct
18 Correct 281 ms 394592 KB Output is correct
19 Correct 307 ms 394828 KB Output is correct
20 Correct 285 ms 394492 KB Output is correct
21 Correct 285 ms 394628 KB Output is correct
22 Correct 308 ms 394540 KB Output is correct
23 Correct 289 ms 394728 KB Output is correct
24 Correct 298 ms 394612 KB Output is correct
25 Correct 282 ms 394724 KB Output is correct

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 275 ms 394316 KB Output is correct
2 Correct 339 ms 394324 KB Output is correct
3 Correct 276 ms 394424 KB Output is correct
4 Correct 3120 ms 416664 KB Output is correct
5 Correct 1770 ms 406788 KB Output is correct
6 Correct 3524 ms 419620 KB Output is correct
7 Correct 1786 ms 406828 KB Output is correct
8 Execution timed out 4059 ms 423832 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 262 ms 394312 KB Output is correct
2 Correct 1667 ms 404636 KB Output is correct
3 Correct 2185 ms 408340 KB Output is correct
4 Correct 3379 ms 416948 KB Output is correct
5 Correct 3262 ms 416792 KB Output is correct
6 Correct 3377 ms 418528 KB Output is correct
7 Correct 555 ms 397308 KB Output is correct
8 Correct 1876 ms 409076 KB Output is correct
9 Correct 2672 ms 414308 KB Output is correct
10 Execution timed out 4083 ms 449196 KB Time limit exceeded
11 Halted 0 ms 0 KB -

Subtask #4
0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 274 ms 394264 KB Output is correct
2 Correct 267 ms 394348 KB Output is correct
3 Correct 272 ms 394264 KB Output is correct
4 Correct 267 ms 394368 KB Output is correct
5 Correct 268 ms 394188 KB Output is correct
6 Correct 282 ms 394536 KB Output is correct
7 Correct 279 ms 394532 KB Output is correct
8 Correct 280 ms 394400 KB Output is correct
9 Correct 271 ms 394464 KB Output is correct
10 Correct 292 ms 394736 KB Output is correct
11 Correct 299 ms 394740 KB Output is correct
12 Correct 302 ms 394688 KB Output is correct
13 Correct 308 ms 394756 KB Output is correct
14 Correct 304 ms 394888 KB Output is correct
15 Correct 294 ms 394772 KB Output is correct
16 Correct 286 ms 394608 KB Output is correct
17 Correct 292 ms 394508 KB Output is correct
18 Correct 281 ms 394592 KB Output is correct
19 Correct 307 ms 394828 KB Output is correct
20 Correct 285 ms 394492 KB Output is correct
21 Correct 285 ms 394628 KB Output is correct
22 Correct 308 ms 394540 KB Output is correct
23 Correct 289 ms 394728 KB Output is correct
24 Correct 298 ms 394612 KB Output is correct
25 Correct 282 ms 394724 KB Output is correct
26 Correct 275 ms 394316 KB Output is correct
27 Correct 339 ms 394324 KB Output is correct
28 Correct 276 ms 394424 KB Output is correct
29 Correct 3120 ms 416664 KB Output is correct
30 Correct 1770 ms 406788 KB Output is correct
31 Correct 3524 ms 419620 KB Output is correct
32 Correct 1786 ms 406828 KB Output is correct
33 Execution timed out 4059 ms 423832 KB Time limit exceeded
34 Halted 0 ms 0 KB -