oj.uz

Submission #816962

# Submission time Handle Problem Language Result Execution time Memory
816962 2023-08-09T07:51:08 Z GEN 이지후(#10378) Ants and Sugar (JOI22_sugar) C++17
22 / 100
 4000 ms 128004 KB 
#include <bits/stdc++.h>
using namespace std;
using lint = long long;
#define sz(a) ((int)(a).size())
#define all(a) (a).begin(), (a).end()
const int MAXT = 1050000;

struct node {
	lint adj[3][3];
	node() {
		for (int i = 0; i < 3; i++) {
			for (int j = 0; j < 3; j++) {
				adj[i][j] = -1e18;
			}
		}
	}
	node operator+(const node &nd) const {
		node ret;
		for (int i = 0; i < 3; i++) {
			for (int j = 0; j < 3; j++) {
				for (int k = 0; k < 3; k++) {
					ret.adj[j][k] = max(ret.adj[j][k], adj[j][i] + nd.adj[i][k]);
				}
			}
		}
		return ret;
	}
} tree[MAXT];

void init(int s, int e, int p, vector<node> &v) {
	if (s == e) {
		tree[p] = v[s];
		return;
	}
	int m = (s + e) / 2;
	init(s, m, 2 * p, v);
	init(m + 1, e, 2 * p + 1, v);
	tree[p] = tree[2 * p] + tree[2 * p + 1];
}

void upd(int pos, int s, int e, int p, node v) {
	if (s == e) {
		tree[p] = v;
		return;
	}
	int m = (s + e) / 2;
	if (pos <= m)
		upd(pos, s, m, 2 * p, v);
	else
		upd(pos, m + 1, e, 2 * p + 1, v);
	tree[p] = tree[2 * p] + tree[2 * p + 1];
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	lint q, l;
	cin >> q >> l;
	vector<array<lint, 3>> qry(q);
	vector<int> vect;
	for (int i = 0; i < q; i++) {
		for (int j = 0; j < 3; j++) {
			cin >> qry[i][j];
		}
		if (qry[i][0] == 1) {
			qry[i][1] -= l;
		}
		if (qry[i][0] == 2)
			vect.push_back(qry[i][1]);
	}
	if (sz(vect) == 0) {
		while (q--)
			cout << "0\n";
		return 0;
	}
	sort(all(vect));
	vect.resize(unique(all(vect)) - vect.begin());
	// (my weight, R mode, T mode)
	vector<array<lint, 3>> values(sz(vect));
	auto genNode = [&](int pos) {
		node ret;
		for (int i = 0; i < 3; i++) {
			for (int j = 0; j < 3; j++) {
				if (j == 0)
					ret.adj[i][j] = 0;
				if (j == 1)
					ret.adj[i][j] = values[pos][0] - values[pos][2];
				if (j == 2) {
					if (i > 0 && (pos > 0 && vect[pos] - vect[pos - 1] <= 2 * l)) {
						ret.adj[i][j] = values[pos][0] - values[pos][1];
					} else
						ret.adj[i][j] = -1e18;
				}
			}
		}
		return ret;
	};
	vector<node> nodes;
	for (int i = 0; i < sz(vect); i++) {
		nodes.push_back(genNode(i));
	}
	init(0, sz(vect) - 1, 1, nodes);
	lint sugsum = 0;
	for (int i = 0; i < q; i++) {
		if (qry[i][0] == 1) {
			int st = lower_bound(all(vect), qry[i][1]) - vect.begin();
			int ed = lower_bound(all(vect), qry[i][1] + 2 * l + 1) - vect.begin();
			if (st < sz(vect)) {
				values[st][1] += qry[i][2];
				upd(st, 0, sz(vect) - 1, 1, genNode(st));
			}
			for (int pos = st; pos < ed; pos++) {
				values[pos][2] += qry[i][2];
				upd(pos, 0, sz(vect) - 1, 1, genNode(pos));
			}
		} else {
			auto it = lower_bound(all(vect), qry[i][1]) - vect.begin();
			values[it][0] += qry[i][2];
			sugsum += qry[i][2];
			upd(it, 0, sz(vect) - 1, 1, genNode(it));
		}
		cout << sugsum - *max_element(tree[1].adj[0], tree[1].adj[0] + 3) << "\n";
	}
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 74188 KB Output is correct
2 Correct 28 ms 74196 KB Output is correct
3 Correct 28 ms 74176 KB Output is correct
4 Correct 28 ms 74284 KB Output is correct
5 Correct 29 ms 74208 KB Output is correct
6 Correct 30 ms 74512 KB Output is correct
7 Correct 31 ms 74444 KB Output is correct
8 Correct 29 ms 74324 KB Output is correct
9 Correct 30 ms 74328 KB Output is correct
10 Correct 30 ms 74664 KB Output is correct
11 Correct 31 ms 74676 KB Output is correct
12 Correct 32 ms 74624 KB Output is correct
13 Correct 32 ms 74580 KB Output is correct
14 Correct 31 ms 74852 KB Output is correct
15 Correct 31 ms 74836 KB Output is correct
16 Correct 29 ms 74352 KB Output is correct
17 Correct 28 ms 74316 KB Output is correct
18 Correct 29 ms 74340 KB Output is correct
19 Correct 32 ms 74592 KB Output is correct
20 Correct 29 ms 74272 KB Output is correct
21 Correct 40 ms 74672 KB Output is correct
22 Correct 29 ms 74320 KB Output is correct
23 Correct 116 ms 74580 KB Output is correct
24 Correct 32 ms 74304 KB Output is correct
25 Correct 409 ms 74652 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 74188 KB Output is correct
2 Correct 28 ms 74216 KB Output is correct
3 Correct 28 ms 74244 KB Output is correct
4 Correct 737 ms 100044 KB Output is correct
5 Correct 363 ms 99912 KB Output is correct
6 Correct 790 ms 114828 KB Output is correct
7 Correct 362 ms 100044 KB Output is correct
8 Correct 1008 ms 118868 KB Output is correct
9 Correct 787 ms 128004 KB Output is correct
10 Correct 1030 ms 118824 KB Output is correct
11 Correct 738 ms 127964 KB Output is correct
12 Correct 346 ms 96608 KB Output is correct
13 Correct 460 ms 110372 KB Output is correct
14 Correct 736 ms 124548 KB Output is correct
15 Correct 746 ms 124808 KB Output is correct

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 74296 KB Output is correct
2 Correct 340 ms 92640 KB Output is correct
3 Correct 491 ms 110376 KB Output is correct
4 Correct 747 ms 124656 KB Output is correct
5 Correct 744 ms 124604 KB Output is correct
6 Correct 805 ms 114720 KB Output is correct
7 Correct 57 ms 77480 KB Output is correct
8 Correct 367 ms 94780 KB Output is correct
9 Correct 700 ms 102884 KB Output is correct
10 Correct 1102 ms 125928 KB Output is correct
11 Correct 1325 ms 125924 KB Output is correct
12 Correct 1165 ms 125872 KB Output is correct
13 Correct 1084 ms 125908 KB Output is correct
14 Correct 1182 ms 125896 KB Output is correct
15 Correct 930 ms 125828 KB Output is correct
16 Correct 993 ms 125924 KB Output is correct
17 Execution timed out 4045 ms 122548 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #4
0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 74188 KB Output is correct
2 Correct 28 ms 74196 KB Output is correct
3 Correct 28 ms 74176 KB Output is correct
4 Correct 28 ms 74284 KB Output is correct
5 Correct 29 ms 74208 KB Output is correct
6 Correct 30 ms 74512 KB Output is correct
7 Correct 31 ms 74444 KB Output is correct
8 Correct 29 ms 74324 KB Output is correct
9 Correct 30 ms 74328 KB Output is correct
10 Correct 30 ms 74664 KB Output is correct
11 Correct 31 ms 74676 KB Output is correct
12 Correct 32 ms 74624 KB Output is correct
13 Correct 32 ms 74580 KB Output is correct
14 Correct 31 ms 74852 KB Output is correct
15 Correct 31 ms 74836 KB Output is correct
16 Correct 29 ms 74352 KB Output is correct
17 Correct 28 ms 74316 KB Output is correct
18 Correct 29 ms 74340 KB Output is correct
19 Correct 32 ms 74592 KB Output is correct
20 Correct 29 ms 74272 KB Output is correct
21 Correct 40 ms 74672 KB Output is correct
22 Correct 29 ms 74320 KB Output is correct
23 Correct 116 ms 74580 KB Output is correct
24 Correct 32 ms 74304 KB Output is correct
25 Correct 409 ms 74652 KB Output is correct
26 Correct 27 ms 74188 KB Output is correct
27 Correct 28 ms 74216 KB Output is correct
28 Correct 28 ms 74244 KB Output is correct
29 Correct 737 ms 100044 KB Output is correct
30 Correct 363 ms 99912 KB Output is correct
31 Correct 790 ms 114828 KB Output is correct
32 Correct 362 ms 100044 KB Output is correct
33 Correct 1008 ms 118868 KB Output is correct
34 Correct 787 ms 128004 KB Output is correct
35 Correct 1030 ms 118824 KB Output is correct
36 Correct 738 ms 127964 KB Output is correct
37 Correct 346 ms 96608 KB Output is correct
38 Correct 460 ms 110372 KB Output is correct
39 Correct 736 ms 124548 KB Output is correct
40 Correct 746 ms 124808 KB Output is correct
41 Correct 27 ms 74296 KB Output is correct
42 Correct 340 ms 92640 KB Output is correct
43 Correct 491 ms 110376 KB Output is correct
44 Correct 747 ms 124656 KB Output is correct
45 Correct 744 ms 124604 KB Output is correct
46 Correct 805 ms 114720 KB Output is correct
47 Correct 57 ms 77480 KB Output is correct
48 Correct 367 ms 94780 KB Output is correct
49 Correct 700 ms 102884 KB Output is correct
50 Correct 1102 ms 125928 KB Output is correct
51 Correct 1325 ms 125924 KB Output is correct
52 Correct 1165 ms 125872 KB Output is correct
53 Correct 1084 ms 125908 KB Output is correct
54 Correct 1182 ms 125896 KB Output is correct
55 Correct 930 ms 125828 KB Output is correct
56 Correct 993 ms 125924 KB Output is correct
57 Execution timed out 4045 ms 122548 KB Time limit exceeded
58 Halted 0 ms 0 KB -