Submission #484286

#	Time	Username	Problem	Language	Result	Execution time	Memory
484286		rainboy	Sjeckanje (COCI21_sjeckanje)	C11	110 / 110	1016 ms	49384 KiB

Main

#include <stdio.h>

#define N	200000
#define H_	18	/* H_ = ceil(log2(N)) */
#define N_	(1 << H_)
#define INF	0x3f3f3f3f3f3f3f3fLL

long long max(long long a, long long b) { return a > b ? a : b; }

long long st[N_ * 2][3][3], lz[N_]; int h_, n_;

void put(int i, long long x) {
	int a, b;

	for (a = 0; a < 3; a++)
		for (b = 0; b < 3; b++)
			if (st[i][a][b] != -INF) {
				if (a == 1)
					st[i][a][b] -= x;
				else if (a == 2)
					st[i][a][b] += x;
				if (b == 1)
					st[i][a][b] += x;
				else if (b == 2)
					st[i][a][b] -= x;
			}
	if (i < n_)
		lz[i] += x;
}

void pus(int i) {
	if (lz[i])
		put(i << 1 | 0, lz[i]), put(i << 1 | 1, lz[i]), lz[i] = 0;
}

void pul(int i) {
	if (!lz[i]) {
		int l = i << 1, r = l | 1, a, b, c;

		for (a = 0; a < 3; a++)
			for (b = 0; b < 3; b++)
				st[i][a][b] = -INF;
		for (a = 0; a < 3; a++)
			for (b = 0; b < 3; b++) {
				long long x = st[l][a][b];

				for (c = 0; c < 3; c++) {
					long long y = st[r][b][c];

					if (x != -INF && y != -INF)
						st[i][a][c] = max(st[i][a][c], x + y);
				}
			}
	}
}

void push(int i) {
	int h;

	for (h = h_; h > 0; h--)
		pus(i >> h);
}

void pull(int i) {
	while (i > 1)
		pul(i >>= 1);
}

void build(int *aa, int n) {
	int i, a, b;

	while (1 << h_ < n)
		h_++;
	n_ = 1 << h_;
	for (i = 0; i < n_; i++) {
		for (a = 0; a < 3; a++)
			for (b = 0; b < 3; b++)
				st[n_ + i][a][b] = a == b ? 0 : -INF;
		if (i < n) {
			st[n_ + i][0][1] = st[n_ + i][2][0] = aa[i];
			st[n_ + i][0][2] = st[n_ + i][1][0] = -aa[i];
		}
	}
	for (i = n_ - 1; i > 0; i--)
		pul(i);
}

void update(int l, int r, int x) {
	int l_ = l += n_, r_ = r += n_;

	push(l_), push(r_);
	for ( ; l <= r; l >>= 1, r >>= 1) {
		if ((l & 1) == 1)
			put(l++, x);
		if ((r & 1) == 0)
			put(r--, x); }
	pull(l_), pull(r_);
}

int main() {
	static int aa[N];
	int n, q, i;

	scanf("%d%d", &n, &q);
	for (i = 0; i < n; i++)
		scanf("%d", &aa[i]);
	build(aa, n);
	while (q--) {
		int l, r, x;

		scanf("%d%d%d", &l, &r, &x), l--, r--;
		update(l, r, x);
		printf("%lld\n", st[1][0][0]);
	}
	return 0;
}

Compilation message (stderr)

Main.c: In function 'main':
Main.c:104:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  104 |  scanf("%d%d", &n, &q);
      |  ^~~~~~~~~~~~~~~~~~~~~
Main.c:106:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  106 |   scanf("%d", &aa[i]);
      |   ^~~~~~~~~~~~~~~~~~~
Main.c:111:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  111 |   scanf("%d%d%d", &l, &r, &x), l--, r--;
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 15 / 15
• Subtask 2: 40 / 40
• Subtask 3: 55 / 55