Submission #114266

#	Time	Username	Problem	Language	Result	Execution time	Memory
114266		jhnah917	Foehn Phenomena (JOI17_foehn_phenomena)	C++14	30 / 100	204 ms	7292 KiB

foehn_phenomena

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

int n, q;
ll S, T;
ll ans;

vector<ll> v;

struct BIT{
	ll tree[202020];
	
	void update(int x, ll v){
		x++;
		while(x < 202020){
			tree[x] += v;
			x += x & -x;
		}
	}
	
	ll query(int x){
		ll ret = 0; x++;
		while(x){
			ret += tree[x];
			x -= x & -x;
		}
		return ret;
	}
	
	void update(int l, int r, ll v){
		update(l, v); update(r+1, -v);
	}
}seg;

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> n >> q >> S >> T; v.resize(n+1);
	for(int i=0; i<=n; i++){
		cin >> v[i];
		seg.update(i, i, v[i]);
	}
	
	for(int i=0; i<n; i++){
		if(v[i] < v[i+1]) ans -= (v[i+1] - v[i]) * S;
		else ans += (v[i] - v[i+1]) * T;
	}
	
	while(q--){
		int s, e, x; cin >> s >> e >> x;
		if(s != 0){
			int prv = seg.query(s-1);
			int now = seg.query(s);
			if(prv < now) ans -= (prv - now) * S;
			else ans += (now - prv) * T;
		}
		if(e != n){
			int prv = seg.query(e);
			int now = seg.query(e+1);
			if(prv < now) ans -= (prv - now) * S;
			else ans += (now - prv) * T;
		}
		seg.update(s, e, x);
		
		if(s != 0){
			int prv = seg.query(s-1);
			int now = seg.query(s);
			if(prv < now) ans -= (now - prv) * S;
			else ans += (prv - now) * T;
		}
		if(e != n){
			int prv = seg.query(e);
			int now = seg.query(e+1);
			if(prv < now) ans -= (now - prv) * S;
			else ans += (prv - now) * T;
		}
		cout << ans << "\n";
	}
}

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