oj.uz

Submission #568092

# Submission time Handle Problem Language Result Execution time Memory
568092 2022-05-24T16:21:03 Z nonsensenonsense1 Ants and Sugar (JOI22_sugar) C++17
26 / 100
 1241 ms 1048576 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];
	}
	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
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 39380 KB Output is correct
2 Correct 19 ms 39352 KB Output is correct
3 Correct 19 ms 39432 KB Output is correct
4 Correct 18 ms 39460 KB Output is correct
5 Correct 16 ms 39364 KB Output is correct
6 Correct 20 ms 39484 KB Output is correct
7 Correct 18 ms 39500 KB Output is correct
8 Correct 19 ms 39508 KB Output is correct
9 Correct 18 ms 39448 KB Output is correct
10 Correct 20 ms 39560 KB Output is correct
11 Correct 20 ms 39612 KB Output is correct
12 Correct 20 ms 39560 KB Output is correct
13 Correct 26 ms 39568 KB Output is correct
14 Runtime error 478 ms 1048576 KB Execution killed with signal 9
15 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 39380 KB Output is correct
2 Correct 19 ms 39364 KB Output is correct
3 Runtime error 519 ms 1048576 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 39380 KB Output is correct
2 Correct 262 ms 48572 KB Output is correct
3 Correct 349 ms 51904 KB Output is correct
4 Correct 596 ms 59416 KB Output is correct
5 Correct 554 ms 59340 KB Output is correct
6 Correct 637 ms 54328 KB Output is correct
7 Correct 46 ms 41072 KB Output is correct
8 Correct 335 ms 47392 KB Output is correct
9 Correct 541 ms 50900 KB Output is correct
10 Correct 935 ms 59216 KB Output is correct
11 Correct 977 ms 59116 KB Output is correct
12 Correct 951 ms 59136 KB Output is correct
13 Correct 926 ms 59136 KB Output is correct
14 Correct 928 ms 59000 KB Output is correct
15 Correct 676 ms 56320 KB Output is correct
16 Correct 848 ms 59048 KB Output is correct
17 Correct 1097 ms 59116 KB Output is correct
18 Correct 1198 ms 59168 KB Output is correct
19 Correct 1164 ms 59172 KB Output is correct
20 Correct 1154 ms 59160 KB Output is correct
21 Correct 1241 ms 59152 KB Output is correct
22 Correct 1198 ms 59108 KB Output is correct
23 Correct 1231 ms 59208 KB Output is correct
24 Correct 694 ms 53916 KB Output is correct
25 Correct 995 ms 59160 KB Output is correct

Subtask #4
0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 39380 KB Output is correct
2 Correct 19 ms 39352 KB Output is correct
3 Correct 19 ms 39432 KB Output is correct
4 Correct 18 ms 39460 KB Output is correct
5 Correct 16 ms 39364 KB Output is correct
6 Correct 20 ms 39484 KB Output is correct
7 Correct 18 ms 39500 KB Output is correct
8 Correct 19 ms 39508 KB Output is correct
9 Correct 18 ms 39448 KB Output is correct
10 Correct 20 ms 39560 KB Output is correct
11 Correct 20 ms 39612 KB Output is correct
12 Correct 20 ms 39560 KB Output is correct
13 Correct 26 ms 39568 KB Output is correct
14 Runtime error 478 ms 1048576 KB Execution killed with signal 9
15 Halted 0 ms 0 KB -