oj.uz

Submission #568094

# Submission time Handle Problem Language Result Execution time Memory
568094 2022-05-24T16:22:44 Z nonsensenonsense1 Ants and Sugar (JOI22_sugar) C++17
100 / 100
 1354 ms 73292 KB 
#include <cstdio>
#include <cstring>
#include <algorithm>

const int N = 500000;
int q, l, type[N], x[N], a[N], val[N], m;
long long add[N * 2], sameadd[N * 2];

struct item {
	long long d[2][2], same;
	item() {
		memset(d, 0, sizeof d);
		same = 0;
	}
	void inc(long long x) {
		d[0][0] -= x;
		d[0][1] -= x;
		d[1][0] -= x;
		d[1][1] -= x;
		d[0][0] = std::max(d[0][0], (long long)0);
	}
} t[N * 2];

item operator+(item a, item b) {
	item res;
	memset(res.d, 0xc3, sizeof res.d);
	for (int i = 0; i < 2; ++i) for (int j = 0; j < 2; ++j) for (int k = 0; k < 2; ++k) for (int l = 0; l < 2; ++l) 
		res.d[i][l] = std::max(res.d[i][l], a.d[i][j] + b.d[k][l] + a.same * j * k);
	res.same = b.same;
	return res;
}

void build(int v = 0, int tl = 0, int tr = m) {
	if (tr - tl == 1) t[v].d[0][1] = t[v].d[1][0] = ((long long)1 << 63) >> 2;
	else {
		int m = tl + tr >> 1;
		build(v + 1, tl, m);
		build(v + (tr - tl & ~1), m, tr);
		t[v] = t[v + 1] + t[v + (tr - tl & ~1)];
	}
}

void pointupd(int i, int x, int v = 0, int tl = 0, int tr = m) {
	if (tr - tl == 1) t[v].d[1][1] += x;
	else {
		int m = tl + tr >> 1;
		if (i < m) pointupd(i, x, v + 1, tl, m);
		else pointupd(i, x, v + (tr - tl & ~1), m, tr);
		t[v] = t[v + 1] + t[v + (tr - tl & ~1)];
		t[v].same += sameadd[v];
		t[v].inc(add[v]);
	}
}

void update(int l, int r, int x, int v = 0, int tl = 0, int tr = m) {
	if (l == r) return;
	if (tl >= r || tr <= l) return;
	if (tl >= l && tr <= r) {
		if (tr != r) {
			sameadd[v] += x;
			t[v].same += x;
		}
		add[v] += x;
		t[v].inc(x);
	} else {
		int m = tl + tr >> 1;
		update(l, r, x, v + 1, tl, m);
		update(l, r, x, v + (tr - tl & ~1), m, tr);
		t[v] = t[v + 1] + t[v + (tr - tl & ~1)];
		t[v].same += sameadd[v];
		t[v].inc(add[v]);
	}
}

int main() {
	scanf("%d%d", &q, &l);
	for (int i = 0; i < q; ++i) {
		scanf("%d%d%d", type + i, x + i, a + i);
		if (type[i] == 1) val[m++] = x[i];
	}
	if (!m) {
		for (int i = 0; i < q; ++i) printf("0\n");
		return 0;
	}
	std::sort(val, val + m);
	m = std::unique(val, val + m) - val;
	long long cnt = 0;
	build();
	for (int i = 0; i < q; ++i) {
		if (type[i] == 1) {
			pointupd(std::lower_bound(val, val + m, x[i]) - val, a[i]);
			cnt += a[i];
		} else update(std::lower_bound(val, val + m, x[i] - l) - val, std::upper_bound(val, val + m, x[i] + l) - val, a[i]);
		long long mx = 0;
		for (int i = 0; i < 2; ++i) for (int j = 0; j < 2; ++j) mx = std::max(mx, t[0].d[i][j]);
		printf("%lld\n", cnt - mx);
	}
	return 0;
}

Compilation message

sugar.cpp: In function 'void build(int, int, int)':
sugar.cpp:36:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   36 |   int m = tl + tr >> 1;
      |           ~~~^~~~
sugar.cpp:38:17: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   38 |   build(v + (tr - tl & ~1), m, tr);
      |              ~~~^~~~
sugar.cpp:39:31: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   39 |   t[v] = t[v + 1] + t[v + (tr - tl & ~1)];
      |                            ~~~^~~~
sugar.cpp: In function 'void pointupd(int, int, int, int, int)':
sugar.cpp:46:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   46 |   int m = tl + tr >> 1;
      |           ~~~^~~~
sugar.cpp:48:31: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   48 |   else pointupd(i, x, v + (tr - tl & ~1), m, tr);
      |                            ~~~^~~~
