oj.uz

Submission #670584

# Submission time Handle Problem Language Result Execution time Memory
670584 2022-12-09T15:19:47 Z vovamr Sjeckanje (COCI21_sjeckanje) C++17
110 / 110
 1565 ms 71484 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define fi first
#define se second
#define ll long long
#define ld long double
#define sz(x) ((int)(x).size())
#define all(x) 	(x).begin(), (x).end()
#define pb push_back
#define mpp make_pair
#define ve vector
using namespace std;
using namespace __gnu_pbds;
template<class T> using oset = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
const ll inf = 1e18; const int iinf = 1e9;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
template <typename T> inline bool chmin(T& a, T b) { return (a > b ? a = b, 1 : 0); }
template <typename T> inline bool chmax(T& a, T b) { return (a < b ? a = b, 1 : 0); }

const int N = 2e5 + 100;
struct st {
	ll a[3][3];
	// 0 - neg, 1 - none, 2 - pos
	// left, right
	st() {
		for (int i = 0; i < 3; ++i) {
			for (int j = 0; j < 3; ++j) {
				a[i][j] = -inf;
			}
		}
	}
	st(ll x) {
		for (int i = 0; i < 3; ++i) {
		for (int j = 0; j < 3; ++j) {
			a[i][j] = -inf;
		}}
		a[1][1] = 0;
		a[0][1] = -x;
		a[1][0] = -x;
		a[2][1] = x;
		a[1][2] = x;
	}
} t[4 * N];
inline st mg(const st &a, const st &b) {
	st res;
	for (int i = 0; i < 3; ++i) {
	for (int j = 0; j < 3; ++j) {
		for (int z = 0; z < 3; ++z) {
		for (int k = 0; k < 3; ++k) {
			if (j + z == 2) chmax(res.a[i][k], a.a[i][j] + b.a[z][k]);
		}}
	}}
	for (int i = 0; i < 3; ++i) {
	for (int j = 0; j < 3; ++j) {
		chmax(res.a[i][j], a.a[i][j]);
		chmax(res.a[i][j], b.a[i][j]);
	}} return res;
}

ll p[4 * N];
int a[N];

inline void build(int v, int vl, int vr) {
	if (vl == vr) return void(t[v] = st(a[vl]));
	int m = vl + vr >> 1;
	build(2 * v + 1, vl, m);
	build(2 * v + 2, m + 1, vr);
	t[v] = mg(t[2 * v + 1], t[2 * v + 2]);
}
inline void push(int v) {
	if (!p[v]) return;
	for (int u : {2 * v + 1, 2 * v + 2}) {
		p[u] += p[v];
		for (int i = 0; i < 3; ++i) {
		for (int j = 0; j < 3; ++j) {
			ll to_add = 0;
			to_add += (i == 0 ? -p[v] : (i == 1 ? 0 : p[v]));
			to_add += (j == 0 ? -p[v] : (j == 1 ? 0 : p[v]));
			t[u].a[i][j] += to_add;

		}}
	}
	p[v] = 0;
}
inline void upd(int v, int vl, int vr, int l, int r, int x) {
	if (l > r) return;
	else if (vl == l && vr == r) {
		p[v] += x;
		for (int i = 0; i < 3; ++i) {
		for (int j = 0; j < 3; ++j) {
			ll to_add = 0;
			to_add += (i == 0 ? -x : (i == 1 ? 0 : x));
			to_add += (j == 0 ? -x : (j == 1 ? 0 : x));
			t[v].a[i][j] += to_add;
		}}
		return;
	}
	push(v);
	int m = vl + vr >> 1;
	upd(2 * v + 1, vl, m, l, min(r, m), x);
	upd(2 * v + 2, m + 1, vr, max(l, m + 1), r, x);
	t[v] = mg(t[2 * v + 1], t[2 * v + 2]);
}

inline void solve() {
	int n, q;
	cin >> n >> q;
	for (int i = 0; i < n; ++i) cin >> a[i];

	build(0, 0, n - 1);

	while (q--) {
		int l, r, x;
		cin >> l >> r >> x;
		upd(0, 0, n - 1, --l, --r, x);

		cout << t[0].a[1][1] << '\n';
	}
}

signed main() {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	int q = 1; // cin >> q;
	while (q--) solve();
	cerr << fixed << setprecision(3) << "Time execution: " << (double)clock() / CLOCKS_PER_SEC << endl;
}

Compilation message

Main.cpp: In function 'void build(int, int, int)':
Main.cpp:68:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   68 |  int m = vl + vr >> 1;
      |          ~~~^~~~
Main.cpp: In function 'void upd(int, int, int, int, int, int)':
Main.cpp:102:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  102 |  int m = vl + vr >> 1;
      |          ~~~^~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 56712 KB Output is correct
2 Correct 24 ms 56720 KB Output is correct
3 Correct 24 ms 56708 KB Output is correct
4 Correct 24 ms 56628 KB Output is correct
5 Correct 23 ms 56696 KB Output is correct
6 Correct 25 ms 56712 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 56712 KB Output is correct
2 Correct 24 ms 56720 KB Output is correct
3 Correct 24 ms 56708 KB Output is correct
4 Correct 24 ms 56628 KB Output is correct
5 Correct 23 ms 56696 KB Output is correct
6 Correct 25 ms 56712 KB Output is correct
7 Correct 36 ms 56908 KB Output is correct
8 Correct 36 ms 56908 KB Output is correct
9 Correct 35 ms 56832 KB Output is correct
10 Correct 36 ms 56852 KB Output is correct
11 Correct 37 ms 56904 KB Output is correct
12 Correct 36 ms 56908 KB Output is correct

Subtask #3
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 56712 KB Output is correct
2 Correct 24 ms 56720 KB Output is correct
3 Correct 24 ms 56708 KB Output is correct
4 Correct 24 ms 56628 KB Output is correct
5 Correct 23 ms 56696 KB Output is correct
6 Correct 25 ms 56712 KB Output is correct
7 Correct 36 ms 56908 KB Output is correct
8 Correct 36 ms 56908 KB Output is correct
9 Correct 35 ms 56832 KB Output is correct
10 Correct 36 ms 56852 KB Output is correct
11 Correct 37 ms 56904 KB Output is correct
12 Correct 36 ms 56908 KB Output is correct
13 Correct 1565 ms 70904 KB Output is correct
14 Correct 1546 ms 70760 KB Output is correct
15 Correct 1546 ms 70680 KB Output is correct
16 Correct 1552 ms 70628 KB Output is correct
17 Correct 1552 ms 70476 KB Output is correct
18 Correct 1541 ms 71484 KB Output is correct