Submission #1119069

#	Time	Username	Problem	Language	Result	Execution time	Memory
1119069		Zflop	Sjeckanje (COCI21_sjeckanje)	C++14	0 / 110	2 ms	592 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int NMAX = 20;
int N,Q,A[NMAX],D[NMAX],L[NMAX],R[NMAX],t = 1;
int dp[NMAX * 4][2][2],border[NMAX * 4][2];
// 1 - e prezent capatul

void combine(int dad,int left,int right) {
	dp[dad][0][0] = dp[dad][0][1] = dp[dad][1][0] =  dp[dad][1][1] = 0;
	for (int l = 0; l < 2;++l) {
		for (int r = 0; r < 2;++r)
			for (int a = 0; a < 2;++a)
				for (int b = 0; b < 2;++b) {
					if (l && r) {
						if (border[left][1] * border[right][0] > 0)
							dp[dad][a][b] = max(dp[dad][a][b],dp[left][a][l] + dp[right][r][b]);
						}
					else {
						dp[dad][a][b] = max(dp[dad][a][b],dp[left][a][l] + dp[right][r][b]);
						}
					}
		}
	border[dad][0] = border[left][0];
	border[dad][1] = border[right][1];
	}
void add(int i,int v,int l,int r,int x) {
	if (l == r) {
		dp[x][0][0] = dp[x][0][1] = dp[x][1][0] = 0;
		border[x][0] += v;
		border[x][1] += v;
		dp[x][1][1] = abs(border[x][0]);
		return;
		}
	int mid = (l + r) / 2;
	if (L[x] == 0) {
		L[x] = ++t;
		}
	if (R[x] == 0) {
		R[x] = ++t;
		}
	if (i <= mid) add(i,v,l,mid,L[x]);
	else add(i,v,mid + 1,r,R[x]);
	combine(x,L[x],R[x]);
	//cout << l << ' ' << r << '\n';
	//cout << dp[x][0][0] << ' ' << dp[x][0][1] << ' ' << dp[x][1][0] << ' ' << dp[x][1][1] << '\n';
	}

void solve() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> N >> Q;
	for (int i = 1; i <= N;++i) {
		cin >> A[i]; 
		D[i] = A[i + 1] - A[i];
		if (i != N)
			add(i,D[i],1,N - 1,1);
		}
	for (int q = 1; q <= Q;++q) {
		int l,r,k; cin >> l >> r >> k;
		if (l > 1) add(l - 1,k,1,N - 1,1);
		if (r < N) add(r,-k,1,N - 1,1);
		cout << dp[1][1][1] << '\n';
		}
	}
main() {
	solve();
	}
// te-n gura gintule

Compilation message (stderr)

Main.cpp:67:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   67 | main() {
      | ^~~~

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