oj.uz

Submission #482967

# Submission time Handle Problem Language Result Execution time Memory
482967 2021-10-27T05:56:57 Z iliaM Sjeckanje (COCI21_sjeckanje) C++17
110 / 110
 910 ms 52696 KB 
#include <bits/stdc++.h>
using namespace std;

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

constexpr int N = 2e5 + 10, INF = 1e16;

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) {
				if (dp[i][j] <= -INF) {
					continue;
				}
				dp[i][j] += 1ll * x * (i - 1 + j - 1);
				setmax(dp[i][j], -INF);
			}
		}
		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] = -INF;
			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], max(t[l].dp[i][j], 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] = -INF;
			}
		}
		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);
		cout << t[1].dp[1][1] << '\n';
	}
}

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 328 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 328 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 7 ms 1100 KB Output is correct
8 Correct 8 ms 1100 KB Output is correct
9 Correct 9 ms 1100 KB Output is correct
10 Correct 6 ms 1100 KB Output is correct
11 Correct 7 ms 1100 KB Output is correct
12 Correct 7 ms 1068 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 328 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 7 ms 1100 KB Output is correct
8 Correct 8 ms 1100 KB Output is correct
9 Correct 9 ms 1100 KB Output is correct
10 Correct 6 ms 1100 KB Output is correct
11 Correct 7 ms 1100 KB Output is correct
12 Correct 7 ms 1068 KB Output is correct
13 Correct 820 ms 52096 KB Output is correct
14 Correct 836 ms 52208 KB Output is correct
15 Correct 807 ms 52100 KB Output is correct
16 Correct 910 ms 52000 KB Output is correct
17 Correct 824 ms 51880 KB Output is correct
18 Correct 799 ms 52696 KB Output is correct