Submission #674389

#	Time	Username	Problem	Language	Result	Execution time	Memory
674389		badont	Sjeckanje (COCI21_sjeckanje)	C++17	110 / 110	666 ms	50728 KiB

Main

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

void dbg_out() { cout << endl; }
template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cout << ' ' << H; dbg_out(T...); }

#ifdef LOCAL
#define debug(...) cout << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
#else
#define debug(...) "zzz"
#endif

using LL = long long;
using LD = long double;
using pii = pair<LL,LL>;

#define FOR(i, n) for(int i = 1; i<=n; i++)
#define F0R(i, n) for(int i = 0; i<n; i++)
#define all(x) x.begin(), x.end()
#define mp make_pair
#define pb push_back
#define f first
#define s second

template<typename T, typename = void> struct is_iterable : false_type {};
template<typename T> struct is_iterable<T, void_t<decltype(begin(declval<T>())),decltype(end(declval<T>()))>> : true_type {};
template<typename T> typename enable_if<is_iterable<T>::value&&!is_same<T, string>::value,ostream&>::type operator<<(ostream &cout, T const &v);
template<typename A, typename B> ostream& operator<<(ostream &cout, pair<A, B> const &p) { return cout << "(" << p.f << ", " << p.s << ")"; }
template<typename T> typename enable_if<is_iterable<T>::value&&!is_same<T, string>::value,ostream&>::type operator<<(ostream &cout, T const &v) {
	cout << "["; 
	for (auto it = v.begin(); it != v.end();) {
		cout << *it;
		if (++it != v.end()) cout << ", ";
	}
	return cout << "]";
}

const LL INF = 1e16;

struct Info {
	array<array<LL, 2>, 2> take;
	LL left, right;

	Info(LL g) : left((g == 0 ? 0LL : g / abs(g))), right(left) {
		this->take[0][0] = 0;
		this->take[1][1] = abs(g);
		this->take[0][1] = this->take[1][0] = -INF;
	}
	Info() : Info(0) {
		this->take[0][0] = this->take[1][1] = -INF;
	}
};

struct Merge {
	Info operator()(const Info& a, const Info& b) {
		Info res;
		F0R (i, 2) F0R(j, 2) {
			F0R (k, 2) F0R (z, 2) if (a.take[i][k] < INF && b.take[z][j] < INF) {
				if (k && z) if (a.right * b.left < 0)
					continue;

				res.take[i][j] = max(res.take[i][j],
					a.take[i][k] + b.take[z][j]
				);
			} 
		}
		res.left = a.left;
		res.right = b.right;
		return res;
	}
};

template<typename T, typename Merge = plus<T>>
struct seg {
	int n;
	vector<T> tr;
	Merge merge;
	seg(int n) : n(n), merge(Merge()), tr((n << 2) + 5, T(0)) {};
	
	seg(vector<LL> a) : seg((int)a.size()) {
		function<void (int, int, int)> build = [&](int z, int l, int r) {
			if (l == r) {
				tr[z] = T(a[l]);
				return;
			}
			
			int mid = (l + r) >> 1;
			build(2 * z, l, mid);
			build(2 * z + 1, mid + 1, r);
			tr[z] = merge(tr[2 * z], tr[2 * z + 1]);
		};
		build(1, 0, n - 1);
	}
	
	void upd(int z, int l, int r, int qg, LL val) {
		if (qg == l && qg == r) {
			tr[z] = T(val);
			return;
		}
		
		int mid = (l + r) >> 1;
		if (qg <= mid) {
			upd(2 * z, l, mid, qg, val);
		} else {
			upd(2 * z + 1, mid + 1, r, qg, val);
		}
		
		tr[z] = merge(tr[2 * z], tr[2 * z + 1]);
	};
	
	T query(int z, int l, int r, int ql, int qr) {
		if (ql > qr) return T(0);
		if (ql == l && qr == r) {
			return tr[z];
		}
		
		int mid = (l + r) >> 1;
		return merge(query(2 * z, l, mid, ql, min(qr, mid)),
					 query(2 * z + 1, mid + 1, r, max(ql, mid + 1), qr));
	};
	
	void upd(int g, LL val) { upd(1, 0, n - 1, g, val); }
	T query(int l, int r) { return query(1, 0, n - 1, l, r); }
};


//var 
LL T;

void solve() {
	LL n, q;
	cin >> n >> q;

	vector<LL> a(n);
	for (auto& u : a)
		cin >> u;

	vector<LL> d(n - 1);
	F0R (i, n - 1) {
		d[i] = a[i] - a[i + 1];
	}

	seg<Info, Merge> tree(d);
	while (q--) {
		LL l, r, x;
		cin >> l >> r >> x;
		l--; r--;

		if (l) {
			d[l - 1] -= x;
			tree.upd(l - 1, d[l - 1]);
		}
		if (r != n - 1) {
			d[r] += x;
			tree.upd(r, d[r]);
		}

		debug(d);

		LL ans = 0;
		F0R (i, 2) F0R(j, 2) ans = max(ans, tree.tr[1].take[i][j]);
		cout << ans << "\n";
	}

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


	T = 1;
	//cin >> T;
	FOR(t, T)
		solve();

	cout.flush();
	return 0;
}

Compilation message (stderr)

Main.cpp: In function 'void solve()':
Main.cpp:10:20: warning: statement has no effect [-Wunused-value]
   10 | #define debug(...) "zzz"
      |                    ^~~~~
Main.cpp:158:3: note: in expansion of macro 'debug'
  158 |   debug(d);
      |   ^~~~~
Main.cpp: In instantiation of 'seg<T, Merge>::seg(int) [with T = Info; Merge = Merge]':
Main.cpp:80:39:   required from 'seg<T, Merge>::seg(std::vector<long long int>) [with T = Info; Merge = Merge]'
Main.cpp:143:25:   required from here
Main.cpp:77:8: warning: 'seg<Info, Merge>::merge' will be initialized after [-Wreorder]
   77 |  Merge merge;
      |        ^~~~~
Main.cpp:76:12: warning:   'std::vector<Info, std::allocator<Info> > seg<Info, Merge>::tr' [-Wreorder]
   76 |  vector<T> tr;
      |            ^~
Main.cpp:78:2: warning:   when initialized here [-Wreorder]
   78 |  seg(int n) : n(n), merge(Merge()), tr((n << 2) + 5, T(0)) {};
      |  ^~~

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