oj.uz

Submission #868000

# Submission time Handle Problem Language Result Execution time Memory
868000 2023-10-30T07:08:46 Z _hbk06 Sjeckanje (COCI21_sjeckanje) C++17
110 / 110
 504 ms 186192 KB 
#include<bits/stdc++.h>
#define fi first
#define se second
#define ll long long
#define ull unsigned long long
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define sz(x) (int) (x).size()
#define MASK(n) (1 << (n))
#define BIT(mask,x) ((mask >> (x)) & 1)
#define TASK "recipe"

using namespace std;
const int mxN = 5e5 + 7;
const int base = 512;
const int inf = 1e9 + 6969;
const int Mod = 1e9 + 7;
const long long infll = 1e18 + 6969;

template <typename T1, typename T2> bool minimize(T1 &a, T2 b) {
     if (a > b) {a = b; return true;} return false;
}
template <typename T1, typename T2> bool maximize(T1 &a, T2 b) {
     if (a < b) {a = b; return true;} return false;
}

#define int long long

struct node {
	int dp[3][3];
	int val[2];
	node(int u = 0) {
		memset(dp,0,sizeof dp);
		dp[1][1] = abs(u);
		val[0] = val[1] = u;
	}
}Node[4 * mxN];

int n;
int q;
int a[mxN];


node merge(const node &x,const node &y) {
	node res;
	res.val[0] = x.val[0];
	res.val[1] = y.val[1];
	for (int i = 0; i <= 1; i++) for (int j = 0; j <= 1; j++) {
		maximize(res.dp[i][j],x.dp[i][0] + y.dp[0][j]);
		maximize(res.dp[i][j],x.dp[i][0] + y.dp[1][j]);
		maximize(res.dp[i][j],x.dp[i][1] + y.dp[0][j]);
		if(1LL * x.val[1] * y.val[0] >= 0) maximize(res.dp[i][j],x.dp[i][1] + y.dp[1][j]);
	} 
	return res;
}

void built(int id,int l,int r) {
	if(l == r) {
		Node[id] = node(a[l]);
		return;
	}
	int mid = (l + r) >> 1;
	built(id * 2,l,mid);
	built(id * 2 + 1,mid + 1,r);
	Node[id] = merge(Node[id * 2],Node[id * 2 + 1]);
}

void update(int id,int l,int r,int u) {
	if(u < l || u > r) return;
	if(l == r) {
		Node[id] = node(a[u]);
		return;
	}
	int mid = (l + r) >> 1;
	update(id * 2,l,mid,u);
	update(id * 2 + 1,mid + 1,r,u);
	Node[id] = merge(Node[id * 2],Node[id * 2 + 1]);
}

void solve() {
	cin >> n >> q;
	for (int i = 1; i <= n; i++) cin >> a[i];
	for (int i = 1; i < n; i++) a[i] = a[i + 1] - a[i];
	built(1,1,n - 1);
// cout << max(Node[1].dp[0][0],max(Node[1].dp[0][1],max(Node[1].dp[1][0],Node[1].dp[1][1])));
	while(q--) {
		int l,r,x;
		cin >> l >> r >> x;
		if(l > 1) {
			a[l - 1] += x;
			update(1,1,n - 1,l - 1);
		}
		a[r] -= x;
		if(r < n) update(1,1,n - 1,r);
		cout << max(Node[1].dp[0][0],max(Node[1].dp[0][1],max(Node[1].dp[1][0],Node[1].dp[1][1])));
		cout << '\n';
	}
}

signed main() {
	ios_base :: sync_with_stdio(0);
	cin.tie(0);
	//freopen(TASK".inp","r",stdin);
	//freopen(TASK".out","w",stdout);
	int tc = 1;
	//cin >> tc;
	while(tc--) {
		solve();
	}
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 174172 KB Output is correct
2 Correct 22 ms 174192 KB Output is correct
3 Correct 22 ms 174168 KB Output is correct
4 Correct 22 ms 174164 KB Output is correct
5 Correct 22 ms 174292 KB Output is correct
6 Correct 23 ms 174272 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 174172 KB Output is correct
2 Correct 22 ms 174192 KB Output is correct
3 Correct 22 ms 174168 KB Output is correct
4 Correct 22 ms 174164 KB Output is correct
5 Correct 22 ms 174292 KB Output is correct
6 Correct 23 ms 174272 KB Output is correct
7 Correct 26 ms 174424 KB Output is correct
8 Correct 26 ms 174428 KB Output is correct
9 Correct 26 ms 174304 KB Output is correct
10 Correct 27 ms 174416 KB Output is correct
11 Correct 27 ms 174280 KB Output is correct
12 Correct 26 ms 174396 KB Output is correct

Subtask #3
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 174172 KB Output is correct
2 Correct 22 ms 174192 KB Output is correct
3 Correct 22 ms 174168 KB Output is correct
4 Correct 22 ms 174164 KB Output is correct
5 Correct 22 ms 174292 KB Output is correct
6 Correct 23 ms 174272 KB Output is correct
7 Correct 26 ms 174424 KB Output is correct
8 Correct 26 ms 174428 KB Output is correct
9 Correct 26 ms 174304 KB Output is correct
10 Correct 27 ms 174416 KB Output is correct
11 Correct 27 ms 174280 KB Output is correct
12 Correct 26 ms 174396 KB Output is correct
13 Correct 453 ms 184660 KB Output is correct
14 Correct 485 ms 185468 KB Output is correct
15 Correct 504 ms 185500 KB Output is correct
16 Correct 478 ms 185428 KB Output is correct
17 Correct 453 ms 185684 KB Output is correct
18 Correct 420 ms 186192 KB Output is correct