Submission #699164

#	Time	Username	Problem	Language	Result	Execution time	Memory
699164		bane	Sjeckanje (COCI21_sjeckanje)	C++17	110 / 110	897 ms	38532 KiB

Main

#include<bits/stdc++.h>
using namespace std;
 
#ifdef LOCAL
    #define eprintf(...) {fprintf(stderr, __VA_ARGS__);fflush(stderr);}
#else
    #define eprintf(...) 42
#endif
 
//order statistic tree
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template <class T> using Tree = tree<
    T, null_type, less<T>,
    rb_tree_tag, tree_order_statistics_node_update
>;
#define pb push_back
#define mp make_pair
#define ins insert
#define popb pop_back
#define popf pop_front
#define ft front
#define bk back
#define fr first
#define sc second
using ll = long long;
using ld = long double;
using db = double;
using ull = unsigned long long;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
using pdd = pair<ld,ld>;
using str = string;
const int NAX = (int)1000000;
const int MOD = (int)998244353;
template<int MOD, int RT> struct mint {
	static const int mod = MOD;
	static constexpr mint rt() { return RT; } // primitive root for FFT
	int v; explicit operator int() const { return v; } // explicit -> don't silently convert to int
	mint():v(0) {}
	mint(ll _v) { v = int((-MOD < _v && _v < MOD) ? _v : _v % MOD);
		if (v < 0) v += MOD; }
	bool operator==(const mint& o) const {
		return v == o.v; }
	friend bool operator!=(const mint& a, const mint& b) { 
		return !(a == b); }
	friend bool operator<(const mint& a, const mint& b) { 
		return a.v < b.v; }
   
	mint& operator+=(const mint& o) { 
		if ((v += o.v) >= MOD) v -= MOD; 
		return *this; }
	mint& operator-=(const mint& o) { 
		if ((v -= o.v) < 0) v += MOD; 
		return *this; }
	mint& operator*=(const mint& o) { 
		v = int((ll)v*o.v%MOD); return *this; }
	mint& operator/=(const mint& o) { return (*this) *= inv(o); }
	friend mint pow(mint a, ll p) {
		mint ans = 1; assert(p >= 0);
		for (; p; p /= 2, a *= a) if (p&1) ans *= a;
		return ans; }
	friend mint inv(const mint& a) { assert(a.v != 0); 
		return pow(a,MOD-2); }
		
	mint operator-() const { return mint(-v); }
	mint& operator++() { return *this += 1; }
	mint& operator--() { return *this -= 1; }
	friend mint operator+(mint a, const mint& b) { return a += b; }
	friend mint operator-(mint a, const mint& b) { return a -= b; }
	friend mint operator*(mint a, const mint& b) { return a *= b; }
	friend mint operator/(mint a, const mint& b) { return a /= b; }
};

using mi = mint<MOD,5>;
using vmi = vector<mi>;
using pmi = pair<mi,mi>;
using vpmi = vector<pmi>;
ll n, q;
ll D[300000];
struct Node{
	ll borders[2];
	ll dp[2][2];
	Node(){}
	Node(ll v){
		borders[1] = borders[0] = v;
		memset(dp, 0, sizeof(dp));
		dp[1][1] = abs(v);
	}
	Node Merge(Node right){
		Node res;
		res.borders[0] = borders[0], res.borders[1] = right.borders[1];
		memset(res.dp, 0, sizeof(res.dp));
		for (int a = 0; a < 2; a++){
			for (int b = 0; b < 2; b++){
				for (int c = 0; c < 2; c++){
					for (int d = 0; d < 2; d++){
						if (c && b){
							//this implies that we merge the two segments because we include [l..r] ->[l...r2]
							if ((borders[1] < 0) == (right.borders[0] < 0)){
								//check signs, dumb to use two same signed borders because we have more optimal arrangement
								res.dp[a][d] = max(res.dp[a][d], dp[a][b] + right.dp[c][d]);
							}
						}else{
							//we do not merge them => they are seperate segments
							res.dp[a][d] = max(res.dp[a][d], dp[a][b] + right.dp[c][d]);
						}
					}
				}
			}
		}
		return res;
	}
	void upd(ll u){
		borders[1]+=u;
		borders[0]+=u;
		dp[1][1]=abs(u);
	}
};
template<class V, int NV> class SegmentTree{
	public:
			Node t[NV * 3];
			
			void build(int l = 0, int r = n - 2, int node = 1){
				if (l ==r){
					t[node] = Node(D[l]);
					return;
				}
				int mid = (l + r)/2;
				build(l, mid, node * 2);
				build(mid + 1, r, node * 2 + 1);
				t[node] = t[node * 2].Merge(t[node * 2 + 1]);
			}
			void update(int l = 0, int r = n - 2, int node = 1, int pos = 1, ll updval = 0){
				if (l == r){
					t[node] = Node(D[l]);
					return;
				}
				int mid = (l + r)/2;
				if (pos <= mid)update(l,mid,node*2,pos, updval);
				else update(mid+1,r,node*2+1,pos, updval);
				t[node] = t[node * 2].Merge(t[node * 2 + 1]);
			}
};
SegmentTree<int,1<<20>st;

void Task_Sjeckanje(){
	cin >> n >> q;
	vector<ll>a(n);
	memset(D, 0, sizeof(D));
	for (int i = 0; i<n; i++){
		cin >> a[i];
		if (i)D[i - 1] = a[i] - a[i - 1];
	}
	st.build(0,n-2,1);
	while(q--){
		ll b,c, d;
		cin >>  b >> c >> d;
		--b;
		--c;
		if (b){
			D[b-1]+=d;
			st.update(0,n-2,1,b-1, d);
		}
		if(c < n - 1){
			D[c]-=d;
			st.update(0,n-2,1,c, -d);
		}
		//st.build();
		ll ans = 0;
		for(int i = 0; i < 2; i++){
			for (int j =0 ; j < 2; j++){
				ans = max(ans, st.t[1].dp[i][j]);
			}
		}
		cout<<ans<<endl;
	}
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	//freopen("optmilk.in", "r", stdin);
	//freopen("optmilk.out", "w", stdout);
	Task_Sjeckanje();
	return 0;
}

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