Submission #1145241

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

Main

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

const int maxn = 2e5 + 100;

long long int a[maxn];

struct Node
{
	int L, R, mid;
	long long int s[4];
	Node *lc, *rc;
	Node(int l, int r)
	{
		L = l, R = r, mid = (L + R) / 2, s[0] = s[1] = s[2] = s[3] = 0, lc = rc = NULL;
		return ;
	}

	void cu()
	{
		for (int i = 0;i < 4;i++)
		{
			int ul = i % 2, ur = (i >> 1);
			s[i] = lc->s[ul] + rc->s[ur * 2];
			s[i] = max(s[i], lc->s[ul + 2] + rc->s[ur * 2]);
			s[i] = max(s[i], lc->s[ul] + rc->s[ur * 2 + 1]);
			if ((a[mid] >= 0 and a[mid - 1] >= 0) or (a[mid] <= 0 and a[mid - 1] <= 0))
			{
				s[i] = max(s[i], lc->s[ul + 2] + rc->s[ur * 2 + 1]);
			}
		}
		return ;	
	}

	void init()
	{
		if (R == L)
		{
			return ;
		}
		if (R - L == 1)
		{
			s[3] = abs(a[L]);
			return ;
		}
		lc = new Node(L, mid);
		rc = new Node(mid, R);
		lc->init();
		rc->init();
		cu();
		return ;
	}

	void update(int p)
	{
		if (p < L or p >= R)
		{
			return ;
		}
		if (R - L == 1)
		{
			s[3] = abs(a[L]);
			return ;
		}
		if (p < mid)
		{
			lc->update(p);
		}
		else
		{
			rc->update(p);
		}
		cu();
		return ;
	}

	int get()
	{
		return max(max(s[0], s[1]), max(s[2], s[3]));
	}
};

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int n, q;
	cin >> n >> q;
	for (int i = 1;i <= n;i++)
	{
		cin >> a[i];
	}
	for (int i = 1;i <= n;i++)
	{
		a[i] = a[i + 1] - a[i];
	}
	Node *root = new Node(1, n);
	root->init();

//	cout << root->get() << endl;
//
//	for (int i = 1;i < n;i++)
//	{
//		cout << a[i] << ' ';
//	}
//	cout << endl;

	while (q--)
	{
		if (n == 1)
		{
			cout << 0 << endl;
			continue;
		}
		int l, r, x;
		cin >> l >> r >> x;
		if (l != 1)
		{
			a[l - 1] += x;
			root->update(l - 1);
		}
		if (r != n)
		{
			a[r] -= x;
			root->update(r);
		}

//		for (int i = 1;i < n;i++)
//		{
//			cout << a[i] << ' ';
//		}
//		cout << endl;

		cout << root->get() << endl;
	}
}

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