Submission #923026

#	Time	Username	Problem	Language	Result	Execution time	Memory
923026		Gromp15	Foehn Phenomena (JOI17_foehn_phenomena)	C++17	100 / 100	733 ms	25164 KiB

foehn_phenomena

#include <bits/stdc++.h>
#define ll long long
#define ar array
#define db double
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define rint(l, r) uniform_int_distribution<int>(l, r)(rng)
template<typename T> bool ckmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; }
template<typename T> bool ckmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }
struct seg {
	int n, N, S, T;
	vector<int> size;
	vector<ll> tree, lazy, tree2;
	ll cost(ll x, ll y) {
		return (ll)(x-y) * (x < y ? S : T);
	}
	seg(int s, int t, vector<int> &a) : n(sz(a)-1), N(1<<(__lg(n+1)+1)), S(s), T(t), size(2*N), tree(2*N), lazy(2*N), tree2(2*N) {
		for (int i = 0; i <= n; i++) {
			tree[i+N] = a[i], size[i+N] = 1;
			if (i) tree2[i+N] = cost(a[i-1], a[i]);
		}
		for (int i = N-1; i >= 1; i--) {
			tree[i] = tree[i*2] + tree[i*2+1];
			tree2[i] = tree2[i*2] + tree2[i*2+1];
			size[i] = size[i*2] + size[i*2+1];
		}
	}
	void push(int node) {
		if (lazy[node]) {
			tree[node] += lazy[node] * size[node];
			if (node < N) {
				lazy[node*2] += lazy[node];
				lazy[node*2+1] += lazy[node];
			}
			lazy[node] = 0;
		}
	}
	void update(int node, int nl, int nr, int ql, int qr, int v) {
		push(node);
		if (ql > nr || qr < nl) return;
		if (ql <= nl && nr <= qr) {
			lazy[node] += v;
			push(node);
			return;
		}
		int mid = (nl+nr)/2;
		update(node*2, nl, mid, ql, qr, v);
		update(node*2+1, mid+1, nr, ql, qr, v);
		tree[node] = tree[node*2] + tree[node*2+1];
	}
	void update2(int pos) {
		auto upd = [&](int i) {
			vector<int> ok;
			for (int j = i+N; j; j >>= 1) {
				ok.emplace_back(j);
			}
			for (int k = sz(ok)-1; k >= 0; k--) {
				int j = ok[k];
				push(j);
			}
		};
		for (int i = pos; i <= pos+1; i++) {
			if (i-1 >= 0 && i <= n) {
				upd(i-1), upd(i);
				tree2[i+N] = cost(tree[i-1+N], tree[i+N]);
				for (int j = (i+N) >> 1; j; j >>= 1) {
					tree2[j] = tree2[j*2] + tree2[j*2+1];
				}
			}
		}

	}
};
void test_case() {
	int n, q, S, T;
	cin >> n >> q >> S >> T;
	vector<int> a(n+1);
	for (int &x : a) cin >> x;
	seg st(S, T, a);
	while (q--) {
		int l, r, x;
		cin >> l >> r >> x;
		st.update(1, 0, st.N-1, l, r, x);
		st.update2(l);
		st.update2(r);
		cout << st.tree2[1] << '\n';
	}



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

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