Submission #471029

#	Time	Username	Problem	Language	Result	Execution time	Memory
471029		disastah	Sjeckanje (COCI21_sjeckanje)	C++17	110 / 110	1491 ms	41276 KiB

Main

#include <bits/stdc++.h>
#define ar array
#define fi first
#define se second
std::mt19937 rnd(237);
using namespace std;
typedef long double ld;
typedef long long ll;
const int inf=2e9+9;
const ll linf=4e18+18;
const int N=2e5;

struct fenw {
	vector<ll> f1, f2;
	int n;
	fenw(int n=0): n(n) {
		f1.assign(n+1,0LL), f2=f1;
	}
	void upd(vector<ll>&f, int p, ll x) { ++p;
		for (; p<=n; p+=(p&-p)) f[p]+=x;
	}
	void rng_upd(int l, int r, ll x) {
		upd(f1,l,x), upd(f1,r,-x);
		upd(f2,l,x*l), upd(f2,r,-x*r);
	}
	ll sum(int p, ll ans=0) {
		int p1=p;
		for (; p; p-=(p&-p)) ans+=f1[p]*p1-f2[p];
		return ans;
	}
	ll get(int p) {return sum(p+1)-sum(p);}
};
struct segtr {
	vector<ll> a;
	vector<ar<ar<ll,2>,2>> t;
	fenw fw;
	int n;
	segtr(ll *x, int n): n(n) {
		fw={n};
		a.resize(n);
		for (int i=0; i<n; ++i) {
			a[i]=x[i];
			fw.rng_upd(i,i+1,a[i]);
		}
		t.resize(n*4);
	}
	void calc(int v, int l, int r) {
		int m=(l+r)/2;
		ll am=fw.get(m), am_1=fw.get(m-1), am1=(m+1==n?0:fw.get(m+1));
		for (auto x : {0,1}) {
			for (auto y : {0,1}) {
				t[v][x][y]=max(max(t[2*v+1][x][0]+t[2*v+2][0][y],
								t[2*v+1][x][1]+t[2*v+2][0][y]),
								t[2*v+1][x][0]+t[2*v+2][1][y]);
				if (m+1==n||(am_1<am&&am<am1)||(am_1>am&&am>am1)) {
					t[v][x][y]=max(t[v][x][y],t[2*v+1][x][1]+t[2*v+2][1][y]);
				}
			}
		}
	}
	void build(int v, int l, int r) {
		if (l+1==r) {
			t[v][0][0]=0;
			t[v][0][1]=-4e13;
			t[v][1][0]=-4e13;
			t[v][1][1]=(r==n?0:abs(a[l]-a[r]));
		}
		else {
			int m=(l+r)/2;
			build(2*v+1,l,m);
			build(2*v+2,m,r);
			calc(v,l,r);
		}
	} void build() {build(0,0,n);}
	void upd(int v, int tl, int tr, int l, int r) {
		if (r<=tl||tr<l) return;
		if (l<=tl&&tr<r) return;
		if (tl+1==tr) t[v][1][1]=(tr==n?0:abs(fw.get(tl)-fw.get(tr)));
		else {
			int tm=(tl+tr)/2;
			upd(2*v+1,tl,tm,l,r);
			upd(2*v+2,tm,tr,l,r);
			calc(v,tl,tr);
		}
	} void upd(int l, int r, ll x) {
		fw.rng_upd(l,r,x);
		upd(0,0,n,l,r);
	}
};

int n, q;
ll a[N];

void solve() {
	cin >> n >> q;
	for (int i=0; i<n; ++i) cin >> a[i];
	segtr tr(a,n); tr.build();
	while(q--){
		int l, r, x; cin >> l >> r >> x; --l;
		tr.upd(l,r,x);
		cout << max(max(tr.t[0][0][0],tr.t[0][0][1]),max(tr.t[0][1][0],tr.t[0][1][1])) << "\n";
	}
}

signed main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
#ifdef disastah
	cout << "Output\n\n";
#endif
/*#ifndef disastah
	freopen("marathon.in","r",stdin);
	freopen("marathon.out","w",stdout);
#endif*/
	int tt=1;
//	cin >> tt;
	while (tt--) {
		solve();
		cout << "\n";
	}
}

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