Submission #1081125

#	Time	Username	Problem	Language	Result	Execution time	Memory
1081125		Trent	Foehn Phenomena (JOI17_foehn_phenomena)	C++17	100 / 100	121 ms	11600 KiB

foehn_phenomena

#include "bits/stdc++.h"
using namespace std;
#define forR(i, x) for(int i=0; i<(x); ++i)
#define REP(i, a, b) for(int i=(a); i<(b); ++i)
#define all(x) x.begin(), x.end()
#define boost() cin.sync_with_stdio(0); cin.tie(0)
typedef long long ll;
typedef vector<int> vi;

const int MN = 2e5 + 10;

ll bit[MN];
void upd(int i, ll by) {
	++i;
	for(; i < MN; i+=i&-i) bit[i] += by;
}
ll qu(int i) {
	++i;
	ll tot = 0;
	for(; i > 0; i-=i&-i) tot += bit[i];
	return tot;
}

signed main() {
	boost();
    int n, q; ll s, t; cin >> n >> q >> s >> t;
    ll tot = 0;
	forR(i, n+1) {
		ll v; cin >> v;
		upd(i, v - (i == 0 ? 0 : qu(i-1)));
	}
	REP(i, 1, n+1) {
		ll ac = qu(i), ap=qu(i-1);
		if(ac > ap) tot -= s * (ac-ap);
		else tot += t * (ap - ac);
	}
	forR(j, q){
		int l, r; ll x; cin >> l >> r >> x;
		if(l > 0){
			ll ac=qu(l), ap=qu(l-1);
			if(ac > ap) tot += s * (ac-ap);
			else tot -= t * (ap - ac);
			ll na = ac + x;
			if(na > ap) tot -= s * (na-ap);
			else tot += t * (ap - na);
		}
		if(r < n){
			ll ac=qu(r+1), ap=qu(r);
			if(ac > ap) tot += s * (ac-ap);
			else tot -= t * (ap-ac);
			ll na = ap + x;
			if(ac > na) tot -= s * (ac-na);
			else tot += t * (na-ac);
		}
		upd(l, x);
		upd(r+1, -x);
		cout << tot << '\n';
	}
}

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