Submission #470963

#	Time	Username	Problem	Language	Result	Execution time	Memory
470963		disastah	Sjeckanje (COCI21_sjeckanje)	C++17	0 / 110	1 ms	332 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 {
	struct node {
		ll sum;
		pair<int,bool> l, r;
		node() {}
	};
	vector<node> t;
	fenw fw;
	int n;
	segtr(ll *x, int n): n(n) {
		fw={n};
		for (int i=0; i<n; ++i) fw.rng_upd(i,i+1,x[i]);
		t.resize(n*4);
	}
	void calc(int v, int l, int r) {
		int m=(l+r)/2;
		t[v].sum=t[2*v+1].sum+t[2*v+2].sum;
		t[v].l=t[2*v+1].l, t[v].r=t[2*v+2].r;
		ll s_2=(t[2*v+1].r.fi<m-1?fw.sum(m-2):0), s_1=fw.sum(m-1);
		ll s=fw.sum(m), s1=fw.sum(m+1), s2=(t[2*v+2].l.fi>m?fw.sum(m+2):0);
		int am=s1-s, am_1=s-s_1, am1=(t[2*v+2].l.fi>m?s2-s1:am);
		int am_2=(t[2*v+1].r.fi<m-1?s_1-s_2:am_1);
		ll dif=0;
		if (am_1<am) {
			if (t[2*v+1].r.fi!=m-1&&!t[2*v+1].r.se) dif+=am_2-am_1;
			if (t[2*v+2].l.fi!=m&&!t[2*v+2].l.se) dif+=am-am1;
			t[v].sum+=max(0LL,am-am_1-dif);
			if ((t[2*v+1].r.fi==m-1||t[2*v+1].r.se)&&
					(t[2*v+2].l.fi==m||t[2*v+2].l.se)) {
				if (t[2*v+1].l.fi==m-1) t[v].l={t[2*v+2].l.fi,1};
				if (t[2*v+2].r.fi==m) t[v].r={t[2*v+1].r.fi,1};
			}
			else if (am-am_1-dif>=0) {
				if (t[2*v+1].l.fi==m-1&&t[2*v+1].l.se) t[v].l={m,1};
				if (t[2*v+2].r.fi==m&&t[2*v+2].r.se) t[v].r={m-1,1};
			}
		}
		else if (am_1>am) {
			if (t[2*v+1].r.fi!=m-1&&t[2*v+1].r.se) dif+=am_1-am_2;
			if (t[2*v+2].l.fi!=m&&t[2*v+2].l.se) dif+=am1-am;
			t[v].sum+=max(0LL,am_1-am-dif);
			if ((t[2*v+1].r.fi==m-1||!t[2*v+1].r.se)&&
					(t[2*v+2].l.fi==m||!t[2*v+2].l.se)) {
				if (t[2*v+1].l.fi==m-1) t[v].l={t[2*v+2].l.fi,0};
				if (t[2*v+2].r.fi==m) t[v].r={t[2*v+1].r.fi,0};
			}
			else if (am_1-am-dif>=0) {
				if (t[2*v+1].l.fi==m-1&&!t[2*v+1].l.se) t[v].l={m,0};
				if (t[2*v+2].r.fi==m&&!t[2*v+2].r.se) t[v].r={m-1,0};
			}
		}
	}
	void build(int v, int l, int r) {
		if (l+1==r) {
			t[v].sum=0;
			t[v].l=t[v].r={l,1};
		}
		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 (l>=r||(tl==l&&tr==r)) return;
		int tm=(tl+tr)/2;
		upd(2*v+1,tl,tm,l,min(r,tm));
		upd(2*v+2,tm,tr,max(l,tm),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;
ar<int,3> qs[N];
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 << tr.t[0].sum << "\n";
	}
}
vector<ll> sol() {
	segtr tr(a,n); tr.build();
	vector<ll> ans;
	for (int i=0; i<q; ++i) {
		auto [l,r,x]=qs[i]; --l;
		tr.upd(l,r,x);
		ans.push_back(tr.t[0].sum);
	}
	return ans;
}
vector<ll> sol1() {
	vector<ll> ans;
	vector<ll> b(n);
	for (int i=0; i<n; ++i) b[i]=a[i];
	for (int i=0; i<q; ++i) {
		auto [l,r,x]=qs[i]; --l;
		for (int i=l; i<r; ++i) b[i]+=x;
		ll sum=0;
		int type=-1;
		for (int i=1; i<n; ++i) {
			if (type==-1) {
				if (b[i]>b[i-1]) {
					sum+=b[i]-b[i-1];
					type=1;
				}
				else if (b[i]<b[i-1]) {
					sum+=b[i-1]-b[i];
					type=0;
				}
			}
			else if (type==1) {
				if (b[i]>b[i-1]) sum+=b[i]-b[i-1];
				else if (b[i]==b[i-1]) type=-1;
				else {
					if (b[i-1]-b[i]>b[i-1]-b[i-2]) {
						sum+=b[i-1]-b[i]-(b[i-1]-b[i-2]);
						type=0;
					}
					else type=-1;
				}
			}
			else {
				if (b[i]>b[i-1]) {
					if (b[i]-b[i-1]>b[i-2]-b[i-1]) {
						sum+=b[i]-b[i-1]-(b[i-2]-b[i-1]);
						type=1;
					}
					else type=-1;
				}
				else if (b[i]==b[i-1]) type=-1;
				else sum+=b[i-1]-b[i];
			}
		}
		ans.push_back(sum);
	}
	return ans;
}
void gen(int mxn) {
	for (int i=0; i<n; ++i) a[i]=rnd()%mxn+1;
	for (int i=0; i<q; ++i) {
		qs[i][0]=rnd()%n+1, qs[i][1]=qs[i][0]+rnd()%(n-qs[i][0]+1);
		qs[i][2]=rnd()%mxn;
	}
}
void debug() {
	n=4, q=3;
	int mxn=9, iter=0;
	while(++iter) {
		gen(mxn);
		vector<ll> ans=sol(), ans1=sol1();
		if (ans!=ans1) {
			cout << n << " " << q << "\n";
			for (int i=0; i<n; ++i) cout << a[i] << " ";
			cout << "\n";
			for (int i=0; i<q; ++i) {
				cout << qs[i][0] << " " << qs[i][1] << " " << qs[i][2] << "\n";
			}
			cout << "\n-----------\n";
			for (auto &x : ans) cout << x << "\n";
			cout << "\n---------\n";
			for (auto &x : ans1) cout << x << "\n";
			break;
		}
		cout << "ok " << iter << endl;
	}
}

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: 0 / 15
• Subtask 2: 0 / 40
• Subtask 3: 0 / 55