oj.uz

Submission #487802

# Submission time Handle Problem Language Result Execution time Memory
487802 2021-11-16T16:55:23 Z grt Sjeckanje (COCI21_sjeckanje) C++17
110 / 110
 969 ms 32260 KB 
#include <bits/stdc++.h>
#define PB push_back
#define ST first
#define ND second

//#pragma GCC optimize ("O3")
//#pragma GCC target("tune=native")

//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//using namespace __gnu_pbds;
//typedef tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

using namespace std;
using ll = long long;
using pi = pair<int, int>;
using vi = vector<int>;

const int nax = 200'000 + 10;
const ll INF = 1e18;
int n, q;
ll val[(1 << 18)];

struct Node {
	ll f[2][2];
	int l, r;
};

Node T[(1 << 19)];
int R;

Node combine(Node &a, Node &b) {
	Node c;
	for(int l : {0,1}) for(int r : {0,1}) c.f[l][r] = 0;
	for(int l : {0,1}) {
		for(int r : {0,1}) {
			for(int l1 : {0,1}) {
				for(int r1 : {0,1}) {
					if(l1 + r1 == 2 && (val[a.r] < 0 && val[b.l] > 0 || val[a.r] > 0 && val[b.l] < 0)) continue;
					c.f[l][r] = max(c.f[l][r], a.f[l][l1] + b.f[r1][r]);
				}
			}
		}
	}
	c.l = a.l;
	c.r = b.r;
	return c;
}

void upd(int a, ll x) {
	a += R;
	for(int l : {0,1}) {
		for(int r : {0,1}) {
			if(l != r) T[a].f[l][r] = 0;
			else if(r) T[a].f[l][r] = abs(x);
			else T[a].f[l][r] = 0;
		}
	}
	while(a > 1) {
		a /= 2;
		T[a] = combine(T[2*a], T[2*a+1]);
	}
}


int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> q;
	for(int i = 0; i < n; ++i) {
		cin >> val[i];
	}
	for(int i = 0; i < n - 1; ++i) {
		val[i] -= val[i + 1];
	}
	val[n - 1] = 0;
	R = 1;
	while(R < n) R *= 2;
	for(int i = R; i < R * 2; ++i) {
		T[i].l = T[i].r = i - R;
	}
	for(int i = 0; i < R; ++i) {
		upd(i, val[i]);
	}
	while(q--) {
		int l, r, x;
		cin >> l >> r >> x;
		l-=2;
		if(l >= 0) {
			val[l] -= x;
			upd(l, val[l]);
		}
		r--;
		if(r < n - 1) {
			val[r] += x;
			upd(r, val[r]);
		}
		ll ans = 0;
		for(int a : {0,1}) for(int b : {0,1}) ans = max(ans, T[1].f[a][b]);
		cout << ans << "\n";
	}
	
}

Compilation message

Main.cpp: In function 'Node combine(Node&, Node&)':
Main.cpp:40:39: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   40 |      if(l1 + r1 == 2 && (val[a.r] < 0 && val[b.l] > 0 || val[a.r] > 0 && val[b.l] < 0)) continue;
      |                          ~~~~~~~~~~~~~^~~~~~~~~~~~~~~

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 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 336 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 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 9 ms 792 KB Output is correct
8 Correct 8 ms 720 KB Output is correct
9 Correct 8 ms 796 KB Output is correct
10 Correct 8 ms 720 KB Output is correct
11 Correct 11 ms 720 KB Output is correct
12 Correct 8 ms 720 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 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 9 ms 792 KB Output is correct
8 Correct 8 ms 720 KB Output is correct
9 Correct 8 ms 796 KB Output is correct
10 Correct 8 ms 720 KB Output is correct
11 Correct 11 ms 720 KB Output is correct
12 Correct 8 ms 720 KB Output is correct
13 Correct 969 ms 31640 KB Output is correct
14 Correct 949 ms 31612 KB Output is correct
15 Correct 941 ms 31512 KB Output is correct
16 Correct 922 ms 31328 KB Output is correct
17 Correct 959 ms 31508 KB Output is correct
18 Correct 870 ms 32260 KB Output is correct