Submission #447288

#	Time	Username	Problem	Language	Result	Execution time	Memory
447288		socho	Sjeckanje (COCI21_sjeckanje)	C++14	110 / 110	916 ms	38204 KiB

Main

#include <bits/stdc++.h>
using namespace std;
void fast() {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
}
void ran() {
	srand(chrono::steady_clock::now().time_since_epoch().count());
}
long long get_rand() {
	long long a = rand();
	long long b = rand();
	return a * (RAND_MAX + 1ll) + b;
}
void usaco() {
	freopen("problem.in", "r", stdin); 
	freopen("problem.out", "w", stdout);
}
template<typename T>
using min_pq = priority_queue<T, vector<T>, greater<T>>;
// #define endl '\n'
// #define double long double
#define int long long
// const int MOD = 1000 * 1000 * 1000 + 7;
// const int MOD = 998244353;

int n, q;
const int MXN = 200005;
int arr[MXN];
int df[MXN];

struct info {
	
	int with[2][2] = {{0}}; // first and last, taken or not taken
	
	info() {
		with[0][0] = with[0][1] = with[1][0] = with[1][1] = 0;
	}
	
} seg[MXN * 4];

info get(int x) {
	info res;
	res.with[1][1] = abs(x);
	return res;
}

int sg(int x) {
	if (x > 0) return 1;
	if (x < 0) return -1;
	return 0;
}

info comb(info l, info r, int m) {
	
	info res;
	
	bool cantog = (df[m] <= 0 && df[m+1] <= 0) || (df[m] >= 0 && df[m+1] >= 0);
	if (cantog) {
		
		for (int L=0; L<2; L++) {
			for (int R=0; R<2; R++) {
				for (int k=0; k<2; k++) for (int m=0; m<2; m++) {
					res.with[L][R] = max(res.with[L][R], l.with[L][k] + r.with[m][R]);
				}
			}
		}
		
		
		
	}
	else {
		
		for (int L=0; L<2; L++) {
			for (int R=0; R<2; R++) {
				for (int k=0; k<2; k++) for (int m=0; m<2; m++) {
					if (k == 1 && m == 1) continue;
					else res.with[L][R] = max(res.with[L][R], l.with[L][k] + r.with[m][R]);
				}
			}
		}
		
	}
	
	return res;
	
}

void build(int ind, int l, int r) {
	if (l == r) {
		seg[ind] = get(df[l]);
		return;
	}
	int m = (l + r) / 2;
	build(ind*2, l, m);
	build(ind*2+1, m+1, r);
	seg[ind] = comb(seg[ind*2], seg[ind*2+1], m);
}

void update(int ind, int l, int r, int pos) {
	if (l == r) {
		seg[ind] = get(df[l]);
		return;
	}
	int m = (l + r) / 2;
	if (pos <= m) update(ind*2, l, m, pos);
	else update(ind*2+1, m+1, r, pos);
	seg[ind] = comb(seg[ind*2], seg[ind*2+1], m);
}

int best() {
	int a = 0;
	for (int i=0; i<2; i++) for (int j=0; j<2; j++) a = max(a, seg[1].with[i][j]);
	return a;
}

signed main() {

	ran(); fast();

	cin >> n >> q;
	for (int i=1; i<=n; i++) cin >> arr[i];
	
	if (n == 1) {
		for (int i=0; i<q; i++) cout << 0 << endl;
		exit(0);
	}
	
	for (int i=1; i<n; i++) df[i] = arr[i+1] - arr[i];

	build(1, 1, n-1);
	
	while (q--) {
		int l, r, k;
		cin >> l >> r >> k;
		if (l > 1) {
			df[l-1] += k;
			update(1, 1, n-1, l-1);
		}
		if (r < n) {
			df[r] -= k;
			update(1, 1, n-1, r);
		}
		cout << best() << endl;
		
	}

}

Compilation message (stderr)

Main.cpp: In function 'void usaco()':
Main.cpp:15:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   15 |  freopen("problem.in", "r", stdin);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:16:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   16 |  freopen("problem.out", "w", stdout);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

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