Submission #568094

#	Time	Username	Problem	Language	Result	Execution time	Memory
568094		nonsensenonsense1	Ants and Sugar (JOI22_sugar)	C++17	100 / 100	1354 ms	73292 KiB

sugar

#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 (stderr)

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 / 6
• Subtask 2: 16 / 16
• Subtask 3: 26 / 26
• Subtask 4: 52 / 52