oj.uz

Submission #482764

# Submission time Handle Problem Language Result Execution time Memory
482764 2021-10-26T09:53:14 Z iliaM Sjeckanje (COCI21_sjeckanje) C++17
0 / 110
 2 ms 588 KB 
#include <bits/stdc++.h>
using namespace std;

#define int long long 
inline void setmax(long long &a, long long b) {
	a = max(a, b);
}

constexpr int N = 2e5 + 10;

struct Node {
	long long dp[3][3], lz; //0: negative 2: positive
	
	inline void apply(long long x) {
		for (int i = 0; i < 3; ++i) {
			for (int j = 0; j < 3; ++j) {
				dp[i][j] += x * (i - 1 + j - 1);
			}
		}
		lz += x;
	}
};

Node t[N << 2];

int n, q, a[N];

inline void push(int c, int l, int r) {
	if (t[c].lz != 0) {
		t[l].apply(t[c].lz);
		t[r].apply(t[c].lz);
		t[c].lz = 0;
	}	
}

inline void pull(int c, int l, int r) {
	for (int i = 0; i < 3; ++i) {
		for (int j = 0; j < 3; ++j) {
			t[c].dp[i][j] = -1e18;
			setmax(t[c].dp[i][j], t[l].dp[i][1] + t[r].dp[1][j]);
			setmax(t[c].dp[i][j], t[l].dp[i][0] + t[r].dp[2][j]);
			setmax(t[c].dp[i][j], t[l].dp[i][2] + t[r].dp[0][j]);
		//	setmax(t[c].dp[i][j], t[l].dp[i][j] + t[r].dp[1][1]);
		//	setmax(t[c].dp[i][j], t[l].dp[1][1] + t[r].dp[i][j]);
		}
	}
}

void build(int c, int b, int e) {
	if (e - b == 1) {
		for (int i = 0; i < 3; ++i) {
			for (int j = 0; j < 3; ++j) {
				t[c].dp[i][j] = -8e18;
			}
		}
		t[c].dp[1][1] = 0;
		t[c].dp[1][2] = t[c].dp[2][1] = a[b];
		t[c].dp[1][0] = t[c].dp[0][1] = -a[b];
		return;
	}
	int m = (b + e) >> 1, l = c << 1, r = l | 1;
	build(l, b, m);
	build(r, m, e);
	pull(c, l, r);
}

void update(int c, int b, int e, int u, int v, long long x) {
	if (e <= u || v <= b) {
		return;
	}
	if (u <= b && e <= v) {
		t[c].apply(x);
		return;
	}
	int m = (b + e) >> 1, l = c << 1, r = l | 1;
	push(c, l, r);
	update(l, b, m, u, v, x);
	update(r, m, e, u, v, x);
	pull(c, l, r);
}

int32_t main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	cin >> n >> q;
	for (int i = 0; i < n; ++i) {
		cin >> a[i];
	}
	build(1, 0, n);
	
	while (q--) {
		int l, r, x;
		cin >> l >> r >> x;
		--l;
		update(1, 0, n, l, r, x);
		assert(t[1].dp[1][1] >= 0);
		cout << t[1].dp[1][1] << '\n';
	}
}

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 588 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 588 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #3
0 / 55.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 588 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -