Submission #940594

#	Time	Username	Problem	Language	Result	Execution time	Memory
940594		SamNguyen	Sjeckanje (COCI21_sjeckanje)	C++14	0 / 110	2 ms	2396 KiB

Main

#include <bits/stdc++.h>
using namespace std;

template <class T1, class T2>
inline bool minimise(T1 &x, T2 y) {
	if (x > y) { x = y; return true; }
	return false;
}

template <class T1, class T2>
inline bool maximise(T1 &x, T2 y) {
	if (x < y) { x = y; return true; }
	return false;
}

const int MAX = 2e5 + 7;
int N, Q;
long long arr[MAX];

void input() {
	cin >> N >> Q;
	for (int i = 1; i <= N; i++)
		cin >> arr[i];
}

void init() {
}

void update(int l, int r, long long x) {
	for (int i = l; i <= r; i++)
		arr[i] += x;
}

long long dp[MAX];

long long get() {
	long long res = 0;
	for (int i = 1; i < N; i++)	
		res += abs(arr[i] - arr[i + 1]);

	set<int> segs;
	for (int i = 2; i < N; i++)	{
		int d_left  = abs(arr[i - 1] - arr[i]);
		int d_right = abs(arr[i] - arr[i + 1]);

		// cerr << "* i = " << i << " -> " << d_left << " " << d_right << endl;

		if (d_left + d_right == arr[i - 1] - arr[i + 1])
			continue;

		if (d_left < d_right)
			segs.insert(i - 1);
		else
			segs.insert(i);
	}

	// cerr << "res = " << res << endl;
	for (int i : segs) {
		res -= abs(arr[i] - arr[i + 1]);
		// cerr << "+ res -= " << abs(arr[i] - arr[i + 1]) << endl;
	}

	return res;
}
	
int main(void) {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

	input();
	init();

	while (Q--) {
		int l, r; cin >> l >> r;
		long long x; cin >> x;
		update(l, r, x);
		cout << get() << '\n';
	}

	return 0;
}

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