Submission #1069931

#	Time	Username	Problem	Language	Result	Execution time	Memory
1069931		n1k	Sjeckanje (COCI21_sjeckanje)	C++17	110 / 110	691 ms	44540 KiB

Main

#include <bits/stdc++.h>

#if defined(LOCAL)
#include "debug.cpp"
#else
#define debug(x...) 0
#endif // LOCAL

using namespace std;

using ll = long long;

#define all(a) (a).begin(), (a).end()

vector<ll> a;

struct Data{
	array<array<ll, 2>, 2> mat={};
	ll lo=0, hi=0;
	Data operator+(Data o){
		array<array<ll, 2>, 2> ret={};
		for(int i=0; i<2; i++){
			for(int j=0; j<2; j++){
				for(int x=0; x<2; x++){
					for(int y=0; y<2; y++){
						// ret[i][j], mat[i][x], o.mat[y][j]
						if(x!=1 or y!=1 or signbit(hi) == signbit(o.lo)){
							ret[i][j] = max(ret[i][j], mat[i][x] + o.mat[y][j]);
						}
					}
				}
			}
		}
		return Data{ret, lo, o.hi};
	}
};

struct V{
    int lb=0, rb=0;
	Data val{};
    V *l=nullptr, *r=nullptr;
    V(){};
    V(int lb_, int rb_){lb=lb_, rb=rb_;};
    void ext(){
        if(lb!=rb and not l){
            int mb=(lb+rb)/2;
            l=new V(lb, mb);
            r=new V(mb+1, rb);
        }
    }
    void upd(int id, ll x){
        if(lb==rb and lb==id){
			val = Data{array{array<ll, 2>{0, 0}, array<ll, 2>{0, abs(x)}}, x, x};
        }
        ext();
        if(l){
            if(id<=l->rb){
                l->upd(id, x);
            }else{
                r->upd(id, x);
            }
            val = l->val+ r->val;
        }
    }
    Data qry(int lo, int hi){
        if(lo<=lb and rb<=hi){
            return val;
        }
        if(hi<lb or rb<lo) return Data{};
        ext();
        return l->qry(lo, hi) + r->qry(lo, hi);
    }
};

void solve(){
	int n, q; cin >> n >> q;
	a.assign(n, 0);
	V seg(0, n-2);
	for(int i=0; i<n; i++) cin >> a[i];
	vector<ll> d;
	for(int i=0; i+1<n; i++){
		d.push_back(a[i+1] - a[i]);
		seg.upd(i, d.back());
	}
	a = d;
	while(q--){
		ll l, r, add;
		cin>>l>>r>>add;
		l--, r--;
		if(l){
			d[l-1] += add;
			seg.upd(l-1, d[l-1]);
		}
		if(r<d.size()){
			d[r]-=add;
			seg.upd(r, d[r]);
		}
		auto mat = seg.qry(0, n-1).mat;
		ll ans = 0;
		for(int i=0; i<2; i++){
			for(int j=0; j<2; j++){
				ans = max(ans, mat[i][j]);
			}
		}
		cout<<ans<<endl;
	}
}

int main() {
	cin.tie(0)->sync_with_stdio(0);
	int t=1; //cin >> t;
	while(t--) solve();
}

Compilation message (stderr)

Main.cpp: In function 'void solve()':
Main.cpp:94:7: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   94 |   if(r<d.size()){
      |      ~^~~~~~~~~

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