oj.uz

Submission #373118

# Submission time Handle Problem Language Result Execution time Memory
373118 2021-03-03T12:38:20 Z sam571128 Sjeckanje (COCI21_sjeckanje) C++14
110 / 110
 779 ms 38124 KB 
#include <bits/stdc++.h>

#define int long long
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

using namespace std;

const int N = 2e5+5;
struct node{
	int dp[2][2], lval, rval;
};
node d[N*4];
int n,q;


node combine(node a, node b){
	node res;
	res.lval = a.lval, res.rval = b.rval;
	for(int i = 0;i < 2;i++){
		for(int j = 0;j < 2;j++){
			res.dp[i][j] = -1e14;
			res.dp[i][j] = max({res.dp[i][j], a.dp[i][0]+b.dp[1][j],a.dp[i][0]+b.dp[0][j],a.dp[i][1]+b.dp[0][j]});
			if(a.rval*b.lval >= 0) res.dp[i][j] = max(res.dp[i][j], a.dp[i][1]+b.dp[1][j]);
		}
	}
	return res;
}

void build(int arr[], int idx = 1, int l = 1, int r = n){
	if(l==r){
		d[idx].lval = d[idx].rval = arr[l];
		d[idx].dp[1][0] = d[idx].dp[0][1] = -1e14;
		d[idx].dp[0][0] = 0;
		d[idx].dp[1][1] = abs(arr[l]);
	}else{
		int mid = l+r>>1;
		build(arr,idx<<1,l,mid);
		build(arr,idx<<1|1,mid+1,r);
		d[idx] = combine(d[idx<<1],d[idx<<1|1]);
	}
}


void modify(int pos, int val, int idx = 1, int l = 1, int r = n){
	if(l==r){
		d[idx].lval += val;
		d[idx].rval += val;
		d[idx].dp[1][1] = abs(d[idx].lval);
		return;
	}else{
		int mid = l+r>>1;
		if(pos <= mid) modify(pos,val,idx<<1,l,mid);
		else modify(pos,val,idx<<1|1,mid+1,r);
		d[idx] = combine(d[idx<<1],d[idx<<1|1]);
	}
}

signed main(){
	fastio
	cin >> n >> q;
	int arr[n+1], dd[n+1] = {};
	for(int i = 1;i <= n;i++) cin >> arr[i];
	for(int i = 1;i < n;i++){
		dd[i] = arr[i+1]-arr[i];
	}
	build(dd);
	while(q--){
		int l,r,x;
		cin >> l >> r >> x;
		if(l>1) modify(l-1,x);
		if(r<n) modify(r,-x);
		cout << max({d[1].dp[0][0],d[1].dp[0][1],d[1].dp[1][0],d[1].dp[1][1]}) << "\n";
	}
}

Compilation message

Main.cpp: In function 'void build(long long int*, long long int, long long int, long long int)':
Main.cpp:36:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   36 |   int mid = l+r>>1;
      |             ~^~
Main.cpp: In function 'void modify(long long int, long long int, long long int, long long int, long long int)':
Main.cpp:51:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   51 |   int mid = l+r>>1;
      |             ~^~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 508 KB Output is correct
6 Correct 1 ms 364 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 508 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 7 ms 876 KB Output is correct
8 Correct 7 ms 876 KB Output is correct
9 Correct 7 ms 876 KB Output is correct
10 Correct 7 ms 876 KB Output is correct
11 Correct 7 ms 876 KB Output is correct
12 Correct 7 ms 876 KB Output is correct

Subtask #3
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 508 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 7 ms 876 KB Output is correct
8 Correct 7 ms 876 KB Output is correct
9 Correct 7 ms 876 KB Output is correct
10 Correct 7 ms 876 KB Output is correct
11 Correct 7 ms 876 KB Output is correct
12 Correct 7 ms 876 KB Output is correct
13 Correct 774 ms 35308 KB Output is correct
14 Correct 779 ms 37472 KB Output is correct
15 Correct 778 ms 37612 KB Output is correct
16 Correct 775 ms 37356 KB Output is correct
17 Correct 767 ms 37252 KB Output is correct
18 Correct 747 ms 38124 KB Output is correct