sugar.cpp:49:31: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   49 |   t[v] = t[v + 1] + t[v + (tr - tl & ~1)];
      |                            ~~~^~~~
sugar.cpp: In function 'void update(int, int, int, int, int, int)':
sugar.cpp:66:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   66 |   int m = tl + tr >> 1;
      |           ~~~^~~~
sugar.cpp:68:27: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   68 |   update(l, r, x, v + (tr - tl & ~1), m, tr);
      |                        ~~~^~~~
sugar.cpp:69:31: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   69 |   t[v] = t[v + 1] + t[v + (tr - tl & ~1)];
      |                            ~~~^~~~
sugar.cpp: In function 'int main()':
sugar.cpp:76:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   76 |  scanf("%d%d", &q, &l);
      |  ~~~~~^~~~~~~~~~~~~~~~
sugar.cpp:78:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   78 |   scanf("%d%d%d", type + i, x + i, a + i);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 39380 KB Output is correct
2 Correct 20 ms 39392 KB Output is correct
3 Correct 17 ms 39360 KB Output is correct
4 Correct 16 ms 39448 KB Output is correct
5 Correct 22 ms 39444 KB Output is correct
6 Correct 20 ms 39572 KB Output is correct
7 Correct 18 ms 39496 KB Output is correct
8 Correct 19 ms 39444 KB Output is correct
9 Correct 25 ms 39508 KB Output is correct
10 Correct 21 ms 39608 KB Output is correct
11 Correct 27 ms 39576 KB Output is correct
12 Correct 26 ms 39572 KB Output is correct
13 Correct 21 ms 39636 KB Output is correct
14 Correct 18 ms 39444 KB Output is correct
15 Correct 20 ms 39520 KB Output is correct
16 Correct 19 ms 39636 KB Output is correct
17 Correct 19 ms 39500 KB Output is correct
18 Correct 19 ms 39536 KB Output is correct
19 Correct 20 ms 39572 KB Output is correct
20 Correct 19 ms 39508 KB Output is correct
21 Correct 31 ms 39552 KB Output is correct
22 Correct 23 ms 39440 KB Output is correct
23 Correct 24 ms 39608 KB Output is correct
24 Correct 24 ms 39428 KB Output is correct
25 Correct 22 ms 39588 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 39368 KB Output is correct
2 Correct 21 ms 39384 KB Output is correct
3 Correct 19 ms 39380 KB Output is correct
4 Correct 744 ms 59272 KB Output is correct
5 Correct 324 ms 53920 KB Output is correct
6 Correct 849 ms 63040 KB Output is correct
7 Correct 352 ms 54152 KB Output is correct
8 Correct 1036 ms 66560 KB Output is correct
9 Correct 635 ms 70832 KB Output is correct
10 Correct 1061 ms 67480 KB Output is correct
11 Correct 684 ms 69476 KB Output is correct
12 Correct 316 ms 52020 KB Output is correct
13 Correct 387 ms 56372 KB Output is correct
14 Correct 628 ms 67212 KB Output is correct
15 Correct 631 ms 67208 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 39380 KB Output is correct
2 Correct 272 ms 47804 KB Output is correct
3 Correct 375 ms 51020 KB Output is correct
4 Correct 637 ms 58464 KB Output is correct
5 Correct 613 ms 58512 KB Output is correct
6 Correct 761 ms 53468 KB Output is correct
7 Correct 46 ms 40532 KB Output is correct
8 Correct 355 ms 46696 KB Output is correct
9 Correct 612 ms 50104 KB Output is correct
10 Correct 988 ms 58320 KB Output is correct
11 Correct 1068 ms 58332 KB Output is correct
12 Correct 982 ms 58288 KB Output is correct
13 Correct 926 ms 58304 KB Output is correct
14 Correct 1097 ms 58340 KB Output is correct
15 Correct 752 ms 55520 KB Output is correct
16 Correct 880 ms 58244 KB Output is correct
17 Correct 1163 ms 58296 KB Output is correct
18 Correct 1354 ms 58332 KB Output is correct
19 Correct 1294 ms 58444 KB Output is correct
20 Correct 1294 ms 58288 KB Output is correct
21 Correct 1256 ms 58432 KB Output is correct
22 Correct 1281 ms 58396 KB Output is correct
23 Correct 1246 ms 58360 KB Output is correct
24 Correct 710 ms 53136 KB Output is correct
25 Correct 1008 ms 58476 KB Output is correct

