Submission #615848

#	Time	Username	Problem	Language	Result	Execution time	Memory
615848		zhangjishen	Sjeckanje (COCI21_sjeckanje)	C++98	110 / 110	565 ms	37768 KiB

Main

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

typedef long long ll;
const int MAXN = 2e5 + 10;

// Node structure
struct Node{
	ll lv, rv, dp[2][2];
};

Node merge(Node L, Node R){
	Node ans;
	ans.lv = L.lv; ans.rv = R.rv;
	if(L.rv * R.lv >= 0){
		ans.dp[0][0] = L.dp[0][0] + R.dp[0][0];
		ans.dp[0][1] = L.dp[0][0] + R.dp[0][1];
		ans.dp[1][0] = L.dp[1][0] + R.dp[0][0];
		ans.dp[1][1] = L.dp[1][0] + R.dp[0][1];
	}else{
		ans.dp[0][0] = max(L.dp[0][1] + R.dp[0][0], L.dp[0][0] + R.dp[1][0]);
		ans.dp[0][1] = max(L.dp[0][1] + R.dp[0][1], L.dp[0][0] + R.dp[1][1]);
		ans.dp[1][0] = max(L.dp[1][1] + R.dp[0][0], L.dp[1][0] + R.dp[1][0]);
		ans.dp[1][1] = max(L.dp[1][1] + R.dp[0][1], L.dp[1][0] + R.dp[1][1]);
	}
	return ans;
}

// Segment Tree
Node t[MAXN * 4];

void pushup(int u){
	t[u] = merge(t[u * 2], t[u * 2 + 1]);
}

void biuld(int u, int l, int r, ll a[]){
	if(l == r){
		t[u].lv = t[u].rv = a[l];
		t[u].dp[0][0] = abs(a[l]);
		t[u].dp[0][1] = t[u].dp[1][0] = t[u].dp[1][1] = 0;
		return;
	}
	int mid = (l + r) / 2;
	biuld(u * 2, l, mid, a);
	biuld(u * 2 + 1, mid + 1, r, a);
	pushup(u);
}

void update(int u, int l, int r, int p, ll k){
	if(l == r){
		t[u].lv += k; t[u].rv += k;
		t[u].dp[0][0] = abs(t[u].lv);
		t[u].dp[0][1] = t[u].dp[1][0] = t[u].dp[1][1] = 0;
		return;
	}
	int mid = (l + r) / 2;
	if(p <= mid)
		update(u * 2, l, mid, p, k);
	else update(u * 2 + 1, mid + 1, r, p, k);
	pushup(u);
}

int n, q;
ll a[MAXN], d[MAXN];
int main(){
	// input
	scanf("%d %d", &n, &q);
	for(int i = 1; i <= n; i++)
		scanf("%lld", &a[i]);
	// solve
	if(n == 1){	// special case
		for(int i = 1; i <= q; i++)
			printf("0\n");
	}else{
		// prework
		for(int i = 1; i <= n - 1; i++)
			d[i] = a[i + 1] - a[i];
		biuld(1, 1, n - 1, d);
		// query
		int l, r; ll k;
		for(int i = 1; i <= q; i++){
			scanf("%d %d %lld", &l, &r, &k);
			if(l - 1 >= 1)
				update(1, 1, n - 1, l - 1, k);
			if(r <= n - 1)
				update(1, 1, n - 1, r, -k);
			printf("%lld\n", t[1].dp[0][0]);
		}
	}
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:67:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   67 |  scanf("%d %d", &n, &q);
      |  ~~~~~^~~~~~~~~~~~~~~~~
Main.cpp:69:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   69 |   scanf("%lld", &a[i]);
      |   ~~~~~^~~~~~~~~~~~~~~
Main.cpp:82:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   82 |    scanf("%d %d %lld", &l, &r, &k);
      |    ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

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