Submission #530787

#	Time	Username	Problem	Language	Result	Execution time	Memory
530787		xuliu	Sjeckanje (COCI21_sjeckanje)	C++17	0 / 110	1 ms	296 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#define ll long long 
#define ld long double 
#define debug if(0)

const int mod = 1e9 + 7;
const ll infL = 1e18 + 7;
const int inf = 1e9 + 7;

void add(int &a, int b) { a = (a+b)%mod; }
int add(int a, int b, int c) { int res = (((a+b)%mod) + c)%mod; return res; }

#define T array<array<ll, 2>, 2>

struct segtree {
	int size;
	vector<T> seg;
	vector<ll> v;
	T ID;
	void init(int n) {
		ID[0][0] = ID[0][1] = ID[1][0] = ID[1][1] = 0;
		size = 1;
		while(size < n) size <<= 1;
		seg.assign(2*size+2, ID);
		v.assign(2*size+2, 0);
	}
	T comb(T a, T b, int pa, int pb) {
		T res;
		for(int i=0; i<2; i++) {
			for(int j=0; j<2; j++) {
				res[i][j] = max(a[i][0]+b[0][j], max(a[i][1]+b[0][j], a[i][0]+b[1][j]));
				if(v[pa]*v[pb] < 0) res[i][j] = max(res[i][j], a[i][1]+b[1][j]);
			}
		}
		return res;
	}
	void update(int i, ll val, int x, int lx, int rx) {
		if(lx == rx) {
			v[x] += val; seg[x][1][1] = abs(v[x]);
			return;
		}
		int m = (lx+rx)/2;
		if(i <= m) update(i, val, 2*x, lx, m);
		else update(i, val, 2*x+1, m+1, rx);
		seg[x] = comb(seg[2*x], seg[2*x+1], m, m+1);
	}
	void update(int i, ll val) { update(i, val, 1, 0, size-1); }
	ll query() {
		return max(max(seg[1][0][0], seg[1][1][0]), max(seg[1][0][1], seg[1][1][1]));
	}
	void print() {
		for(int i=size; i<(2*size); i++) cerr<<v[i]<<" ";
		cerr<<"\n";
	}
};

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	int n, q; cin>>n>>q;
	vector<int> x(n);
	segtree st;
	st.init(n+1);
	for(int i=0; i<n; i++) {
		cin>>x[i];
		if(i) st.update(i, x[i]-x[i-1]);
	}
	int kt = 0;
	while(q--) {
		kt++;
		int l, r; ll v; cin>>l>>r>>v; l--; r--;
		// [l, r] -> d[l] = x[l] - x[l-1] = (x'[l] + d) - x[l-1] = (x'[l] - x[l-1]) + d -> diff d[l] increase by v
		// [l, r] -> d[r+1] = x[r+1] - x[r] = x[r+1] - (x'[r] + d) = (x[r+1] - x'[r]) - d -> diff d[r+1] decrease by v
		if(l) st.update(l, v);
		if(r < (n-1)) st.update(r+1, -v);
		debug {
			if(kt == 2) {
				st.print();
			}
		}
		cout<<st.query()<<"\n";
	}
}

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