Subtask #4
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 39380 KB Output is correct
2 Correct 20 ms 39392 KB Output is correct
3 Correct 17 ms 39360 KB Output is correct
4 Correct 16 ms 39448 KB Output is correct
5 Correct 22 ms 39444 KB Output is correct
6 Correct 20 ms 39572 KB Output is correct
7 Correct 18 ms 39496 KB Output is correct
8 Correct 19 ms 39444 KB Output is correct
9 Correct 25 ms 39508 KB Output is correct
10 Correct 21 ms 39608 KB Output is correct
11 Correct 27 ms 39576 KB Output is correct
12 Correct 26 ms 39572 KB Output is correct
13 Correct 21 ms 39636 KB Output is correct
14 Correct 18 ms 39444 KB Output is correct
15 Correct 20 ms 39520 KB Output is correct
16 Correct 19 ms 39636 KB Output is correct
17 Correct 19 ms 39500 KB Output is correct
18 Correct 19 ms 39536 KB Output is correct
19 Correct 20 ms 39572 KB Output is correct
20 Correct 19 ms 39508 KB Output is correct
21 Correct 31 ms 39552 KB Output is correct
22 Correct 23 ms 39440 KB Output is correct
23 Correct 24 ms 39608 KB Output is correct
24 Correct 24 ms 39428 KB Output is correct
25 Correct 22 ms 39588 KB Output is correct
26 Correct 19 ms 39368 KB Output is correct
27 Correct 21 ms 39384 KB Output is correct
28 Correct 19 ms 39380 KB Output is correct
29 Correct 744 ms 59272 KB Output is correct
30 Correct 324 ms 53920 KB Output is correct
31 Correct 849 ms 63040 KB Output is correct
32 Correct 352 ms 54152 KB Output is correct
33 Correct 1036 ms 66560 KB Output is correct
34 Correct 635 ms 70832 KB Output is correct
35 Correct 1061 ms 67480 KB Output is correct
36 Correct 684 ms 69476 KB Output is correct
37 Correct 316 ms 52020 KB Output is correct
38 Correct 387 ms 56372 KB Output is correct
39 Correct 628 ms 67212 KB Output is correct
40 Correct 631 ms 67208 KB Output is correct
41 Correct 20 ms 39380 KB Output is correct
42 Correct 272 ms 47804 KB Output is correct
43 Correct 375 ms 51020 KB Output is correct
44 Correct 637 ms 58464 KB Output is correct
45 Correct 613 ms 58512 KB Output is correct
46 Correct 761 ms 53468 KB Output is correct
47 Correct 46 ms 40532 KB Output is correct
48 Correct 355 ms 46696 KB Output is correct
49 Correct 612 ms 50104 KB Output is correct
50 Correct 988 ms 58320 KB Output is correct
51 Correct 1068 ms 58332 KB Output is correct
52 Correct 982 ms 58288 KB Output is correct
53 Correct 926 ms 58304 KB Output is correct
54 Correct 1097 ms 58340 KB Output is correct
55 Correct 752 ms 55520 KB Output is correct
56 Correct 880 ms 58244 KB Output is correct
57 Correct 1163 ms 58296 KB Output is correct
58 Correct 1354 ms 58332 KB Output is correct
59 Correct 1294 ms 58444 KB Output is correct
60 Correct 1294 ms 58288 KB Output is correct
61 Correct 1256 ms 58432 KB Output is correct
62 Correct 1281 ms 58396 KB Output is correct
63 Correct 1246 ms 58360 KB Output is correct
64 Correct 710 ms 53136 KB Output is correct
65 Correct 1008 ms 58476 KB Output is correct
66 Correct 506 ms 56440 KB Output is correct
67 Correct 613 ms 59524 KB Output is correct
68 Correct 833 ms 63532 KB Output is correct
69 Correct 739 ms 61452 KB Output is correct
70 Correct 858 ms 71480 KB Output is correct
71 Correct 988 ms 71640 KB Output is correct
72 Correct 1020 ms 71600 KB Output is correct
73 Correct 1140 ms 71740 KB Output is correct
74 Correct 211 ms 56396 KB Output is correct
75 Correct 323 ms 62244 KB Output is correct
76 Correct 1251 ms 73292 KB Output is correct
77 Correct 1181 ms 58528 KB Output is correct
78 Correct 1129 ms 58692 KB Output is correct
79 Correct 1123 ms 71740 KB Output is correct
80 Correct 1126 ms 58444 KB Output is correct
81 Correct 1050 ms 71440 KB Output is correct
82 Correct 1139 ms 58764 KB Output is correct
83 Correct 1253 ms 71820 KB Output is correct
84 Correct 1079 ms 58696 KB Output is correct
85 Correct 1336 ms 71972 KB Output is correct
86 Correct 1095 ms 58840 KB Output is correct
87 Correct 1344 ms 72216 KB Output is correct
88 Correct 1080 ms 58808 KB Output is correct
89 Correct 1184 ms 68816 KB Output is correct