Submission #1099230

#	Time	Username	Problem	Language	Result	Execution time	Memory
1099230		hiensumi	Sjeckanje (COCI21_sjeckanje)	C++14	110 / 110	293 ms	30020 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define fod(i,a,b) for(int i = (int) (a); i <= (int) (b); i++)
#define fok(i,a,b) for(int i = (int) (a); i >= (int) (b); i--)
#define ll long long
#define pb pusi_back
#define pii pair<int,int>
#define mp make_pair
#define fi first
#define se second
#define el '\n'
#define ve vector
#define vi ve<int>
#define vll ve<ll>
#define mask(a) (1LL<<(a))
#define BIT(msk,i) (msk>>(i)&1LL)
using namespace std;
template <class T> bool mini(T &a, T b){ return (a > (b)) ? a = (b), 1 : 0; }
template <class T> bool maxi(T &a, T b){ return (a < (b)) ? a = (b), 1 : 0; }
#define name "sjeckanje"

int n, q;

const int N = 2e5;
ll a[N + 5];

ll dp[N + 5][3];

int solve(){
    dp[0][0] = 0;
    dp[0][1] = dp[0][2] = -1e15;

    fod(i,1,n){
        dp[i][0] = max({dp[i-1][1] - a[i], dp[i-1][2] + a[i], dp[i-1][0]});
        dp[i][1] = max(dp[i-1][1], dp[i-1][0] + a[i]);
        dp[i][2] = max(dp[i-1][2], dp[i-1][0] - a[i]);
    }

    return dp[n][0];
}

ll d[N + 5];
ll st[4 * N][2][2];

void upd(int u, int i = 1, int l = 1, int r = n - 1){
	if(r < u or u < l) return;
	if(l == r){
		st[i][1][1] = abs(d[l]);
		return;
	}
	int mid = l + r >> 1;
	upd(u,i<<1,l,mid);
	upd(u,i<<1|1,mid+1,r);
	
	st[i][1][1] = max(st[i<<1][1][0] + st[i<<1|1][1][1], st[i<<1][1][1] + st[i<<1|1][0][1]);
	st[i][1][0] = max(st[i<<1][1][0] + st[i<<1|1][1][0], st[i<<1][1][1] + st[i<<1|1][0][0]);
	st[i][0][1] = max(st[i<<1][0][0] + st[i<<1|1][1][1], st[i<<1][0][1] + st[i<<1|1][0][1]);
	st[i][0][0] = max(st[i<<1][0][0] + st[i<<1|1][1][0], st[i<<1][0][1] + st[i<<1|1][0][0]);

	if((d[mid] >= 0 and d[mid + 1] >= 0) or (d[mid] <= 0 and d[mid + 1] <= 0)){
		st[i][1][1] = max(st[i<<1][1][0], st[i<<1][1][1]) + max(st[i<<1|1][0][1], st[i<<1|1][1][1]);
		st[i][1][0] = max(st[i<<1][1][0], st[i<<1][1][1]) + max(st[i<<1|1][0][0], st[i<<1|1][1][0]);
		st[i][0][1] = max(st[i<<1][0][0], st[i<<1][0][1]) + max(st[i<<1|1][0][1], st[i<<1|1][1][1]);
		st[i][0][0] = max(st[i<<1][0][0], st[i<<1][0][1]) + max(st[i<<1|1][0][0], st[i<<1|1][1][0]);
	}
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0);

    cin >> n >> q;
    fod(i,1,n) cin >> a[i];
	
	fod(i,1,n-1){
		d[i] = a[i+1] - a[i];
		upd(i);
	}
	
    while(q--){
        int l, r, x;
        cin >> l >> r >> x;
        // fod(i,l,r) a[i] += x;
        // cout << solve() << el;
    
    	d[r] -= x;
    	upd(r);
    	
    	if(l-1){
    		d[l-1] += x;
    		upd(l-1);
    	}
    	
    	cout << max(max(st[1][0][0], st[1][1][1]), max(st[1][0][1], st[1][1][0])) << el;
    }

    return 0;
}

Compilation message (stderr)

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

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