oj.uz

Submission #551587

# Submission time Handle Problem Language Result Execution time Memory
551587 2022-04-21T06:02:18 Z skittles1412 Ants and Sugar (JOI22_sugar) C++17
6 / 100
 4000 ms 439564 KB 
#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>, 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 = 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.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 209 ms 394316 KB Output is correct
2 Correct 216 ms 394360 KB Output is correct
3 Correct 210 ms 394336 KB Output is correct
4 Correct 215 ms 394284 KB Output is correct
5 Correct 212 ms 394228 KB Output is correct
6 Correct 231 ms 394492 KB Output is correct
7 Correct 235 ms 394528 KB Output is correct
8 Correct 213 ms 394544 KB Output is correct
9 Correct 229 ms 394456 KB Output is correct
10 Correct 247 ms 394700 KB Output is correct
11 Correct 235 ms 394724 KB Output is correct
12 Correct 248 ms 394800 KB Output is correct
13 Correct 247 ms 394696 KB Output is correct
14 Correct 244 ms 394932 KB Output is correct
15 Correct 250 ms 395064 KB Output is correct
16 Correct 230 ms 394636 KB Output is correct
17 Correct 233 ms 394520 KB Output is correct
18 Correct 236 ms 394672 KB Output is correct
19 Correct 244 ms 394688 KB Output is correct
20 Correct 232 ms 394600 KB Output is correct
21 Correct 243 ms 394712 KB Output is correct
22 Correct 241 ms 394540 KB Output is correct
23 Correct 239 ms 394740 KB Output is correct
24 Correct 238 ms 394596 KB Output is correct
25 Correct 242 ms 394740 KB Output is correct

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 224 ms 394308 KB Output is correct
2 Correct 217 ms 394272 KB Output is correct
3 Correct 202 ms 394320 KB Output is correct
4 Correct 3538 ms 417020 KB Output is correct
5 Correct 1987 ms 407592 KB Output is correct
6 Execution timed out 4066 ms 420556 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 228 ms 394308 KB Output is correct
2 Correct 1860 ms 405300 KB Output is correct
3 Correct 2467 ms 409156 KB Output is correct
4 Correct 3873 ms 417628 KB Output is correct
5 Correct 3909 ms 417504 KB Output is correct
6 Correct 3900 ms 419476 KB Output is correct
7 Correct 511 ms 397828 KB Output is correct
8 Correct 2084 ms 409916 KB Output is correct
9 Correct 2965 ms 414884 KB Output is correct
10 Execution timed out 4074 ms 439564 KB Time limit exceeded
11 Halted 0 ms 0 KB -

Subtask #4
0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 209 ms 394316 KB Output is correct
2 Correct 216 ms 394360 KB Output is correct
3 Correct 210 ms 394336 KB Output is correct
4 Correct 215 ms 394284 KB Output is correct
5 Correct 212 ms 394228 KB Output is correct
6 Correct 231 ms 394492 KB Output is correct
7 Correct 235 ms 394528 KB Output is correct
8 Correct 213 ms 394544 KB Output is correct
9 Correct 229 ms 394456 KB Output is correct
10 Correct 247 ms 394700 KB Output is correct
11 Correct 235 ms 394724 KB Output is correct
12 Correct 248 ms 394800 KB Output is correct
13 Correct 247 ms 394696 KB Output is correct
14 Correct 244 ms 394932 KB Output is correct
15 Correct 250 ms 395064 KB Output is correct
16 Correct 230 ms 394636 KB Output is correct
17 Correct 233 ms 394520 KB Output is correct
18 Correct 236 ms 394672 KB Output is correct
19 Correct 244 ms 394688 KB Output is correct
20 Correct 232 ms 394600 KB Output is correct
21 Correct 243 ms 394712 KB Output is correct
22 Correct 241 ms 394540 KB Output is correct
23 Correct 239 ms 394740 KB Output is correct
24 Correct 238 ms 394596 KB Output is correct
25 Correct 242 ms 394740 KB Output is correct
26 Correct 224 ms 394308 KB Output is correct
27 Correct 217 ms 394272 KB Output is correct
28 Correct 202 ms 394320 KB Output is correct
29 Correct 3538 ms 417020 KB Output is correct
30 Correct 1987 ms 407592 KB Output is correct
31 Execution timed out 4066 ms 420556 KB Time limit exceeded
32 Halted 0 ms 0 KB -