Submission #883088

#	Time	Username	Problem	Language	Result	Execution time	Memory
883088		phoenix0423	Sjeckanje (COCI21_sjeckanje)	C++17	110 / 110	660 ms	30356 KiB

Main

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pll;
#define fastio ios::sync_with_stdio(false), cin.tie(0)
// #pragma GCC optimize("Ofast")
#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define REP(i, n) FOR(i, 0, n)
#define REP1(i, n) FOR(i, 0, n + 1)
#define SZ(x) (int)(x).size()
#define pb push_back
#define pf push_front
#define eb emplace_back
#define f first
#define s second
#define lowbit(x) x&-x
#define ckmin(a, b) a = min(a, b)
#define ckmax(a, b) a = max(a, b)
#define int long long
const int INF = 1e18;
const int maxn = 3e5 + 5;
int n, q;
int a[maxn], dif[maxn];
int dp[maxn * 4][2][2];

void pull(int v, int md){
	for(int l = 0; l < 2; l++){
		for(int r = 0; r < 2; r++){
			dp[v][l][r] = -INF;
			for(int j = 0; j < 2; j++){
				for(int k = 0; k < 2; k++){
					if(j == 1 && k == 1 && ((dif[md] > 0 && dif[md + 1] < 0) || (dif[md] < 0 && dif[md + 1] > 0))) continue;
					dp[v][l][r] = max(dp[v][l][r], dp[v * 2][l][j] + dp[v * 2 + 1][k][r]);
				}
			}
		}
	}
}

void upd(int pos, int v = 1, int l = 0, int r = n - 1){
	if(l == r){
		dp[v][1][1] = abs(dif[l]);
		return;
	}
	int m = (l + r) / 2;
	if(pos <= m) upd(pos, v * 2, l, m);
	else upd(pos, v * 2 + 1, m + 1, r);
	pull(v, m);
}

int qry(){
	return max({dp[1][0][0], dp[1][0][1], dp[1][1][0], dp[1][1][1]});
}
signed main(void){
	fastio;
	cin>>n>>q;
	vector<int> a(n);
	for(int i = 0; i < n; i++) cin>>a[i];
	for(int i = 1; i < n; i++) dif[i] = a[i] - a[i - 1], upd(i);
	for(int i = 0; i < q; i++){
		int l, r, x;
		cin>>l>>r>>x;
		l--;
		dif[l] += x, dif[r] -= x;
		if(l > 0){
			upd(l);
		}
		if(r < n){
			upd(r);
		}
		cout<<qry()<<"\n";
	}

}

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