제출 #1280791

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1280791		third	Foehn Phenomena (JOI17_foehn_phenomena)	C++20	100 / 100	463 ms	18156 KiB

foehn_phenomena

//Huyduocdithitp
#include<bits/stdc++.h>
typedef long long ll;
#define endl '\n'
#define fi first
#define se second
#define pii pair<ll,ll>
#define N 400005
#define LOG 18
using namespace std;

const ll inf = 1e8, base = 311, mod = 1e9 + 7;

bool ghuy4g;

ll n, q, S, T, sum = 0, a[N], st[4 * N], f[4 * N];

void build(ll id, ll l, ll r) {
	if (l == r) {
		st[id] = a[l];
		return;
	}
	ll mid = (l + r) / 2;
	build(id * 2, l, mid);
	build(id * 2 + 1, mid + 1, r);
}

void lazy(ll id) {
	if (f[id] == 0) return;
	st[id] += f[id];
	f[id * 2] += f[id];
	f[id * 2 + 1] += f[id];
	f[id] = 0;
}

void update(ll id, ll l, ll r, ll L, ll R, ll v) {
	lazy(id);
	if (l > R || r < L) {
		return;
	}
	if (L <= l && r <= R) {
		f[id] += v;
		lazy(id);
		return;
	}
	ll mid = (l + r) / 2;
	update(id * 2, l, mid, L, R, v);
	update(id * 2 + 1, mid + 1, r, L, R, v);
}

ll get(ll id, ll l, ll r, ll i) {
	if (i < 0 || i > n) return 0;
	lazy(id);
	if (i > r || i < l) return 0;
	if (l == r) {
		return st[id];
	}
	ll mid = (l + r) / 2;
	return get(id * 2, l, mid, i) + get(id * 2 + 1, mid + 1, r, i);
}


bool klinh;

signed main() {
	//freopen("boardgame.inp", "r", stdin);
	//freopen("boardgame.out", "w", stdout);
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> n >> q >> S >> T;
	for (int i = 0; i <= n; i ++) {
		cin >> a[i];
		if (a[i - 1] < a[i]) {
			sum += S * (a[i] - a[i - 1]);
		}
		else if (a[i - 1] >= a[i]){
			sum += T * (a[i] - a[i - 1]); // tang 
		}
	}
	
	build(1, 1, n);
	
	for (int i = 1; i <= q; i ++) {
		ll l, r, x;
		cin >> l >> r >> x;
		if (1) {
			ll old_l = get(1, 1, n, l);
			ll prev = get(1, 1, n, l - 1);
			if (prev < old_l) {
				sum -= S * (old_l - prev);
			}
			else {
				sum -= T * (old_l - prev);
			}
		}
		if (r < n) {
			ll old_r = get(1, 1, n, r);
			ll sau = get(1, 1, n, r + 1);
			if (old_r < sau) {
				sum -= S * (sau - old_r);
			}
			else {
				sum -= T * (sau - old_r);
			}
		}
		update(1, 1, n, l, r, x);
		if (1) {
			ll old_l = get(1, 1, n, l);
			ll prev = get(1, 1, n, l - 1);
			if (prev < old_l) {
				sum += S * (old_l - prev);
			}
			else {
				sum += T * (old_l - prev);
			}
		}
		if (r < n) {
			ll old_r = get(1, 1, n, r);
			ll sau = get(1, 1, n, r + 1);
			if (old_r < sau) {
				sum += S * (sau - old_r);
			}
			else {
				sum += T * (sau - old_r);
			}
		}
		cout << -sum << endl;
	}
			
	cerr << fabs(&klinh - &ghuy4g) / double(1024 * 1024);
	
	return 0;
}

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