Submission #1152690

#	Time	Username	Problem	Language	Result	Execution time	Memory
1152690		siewjh	Sjeckanje (COCI21_sjeckanje)	C++20	0 / 110	1 ms	320 KiB

Main

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 200005;
ll fw[2][MAXN], ans;
int nums, queries;
set<pair<int, int>> zz;
void update(int p, int x, ll v){
	while (x <= nums){
		fw[p][x] += v;
		x += (x & (-x));
	}
}
ll query(int p, int x){
	ll ans = 0;
	while (x){
		ans += fw[p][x];
		x -= (x & (-x));
	}
	return ans;
}
ll cseg(int l, int r){
	return max(query(0, r) - query(0, l - 1), query(1, r) - query(1, l - 1));
}
int sign(ll x){
	return x > 0;
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cin >> nums >> queries;
	vector<ll> vec(nums + 1), diff(nums + 1);
	for (int i = 1; i <= nums; i++) cin >> vec[i];
	for (int i = 2; i <= nums; i++){
		diff[i] = vec[i] - vec[i - 1];
		update(i & 1, i, abs(diff[i]));
	}
	for (int i = 2, st = 2; i <= nums; i++){
		if (i == nums || sign(diff[i]) == sign(diff[i + 1])){
			zz.insert({st, i});
			ans += cseg(st, i);
			st = i + 1;
		}
	}
	while (queries--){
		int l, r; ll x; cin >> l >> r >> x; r++;
		if (l != 1){
			int lb = l, rb = l;
			auto it = zz.lower_bound({l, -1});
			if (it != zz.begin()) it--;
			while (it != zz.end() && it->first <= l + 1){
				lb = min(lb, it->first); rb = max(lb, it->second);
				ans -= cseg(it->first, it->second);
				it = zz.erase(it);
			}
			update(l & 1, l, abs(diff[l] + x) - abs(diff[l]));
			diff[l] += x;
			if (l == 2 || sign(diff[l - 1]) == sign(diff[l])){
				if (l != 2){
					ans += cseg(lb, l - 1); zz.insert({lb, l - 1});
				}
				if (l == nums || sign(diff[l]) == sign(diff[l + 1])){
					ans += cseg(l, l); zz.insert({l, l});
					if (l != nums){
						ans += cseg(l + 1, rb); zz.insert({l + 1, rb});
					}
				}
				else{
					ans += cseg(l, rb); zz.insert({l, rb});
				}
			}
			else{
				if (l == nums || sign(diff[l]) == sign(diff[l + 1])){
					ans += cseg(lb, l); zz.insert({lb, l});
					if (l != nums){
						ans += cseg(l + 1, rb); zz.insert({l + 1, rb});
					}
				}
				else{
					ans += cseg(lb, rb); zz.insert({lb, rb});
				}
			}
		}
		if (r != nums + 1){
			int lb = r, rb = r;
			auto it = zz.lower_bound({r, -1});
			if (it != zz.begin()) it--;
			while (it != zz.end() && it->first <= r + 1){
				lb = min(lb, it->first); rb = max(lb, it->second);
				ans -= cseg(it->first, it->second);
				it = zz.erase(it);
			}
			update(r & 1, r, abs(diff[r] - x) - abs(diff[r]));
			diff[r] -= x;
			if (r == 2 || sign(diff[r - 1]) == sign(diff[r])){
				if (r != 2){
					ans += cseg(lb, r - 1); zz.insert({lb, r - 1});
				}
				if (r == nums || sign(diff[r]) == sign(diff[r + 1])){
					ans += cseg(r, r); zz.insert({r, r});
					if (r != nums){
						ans += cseg(r + 1, rb); zz.insert({r + 1, rb});
					}
				}
				else{
					ans += cseg(r, rb); zz.insert({r, rb});
				}
			}
			else{
				if (r == nums || sign(diff[r]) == sign(diff[r + 1])){
					ans += cseg(lb, r); zz.insert({lb, r});
					if (r != nums){
						ans += cseg(r + 1, rb); zz.insert({r + 1, rb});
					}
				}
				else{
					ans += cseg(lb, rb); zz.insert({lb, rb});
				}
			}
		}
		cout << ans << '\n';
	}
}

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