oj.uz

Submission #615848

# Submission time Handle Problem Language Result Execution time Memory
615848 2022-07-31T13:20:31 Z zhangjishen Sjeckanje (COCI21_sjeckanje) C++
110 / 110
 565 ms 37768 KB 
#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

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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 316 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 288 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 316 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 288 KB Output is correct
7 Correct 4 ms 860 KB Output is correct
8 Correct 6 ms 836 KB Output is correct
9 Correct 4 ms 836 KB Output is correct
10 Correct 5 ms 852 KB Output is correct
11 Correct 5 ms 836 KB Output is correct
12 Correct 5 ms 852 KB Output is correct

Subtask #3
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 316 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 288 KB Output is correct
7 Correct 4 ms 860 KB Output is correct
8 Correct 6 ms 836 KB Output is correct
9 Correct 4 ms 836 KB Output is correct
10 Correct 5 ms 852 KB Output is correct
11 Correct 5 ms 836 KB Output is correct
12 Correct 5 ms 852 KB Output is correct
13 Correct 565 ms 37184 KB Output is correct
14 Correct 532 ms 37152 KB Output is correct
15 Correct 509 ms 37092 KB Output is correct
16 Correct 487 ms 37028 KB Output is correct
17 Correct 490 ms 36988 KB Output is correct
18 Correct 506 ms 37768 KB Output is correct