제출 #1289409

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1289409		youneverfindeme	Sjeckanje (COCI21_sjeckanje)	C++20	0 / 110	1 ms	332 KiB

Main

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


typedef long long ll;
typedef pair<int, int> pii;
#define F first
#define S second
#define len(x) (int)(x).size()
#define All(x) (x).begin(),(x).end()
#define pb push_back
#define int long long



const int N = 2e5 + 7, inf = 1e12;
int n, q, a[N], fen[N];

struct node {
	int l, r, dp[2][2], sz;
	int ans() {
		int res = -inf;
		for (int i = 0; i < 2; i++)
			for (int j = 0; j < 2; j++)
				res = max(res, dp[i][j]);
		return res;
	}
}seg[N << 2];

void upd_fen(int p, int x) {
	p++;
	for (p; p; p -= p & -p)
		fen[p] += x;
}

void add_fen(int l,  int r, int x) {
	upd_fen(r, x);
	upd_fen(l - 1, -x);
}

int get_val(int p) {
	int sum = 0;
	p++;
	for (p; p <= n; p += p & -p)
		sum += fen[p];
	return sum;
}

bool is_ok(int p) {
	if (p == 0 || p == n - 1)
		return false;
	int x = get_val(p - 1), y = get_val(p), z = get_val(p + 1);
	return (y > x && y > z) || (y < x && y < z);
}

int get_w(int i) {
	if (!is_ok(i) && !is_ok(i + 1))
		return -inf;
	return abs(get_val(i) - get_val(i + 1));
}

node merge(node a, node b) {
	node res;
	res.l = a.l, res.r = b.r;
	res.sz = a.sz + b.sz;
	if (a.sz >= 2 && b.sz >= 2) {
		int w = get_w(a.r);
		for (int i = 0; i < 2; i++)
			for (int j = 0; j < 2; j++) {
				res.dp[i][j] = -inf;
				res.dp[i][j] = max(res.dp[i][j], a.dp[i][0] + b.dp[0][j] + w);
				for (int k1 = 0; k1 < 2; k1++)
					for (int k2 = 0; k2 < 2; k2++)
						res.dp[i][j] = max(res.dp[i][j], a.dp[i][k1] + b.dp[k2][j]);
				if (w == -inf)
					res.dp[i][j] += abs(get_val(a.r) - get_val(b.l));
			}
		return res;
	}
	if (a.sz == 1 && b.sz == 1) {
		int w = get_w(a.r);
		int dif = (w == -inf? abs(get_val(a.r) - get_val(b.l)): 0);
	//	cout << "AAAAA" << dif << '\n';
		res.dp[0][1] = res.dp[1][0] = -inf;
		res.dp[0][0] = (w == -inf? dif: 0);
		res.dp[1][1] = (w == -inf? -inf: w);
		return res;
	}
	if (a.sz == 1) {
		int w = get_w(a.r);
		int dif = (w == -inf? abs(get_val(a.r) - get_val(b.l)): 0);
		res.dp[0][0] = b.dp[0][0] + dif;
		res.dp[1][1] = -inf;
		res.dp[0][1] = dif + b.dp[1][1];
		res.dp[1][0] = w + b.dp[0][0];
		return res;
	}
	int w = get_w(a.r);
	int dif = (w == -inf? abs(get_val(a.r) - get_val(b.l)): 0);
	res.dp[0][0] = a.dp[0][0] + b.dp[0][0] + dif;
	res.dp[1][1] = -inf;
	res.dp[1][0] = a.dp[1][0] + dif;
	res.dp[0][1] = a.dp[0][0] + w;
	return res;
}

void build(int id = 1, int st = 0, int en = n) {
	if (en - st == 1) {
		seg[id].l = seg[id].r = st;
		seg[id].sz = 1;
		seg[id].dp[0][0] = 0;
		seg[id].dp[0][1] = seg[id].dp[1][0] = seg[id].dp[1][1] = -inf;
		return;
	}
	int mid = (st + en) >> 1;
	build(id << 1, st, mid);
	build(id << 1 | 1, mid, en);
	seg[id] = merge(seg[id << 1], seg[id << 1 | 1]);
}

void rebuild(int l, int r, int id = 1, int st = 0, int en = n) {
	if (r <= st || l >= en)
		return;
	if (st >= l && en <= r)
		return;
	int mid = (st + en) >> 1;
	rebuild(l, r, id << 1, st, mid);
	rebuild(l, r, id << 1 | 1, mid, en);
	seg[id] = merge(seg[id << 1], seg[id << 1 | 1]);
}


int32_t main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin >> n >> q;
	for (int i = 0; i < n; i++) {
		cin >> a[i];
		add_fen(i, i, a[i]);
	}
/*	cout << '\n';
	for (int i = 0; i < n; i++)
		cout << get_val(i) << ' ';
	cout << '\n';
	for (int i = 0; i < n; i++)
		cout << is_ok(i) << ' ' ;
	cout << '\n';*/
	build();
/*	cout << seg[1].ans() << '\n';
	for (int i = 0; i < 2; i++)
		for (int j = 0; j < 2; j++)
			cout << "***" << i << ' ' << j << ' ' << seg[2].dp[i][j] << '\n';*/
	while (q--) {
		int l, r, x;
		cin >> l >> r >> x;
		add_fen(--l, r - 1, x);
		rebuild(l, r);
		cout << seg[1].ans() << '\n';
	}
    return 0;
}

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