oj.uz

Submission #568089

# Submission time Handle Problem Language Result Execution time Memory
568089 2022-05-24T16:13:12 Z nonsensenonsense1 Ants and Sugar (JOI22_sugar) C++17
26 / 100
 1285 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], sameadd[N];

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 (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:65:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   65 |   int m = tl + tr >> 1;
      |           ~~~^~~~
sugar.cpp:67:27: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   67 |   update(l, r, x, v + (tr - tl & ~1), m, tr);
      |                        ~~~^~~~
sugar.cpp:68:31: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   68 |   t[v] = t[v + 1] + t[v + (tr - tl & ~1)];
      |                            ~~~^~~~
sugar.cpp: In function 'int main()':
sugar.cpp:75:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   75 |  scanf("%d%d", &q, &l);
      |  ~~~~~^~~~~~~~~~~~~~~~
sugar.cpp:77:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   77 |   scanf("%d%d%d", type + i, x + i, a + i);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 39380 KB Output is correct
2 Correct 15 ms 39408 KB Output is correct
3 Correct 16 ms 39424 KB Output is correct
4 Correct 17 ms 39380 KB Output is correct
5 Correct 16 ms 39380 KB Output is correct
6 Correct 20 ms 39548 KB Output is correct
7 Correct 25 ms 39476 KB Output is correct
8 Correct 17 ms 39508 KB Output is correct
9 Correct 20 ms 39440 KB Output is correct
10 Correct 19 ms 39568 KB Output is correct
11 Correct 19 ms 39568 KB Output is correct
12 Correct 20 ms 39620 KB Output is correct
13 Correct 20 ms 39660 KB Output is correct
14 Runtime error 645 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 19 ms 39356 KB Output is correct
2 Correct 20 ms 39348 KB Output is correct
3 Runtime error 525 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 21 ms 39384 KB Output is correct
2 Correct 258 ms 51684 KB Output is correct
3 Correct 342 ms 56396 KB Output is correct
4 Correct 577 ms 67088 KB Output is correct
5 Correct 597 ms 67096 KB Output is correct
6 Correct 734 ms 60680 KB Output is correct
7 Correct 52 ms 41036 KB Output is correct
8 Correct 356 ms 50288 KB Output is correct
9 Correct 550 ms 55428 KB Output is correct
10 Correct 967 ms 68768 KB Output is correct
11 Correct 1006 ms 68644 KB Output is correct
12 Correct 991 ms 68536 KB Output is correct
13 Correct 987 ms 68548 KB Output is correct
14 Correct 1048 ms 68808 KB Output is correct
15 Correct 993 ms 65812 KB Output is correct
16 Correct 1004 ms 68592 KB Output is correct
17 Correct 1058 ms 68604 KB Output is correct
18 Correct 1186 ms 68660 KB Output is correct
19 Correct 1122 ms 68972 KB Output is correct
20 Correct 1168 ms 68180 KB Output is correct
21 Correct 1285 ms 68672 KB Output is correct
22 Correct 1213 ms 68424 KB Output is correct
23 Correct 1221 ms 68724 KB Output is correct
24 Correct 674 ms 63180 KB Output is correct
25 Correct 991 ms 68564 KB Output is correct

Subtask #4
0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 39380 KB Output is correct
2 Correct 15 ms 39408 KB Output is correct
3 Correct 16 ms 39424 KB Output is correct
4 Correct 17 ms 39380 KB Output is correct
5 Correct 16 ms 39380 KB Output is correct
6 Correct 20 ms 39548 KB Output is correct
7 Correct 25 ms 39476 KB Output is correct
8 Correct 17 ms 39508 KB Output is correct
9 Correct 20 ms 39440 KB Output is correct
10 Correct 19 ms 39568 KB Output is correct
11 Correct 19 ms 39568 KB Output is correct
12 Correct 20 ms 39620 KB Output is correct
13 Correct 20 ms 39660 KB Output is correct
14 Runtime error 645 ms 1048576 KB Execution killed with signal 9
15 Halted 0 ms 0 KB -