Submission #1149049

#	Time	Username	Problem	Language	Result	Execution time	Memory
1149049		zhasyn	Foehn Phenomena (JOI17_foehn_phenomena)	C++20	0 / 100	91 ms	9740 KiB

foehn_phenomena

#include <bits/stdc++.h>
#define pb push_back
#define pf push_front
using namespace std;
#define F first
#define S second
typedef long long ll;
#define pii pair <int, int>
#define pll pair <ll, ll>
typedef long double ld;
const ll N = 2 * 1e5 + 100, M = 4096 + 10, len = 21, inf = 1e18;
const ll mod = 1e9 + 7;
ll a[N], fen[N], s, t;
pll was[N];
void upd(ll i, ll delta){
	for(; i < N; i = (i | (i + 1))){
		fen[i] += delta;
	}
}
ll get(ll r){
	ll res = 0;
	for(; r >= 0; r = (r & (r + 1)) - 1){
		res += fen[r];
	}
	return res;
}
ll calc(ll a, ll b){
	if(a > b) return -(a - b) * s;
	else return (b - a) * t;
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  ll n, q, ans;
  cin >> n >> q >> s >> t;
  for(ll i = 0; i <= n; i++){
  	cin >> a[i];
  }
  for(ll i = 1; i <= n; i++){
  	ans += calc(a[i], a[i - 1]);
  	was[i] = {a[i], a[i - 1]};
  	upd(i, a[i]);
  	upd(i + 1, -a[i]);
  }
  
  for(ll i = 0, l, r, x; i < q; i++){
  	cin >> l >> r >> x;
  	upd(l, x);
  	upd(r + 1, -x);
  	ans -= calc(was[l].F, was[l].S);
  	ll fir = get(l - 1), sec = get(l);
  	was[l] = {sec, fir};
  	ans += calc(was[l].F, was[l].S);
  	
  	
  	if(r + 1 <= n){
  		ans -= calc(was[r + 1].F, was[r + 1].S);
  		fir = get(r);
  		sec = get(r + 1);
  		was[r + 1] = {sec, fir};
  		ans += calc(was[r + 1].F, was[r + 1].S);
  	}
  	if(i == q - 1) cout << ans << endl;
  	else cout << ans;
  }
  return 0;
}

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