oj.uz

Submission #484286

# Submission time Handle Problem Language Result Execution time Memory
484286 2021-11-02T21:15:43 Z rainboy Sjeckanje (COCI21_sjeckanje) C
110 / 110
 1016 ms 49384 KB 
#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

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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 9 ms 972 KB Output is correct
8 Correct 10 ms 1012 KB Output is correct
9 Correct 10 ms 972 KB Output is correct
10 Correct 10 ms 972 KB Output is correct
11 Correct 11 ms 1016 KB Output is correct
12 Correct 8 ms 972 KB Output is correct

Subtask #3
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 9 ms 972 KB Output is correct
8 Correct 10 ms 1012 KB Output is correct
9 Correct 10 ms 972 KB Output is correct
10 Correct 10 ms 972 KB Output is correct
11 Correct 11 ms 1016 KB Output is correct
12 Correct 8 ms 972 KB Output is correct
13 Correct 1016 ms 48596 KB Output is correct
14 Correct 955 ms 48732 KB Output is correct
15 Correct 1000 ms 48620 KB Output is correct
16 Correct 961 ms 48600 KB Output is correct
17 Correct 936 ms 48472 KB Output is correct
18 Correct 927 ms 49384 KB Output is correct