Submission #1128471

#	Time	Username	Problem	Language	Result	Execution time	Memory
1128471		nuutsnoynton	Foehn Phenomena (JOI17_foehn_phenomena)	C++20	100 / 100	633 ms	9748 KiB

foehn_phenomena

#include<bits/stdc++.h>

using namespace std;
using ll = long long;
const ll N = 2e5 + 2;
ll T[16 * N], S[16 * N], a[N];
void Update(ll p, ll lo, ll hi, ll l, ll r, ll val) {
	if (l > r) return ;
	if ( lo > r || l > hi) return;
	if ( l <= lo && hi <= r) {
		S[p] += val;
		return ;
	}
	ll mid = (lo + hi)/2;
	Update(2 * p, lo, mid, l, r, val);
	Update(2 * p + 1, mid + 1, hi, l, r, val);
}
ll val =0;
ll Find(ll p, ll lo, ll hi, ll x) {
	val += S[p];
	if ( lo == hi) {
		val += a[lo];
		return val;
	}
	ll mid = (lo +hi)/2;
	if ( x <= mid) return Find(2 * p, lo, mid, x);
	else return Find(2 * p + 1, mid + 1, hi, x);
}
int main() {
	ll n,ans, t, up_price, i, x1, y1, x2, y2, lo, hi, x, down_price, deesh, doosh;
	
	cin >> n >> t >> up_price >> down_price;
	
	up_price *= -1;
	deesh = doosh = 0;
	for (i = 0; i <= n; i ++) {
		cin >> a[i];
		if (i == 0) continue;
		if (a[i] > a[i- 1]) deesh += (a[i] - a[i - 1]);
		else doosh += (a[i - 1] - a[i]);
	}
	while (t --) {
		cin >> lo >> hi >> x;
		val = 0;
		x1 = Find(1, 0, n, lo - 1);
		val = 0;
		x2 = Find(1, 0, n, lo);
		if ( x2 > x1) deesh -= (x2 - x1);
		else doosh -= (x1 - x2);
		if ( hi < n) {
			val =0;
			y1 = Find(1, 0, n, hi);
			val = 0;
			y2 = Find(1, 0, n, hi + 1);
			if ( y2 > y1) deesh -= (y2 - y1);
			else doosh -= (y1 - y2);
		}
		
		Update(1, 0, n, lo, hi, x);
		
		val = 0;
		x1 = Find(1, 0, n, lo - 1);
		val = 0;
		x2 = Find(1, 0, n, lo);
		if ( x2 > x1) deesh += (x2 - x1);
		else doosh += (x1 - x2);
		if ( hi < n) {
			val =0;
			y1 = Find(1, 0, n, hi);
			val = 0;
			y2 = Find(1, 0, n, hi + 1);
			if ( y2 > y1) deesh += (y2 - y1);
			else doosh += (y1 - y2);
		}
		ans = doosh * down_price + deesh * up_price;
		cout << ans << endl;
	}
	
}

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