Submission #1160743

#	Time	Username	Problem	Language	Result	Execution time	Memory
1160743		thelegendary08	Sjeckanje (COCI21_sjeckanje)	C++17	110 / 110	998 ms	62684 KiB

Main

#include<bits/stdc++.h>
#define f0r(i,n) for(int i = 0; i<n; i++)
#define pb push_back
#define vi vector<long long int>
#define ll long long int
#define mp make_pair
#define pii pair<ll,ll>
#define FOR(i, k, n) for(int i = k; i<n; i++)
using namespace std;
const int mxn = 2e5 + 5;
ll d[mxn];
vector<vector<ll>>tree(mxn * 4, vector<ll>(4));
vector<ll> merge(vi a, vi b, bool same){
	if(same){
		return {max(a[0], a[1]) + max(b[0], b[2]), max(a[0], a[1]) + max(b[1], b[3]), max(a[2], a[3]) + max(b[0], b[2]), max(a[2], a[3]) + max(b[1], b[3])};
	}
	else{
		return {max(a[0] + b[2], max(a[1] + b[0], a[0] + b[0])), max(a[1] + b[1], max(a[0] + b[3], a[0] + b[1])), max(a[2] + b[2], max(a[3] + b[0], a[2] + b[0])), max(a[3] + b[1], max(a[2] + b[3], a[2] + b[1]))};
	}
}
vector<ll> build(int l, int r, int node = 1){
	if(l == r){
		tree[node] = {0, (ll)-1e17, (ll)-1e17, abs(d[l])};
		return tree[node];
	}
	else{
		int mid = (l + r) / 2;
		tree[node] = merge(build(l, mid, node * 2), build(mid + 1, r, node * 2 + 1),!((d[mid] > 0 &&  d[mid + 1] < 0) || (d[mid] < 0 && d[mid + 1] > 0)));
		return tree[node];
	}
	
}
int n;
void update(int k, int l, int r, int node = 1){
	
	if(l == r){
		// f0r(i,n-1)cout<<d[i]<<' ';
		// cout<<'\n';	
		tree[node] = {0, (ll)-1e17, (ll)-1e17, abs(d[l])};
	}
	else{
		int mid = (l + r) / 2;
		if(k <= mid){
			update(k, l, mid, node * 2);
		}
		else{
			update(k, mid + 1, r, node * 2 + 1);
		}
		tree[node] = merge(tree[node * 2], tree[node * 2 + 1], !((d[mid] > 0 &&  d[mid + 1] < 0) || (d[mid] < 0 && d[mid + 1] > 0)));
	}
}
int main(){
	cin>>n; int q; cin>>q;
	vi v(n);
	f0r(i,n)cin>>v[i];
	f0r(i,n-1){
		d[i] = v[i+1] - v[i];
	}
	// f0r(i,n-1)cout<<d[i]<<' ';
	// cout<<'\n';
	build(0, n-2);
	// cout<<max(tree[1][0], max(tree[1][1], max(tree[1][2], tree[1][3])))<<'\n';
	while(q--){
		int l,r,x;
		cin>>l>>r>>x;
		l--; r--;
		if(l != 0){
			d[l-1] += x;
			update(l-1, 0, n-2);
		}
		if(r != n-1){
			d[r]-=x;
			update(r, 0, n-2);
		}
		// f0r(i,n-1)cout<<d[i]<<' ';
		// cout<<'\n';
		cout<<max(tree[1][0], max(tree[1][1], max(tree[1][2], tree[1][3])))<<'\n';
	}	
}

• Subtask 1: 15 / 15
• Subtask 2: 40 / 40
• Subtask 3: 55 / 55