Submission #991139

#	Time	Username	Problem	Language	Result	Execution time	Memory
991139		horezushol	Foehn Phenomena (JOI17_foehn_phenomena)	C++14	100 / 100	369 ms	19764 KiB

foehn_phenomena

#include<bits/stdc++.h>

const char nl = '\n';

using namespace std;
using ll = long long;


ll s, t;
struct Segtree {
	struct node {
		ll le, ri, wd; // leftest element, rightest element, power of wind
	};
	vector<ll> tree;
	vector<ll> sh;
	vector<ll> a;

	ll sz = 1;
	ll nope = 0;
	void init(ll n) {
		while (sz < n) {
			sz *= 2;
		}
		tree.assign(2*sz+1, 0);
		sh.assign(2*sz+1, 0);
		a.assign(n+10, 0);
	}

	void create(ll n) {
		for (ll i = 0, lf = sz-1; i <= n; i ++, lf ++) {
			tree[lf] = a[i];
		}
	}

	void build(ll x, ll lx, ll rx) {
		if (rx - lx == 1) {
			return ;
		}
		ll mid = (lx + rx) / 2;
		build(2*x+1, lx, mid);
		build(2*x+2, mid, rx);
		tree[x] = tree[2*x+1] + tree[2*x+2];
	}


	void build() {
		build(0, 0, sz);
	}

	void push(ll x, ll lx, ll rx) {
		if (sh[x] == nope) return ;
		if (rx - lx == 1) return ;
		sh[2*x+1] += sh[x];
		tree[2*x+1] += sh[x];
		sh[2*x+2] += sh[x];
		tree[2*x+2] += sh[x];
		sh[x] = nope;
	}

	void update(ll l, ll r, ll v, ll x, ll lx, ll rx) {
		push(x, lx, rx);
		if (lx >= r || rx <= l) {
			return ;
		}
		if (l <= lx && rx <= r) {
			sh[x] += v;
			push(x, lx, rx);
			tree[x] += v;
			return ;
		}
		ll mid = (lx + rx) / 2;
		update(l, r, v, 2*x+1, lx, mid);
		update(l, r, v, 2*x+2, mid, rx);
		tree[x] = tree[2*x+1] + tree[2*x+2];
	}

	void update(ll l, ll r, ll v) {
		update(l, r, v, 0, 0, sz);
	}

	ll get(ll i, ll x, ll lx, ll rx) {
		push(x, lx, rx);
		if (rx - lx == 1) {
			return tree[x];
		}
		ll mid = (lx + rx) / 2;
		if (i < mid) {
			return get(i, 2*x+1, lx, mid);
		} else {
			return get(i, 2*x+2, mid, rx);
		}
	}

	ll get(ll i) {
		return get(i, 0, 0, sz);
	}

	void debug() {
		for (ll i = 0; i < 2*sz-1; i ++) {
			cout << i << ": " << tree[i] << nl;
		}
	}
};

ll wind(ll x, ll y) {
    return (x < y ? s * (x - y) : t * (x - y));
}

void solve() {
	ll n, q;
	cin >> n >> q >> s >> t;
	Segtree sg;
	n ++;
	sg.init(n);
	for (ll i = 0; i < n; i ++) {
		cin >> sg.a[i];
	}
	sg.create(n);
	sg.build();
	ll res = 0;
	for (ll i = 0; i < n-1; i ++) {
		res += wind(sg.a[i], sg.a[i+1]);
	}
	for (ll i = 0; i < q; i ++) {
		ll l, r, v;
		cin >> l >> r >> v;
		r ++;
		res -= wind(sg.get(l-1), sg.get(l));
		if (r != n) {
			res -= wind(sg.get(r-1), sg.get(r));
		}
		sg.update(l, r, v);
		res += wind(sg.get(l-1), sg.get(l));
		if (r != n) {
			res += wind(sg.get(r-1), sg.get(r));
		}	
		cout << res << nl;	
	}
}

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	ll tst = 1;
	// cin >> tst;
	while (tst --) {
		solve();
		cout << nl;
	}
}

• Subtask 1: 30 / 30
• Subtask 2: 10 / 10
• Subtask 3: 60 / 60