Submission #1182420

#	Time	Username	Problem	Language	Result	Execution time	Memory
1182420		trvhung	Foehn Phenomena (JOI17_foehn_phenomena)	C++20	100 / 100	187 ms	30024 KiB

foehn_phenomena

#include <bits/stdc++.h>
// #include <ext/rope>
// #include <ext/pb_ds/assoc_container.hpp>

// using namespace __gnu_pbds;
// using namespace __gnu_cxx;
using namespace std;

// #define   ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
#define            ll long long
#define           ull unsigned long long
#define            ld long double
#define            pb push_back
#define  bit(mask, i) ((mask >> i) & 1)
#define            el '\n'
#define             F first
#define             S second

template <class X, class Y> bool maximize(X &x, const Y &y) { return (x < y ? x = y, 1 : 0); }
template <class X, class Y> bool minimize(X &x, const Y &y) { return (x > y ? x = y, 1 : 0); }

const int INF = 1e9;
const ll LINF = 1e18;
const int MOD = 1e9 + 7;
const int MULTI = 0;
const ld eps = 1e-9;
const int dx[4] = {0, 1, 0, -1}, dy[4] = {1, 0, -1, 0}; // R D L U
const int ddx[4] = {-1, 1, 1, -1}, ddy[4] = {1, 1, -1, -1}; // UR DR DL UL
const char cx[4] = {'R', 'D', 'L', 'U'};
const ll base = 31;
const int nMOD = 2;
const ll mods[] = {(ll)1e9 + 10777, (ll)1e9 + 19777, (ll)1e9 + 3, (ll)1e9 + 3777};

const int maxn = 2e5 + 5;
int n, q, s, t, a[maxn];

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

struct node {
	ll diff, fir, lst, lz;
	node() : diff(0), fir(0), lst(0), lz(0) {}
} st[4 * maxn];

node merge(node L, node R) {
	node res;
	res.fir = L.fir; res.lst = R.lst;
	res.diff = L.diff + calc(L.lst, R.fir) + R.diff;
	return res;
}

struct IT {
	void build(int id, int l, int r) {
		if (l == r) {
			st[id].fir = st[id].lst = a[l];
			return;
		}

		int mid = (l + r) >> 1;
		build(id << 1, l, mid);
		build(id << 1 | 1, mid + 1, r);

		st[id] = merge(st[id << 1], st[id << 1 | 1]);
	}

	void push(int id) {
		ll &t = st[id].lz;
		if (t == 0) return;

		st[id << 1].fir += t;
		st[id << 1].lst += t;
		st[id << 1].lz += t;

		st[id << 1 | 1].fir += t;
		st[id << 1 | 1].lst += t;
		st[id << 1 | 1].lz += t;

		t = 0;
	}

	void update(int id, int l, int r, int u, int v, int x) {
		if (l == u && r == v) {
			st[id].fir += x;
			st[id].lst += x;
			st[id].lz += x;
			return;
		}

		int mid = (l + r) >> 1; push(id);
		if (v <= mid) update(id << 1, l, mid, u, v, x);
		else if (u > mid) update(id << 1 | 1, mid + 1, r, u, v, x);
		else {
			update(id << 1, l, mid, u, mid, x);
			update(id << 1 | 1, mid + 1, r, mid + 1, v, x);
		}

		st[id] = merge(st[id << 1], st[id << 1 | 1]);
	}

	node get(int id, int l, int r, int u, int v) {
		if (l == u && r == v) return st[id];

		int mid = (l + r) >> 1; push(id);
		if (v <= mid) return get(id << 1, l, mid, u, v);
		else if (u > mid) return get(id << 1 | 1, mid + 1, r, u, v);
		else return merge(get(id << 1, l, mid, u, mid), get(id << 1 | 1, mid + 1, r, mid + 1, v));
	}
} IT;

void solve() {
	cin >> n >> q >> s >> t;
	for (int i = 0; i <= n; ++i)
		cin >> a[i];

	IT.build(1, 0, n);

	while (q--) {
		int l, r, x;
		cin >> l >> r >> x;
		IT.update(1, 0, n, l, r, x);
		cout << st[1].diff << el;
	}
}

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    if (!MULTI) solve();
    else {
        int test; cin >> test;
        while (test--) solve();
    }
    
    return 0;
}

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