Submission #490875

#	Time	Username	Problem	Language	Result	Execution time	Memory
490875		inksamurai	Sjeckanje (COCI21_sjeckanje)	C++17	Compilation error	0 ms	0 KiB

Main

#include <bits/stdc++.h>
#include <atcoder/segtree>
#define fi first
#define se second
#define pb push_back
#define sz(a) (int)a.size()
#define all(a) a.begin(),a.end()
#define rep(i,n) for(int i=0;i<n;i++)
#define crep(i,x,n) for(int i=x;i<n;i++)
#define drep(i,n) for(int i=n-1;i>=0;i--)
#define vec(...) vector<__VA_ARGS__>
#define _3cSpNGp ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
typedef long long ll;
typedef long double ld;
using pii=pair<int,int>;
using vi=vector<int>;

const ll inf=1e12;

struct node{
	ll val[2][2];
	ll back;
	void init(ll _back){
		back=_back;
		val[0][0]=val[1][1]=0;
		val[0][1]=val[1][0]=-inf;
	}
};
node _e;

node op(node l,node r){
	node now;
	now.init(r.back);
	rep(tl,2)rep(tr,2){
		ll merged=0,additional=0;
		
		additional=max(0ll,l.back);
		merged=l.val[tl][0]+r.val[0][tr]+additional; // both positive
		now.val[tl][tr]=max(now.val[tl][tr],merged);
		
		if(l.back!=-inf){
			additional=max(0ll,-l.back);
		}
		merged=l.val[tl][1]+r.val[1][tr]+additional; // both negative
		now.val[tl][tr]=max(now.val[tl][tr],merged);
		
		merged=l.val[tl][0]+r.val[1][tr];
		now.val[tl][tr]=max(now.val[tl][tr],merged);
		
		merged=l.val[tl][1]+r.val[0][tr];
		now.val[tl][tr]=max(now.val[tl][tr],merged);
	}
	return now;
}

node e(){
	return _e;
}
int main(){
_3cSpNGp;
	_e.init(0);
	int n;
	cin>>n;
	int q;
	cin>>q;
	vi a(n);
	rep(i,n){
		cin>>a[i];
	}
	atcoder::segtree<node,op,e> seg(n-1);
	vec(ll) d;
	rep(i,n-1){
		node now;
		d.pb((ll)a[i+1]-a[i]);
		now.init(d.back());
		seg.set(i,now);
	}
	auto f_all=[&](int l,int r)->ll{
		node now=seg.prod(l,r);
		ll ans=-inf;
		rep(t,2)rep(t1,2){
			ans=max(ans,now.val[t][t1]);
		}
		return ans;
	};
	rep(_,q){
		int l,r;
		ll x;
		cin>>l>>r>>x;
		l--,r--;
		if(l) d[l-1]+=x;
		if(r!=n-1) d[r]-=x;
		node now;
		if(l){
			now.init(d[l-1]);
			seg.set(l-1,now);
		}
		if(r!=n-1){
			now.init(d[r]);
			seg.set(r,now);
		}
		ll ans=f_all(0,n-1);
		cout<<ans<<"\n";
	}
//	
	return 0;
}

Compilation message (stderr)

Main.cpp:2:10: fatal error: atcoder/segtree: No such file or directory
    2 | #include <atcoder/segtree>
      |          ^~~~~~~~~~~~~~~~~
compilation terminated.