Submission #870302

#	Time	Username	Problem	Language	Result	Execution time	Memory
870302		phoenix0423	Foehn Phenomena (JOI17_foehn_phenomena)	C++17	100 / 100	126 ms	11688 KiB

foehn_phenomena

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pll;
#define fastio ios::sync_with_stdio(false), cin.tie(0)
#define pb push_back
#define eb emplace_back
#define f first
#define s second
#define lowbit(x) x&-x
const int N = 998244353;
const int maxn = 2e5 + 5;
ll BIT[maxn];

void upd(int pos, int val){
	pos++;
	while(pos < maxn){
		BIT[pos] += val;
		pos += lowbit(pos);
	}
}
ll qry(int pos){
	pos++;
	ll ret = 0;
	while(pos > 0){
		ret += BIT[pos];
		pos -= lowbit(pos);
	}
	return ret;
}

int main(void){
	fastio;
	int n, q, s, t;
	cin>>n>>q>>s>>t;
	for(int i = 0; i <= n; i++){
		int x;
		cin>>x;
		upd(i, x);
		upd(i + 1, -x);
	}
	ll ans = 0;
	auto cost = [&](ll a, ll b) -> ll{
		if(a < b) return - s * (b - a);
		else return t * (a - b);
	};
	for(int i = 1; i <= n; i++){
		ll a = qry(i - 1), b = qry(i);
		ans += cost(a, b);
	}
	for(int i = 0; i < q; i++){
		int l, r, x;
		cin>>l>>r>>x;
		ans -= cost(qry(l - 1), qry(l));
		if(r != n) ans -= cost(qry(r), qry(r + 1));
		upd(l, x);
		upd(r + 1, -x);
		ans += cost(qry(l - 1), qry(l));
		if(r != n) ans += cost(qry(r), qry(r + 1));
		cout<<ans<<"\n";
	}
}

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