oj.uz

Submission #377666

# Submission time Handle Problem Language Result Execution time Memory
377666 2021-03-14T16:28:17 Z maximath_1 Sjeckanje (COCI21_sjeckanje) C++11
110 / 110
 763 ms 29696 KB 
#include <iostream>
#include <math.h>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <assert.h>
#include <set>
#include <functional>
#include <limits.h>
#include <map>
#include <queue>
using namespace std;

#define ll long long
#define ld long double
#define endl "\n"
const int MX = 200005;
const int BLOCK = 350;
const ll mod = 998244353;

int n, q;
ll v[MX], diff[MX];
ll st[4 * MX][2][2]; // neg pos

void upd(int nd, int cl, int cr, int ps){
	if(ps < cl || cr < ps) return;
	if(cl == cr && cl == ps) return void(st[nd][1][1] = abs(diff[ps]));

	upd(nd * 2, cl, (cl + cr) / 2, ps);
	upd(nd * 2 + 1, (cl + cr) / 2 + 1, cr, ps);

	for(int i = 0; i < 4; i ++){
		st[nd][i / 2][i % 2] = 0;
		for(int j = 0; j < 2; j ++)
			st[nd][i / 2][i % 2] = max(st[nd][i / 2][i % 2], 
				st[nd * 2][i / 2][j] + st[nd * 2 + 1][1 - j][i % 2]);
	}

	if((diff[(cl + cr) / 2] >= 0 && diff[(cl + cr) / 2 + 1] >= 0) || (diff[(cl + cr) / 2] <= 0 && diff[(cl + cr) / 2 + 1] <= 0)){
		for(int i = 0; i < 4; i ++){
			st[nd][i / 2][i % 2] = max(st[nd * 2][i / 2][0], st[nd * 2][i / 2][1]) 
					+ max(st[nd * 2 + 1][0][i % 2], st[nd * 2 + 1][1][i % 2]);
		}
	}
}

int main(){
	cin.tie(0) -> sync_with_stdio(0);

	cin >> n >> q;
	for(int i = 1; i <= n; i ++)
		cin >> v[i];
	for(int i = 1; i < n; i ++){
		diff[i] = v[i + 1] - v[i];
		upd(1, 1, n - 1, i);
	}

	for(int l, r, x; q --;){
		cin >> l >> r >> x;

		diff[r] -= x;
		upd(1, 1, n - 1, r);

		if(l - 1 > 0){
			diff[l - 1] += x;
			upd(1, 1, n - 1, l - 1);
		}

		ll ans = 0ll;
		for(int i = 0; i < 4; i ++)
			ans = max(ans, st[1][i / 2][i % 2]);
		cout << ans << endl;
	}

	return 0;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 7 ms 748 KB Output is correct
8 Correct 6 ms 748 KB Output is correct
9 Correct 8 ms 748 KB Output is correct
10 Correct 6 ms 748 KB Output is correct
11 Correct 6 ms 748 KB Output is correct
12 Correct 6 ms 876 KB Output is correct

Subtask #3
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 7 ms 748 KB Output is correct
8 Correct 6 ms 748 KB Output is correct
9 Correct 8 ms 748 KB Output is correct
10 Correct 6 ms 748 KB Output is correct
11 Correct 6 ms 748 KB Output is correct
12 Correct 6 ms 876 KB Output is correct
13 Correct 723 ms 29260 KB Output is correct
14 Correct 763 ms 29060 KB Output is correct
15 Correct 685 ms 29164 KB Output is correct
16 Correct 681 ms 29036 KB Output is correct
17 Correct 716 ms 29036 KB Output is correct
18 Correct 611 ms 29696 KB Output is correct