제출 #1010627

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1010627		Muhammet	Foehn Phenomena (JOI17_foehn_phenomena)	C++17	100 / 100	366 ms	25424 KiB

foehn_phenomena

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

#define ll long long

const int N = 2000005;

ll n, q, s, t, a[N], b[N], st[N], lz[N], k;

int bld(int nd, int l, int r){
	if(l == r) return st[nd] = a[l];
	int md = (l + r) / 2;
	return st[nd] = bld(nd*2,l,md) + bld(nd*2+1,md+1,r);
}

int upd(int nd, int l, int r, int x, int y, int vl){
	st[nd] += ((r-l+1) * lz[nd]);
	lz[nd*2] += lz[nd];
	lz[nd*2+1] += lz[nd];
	lz[nd] = 0;
	if(l > y or r < x) return st[nd];
	if(l >= x and r <= y){
		lz[nd] += vl;
		st[nd] += ((r-l+1) * lz[nd]);
		lz[nd*2] += lz[nd];
		lz[nd*2+1] += lz[nd];
		lz[nd] = 0;
		return st[nd];
	}
	int md = (l + r) / 2;
	return st[nd] = upd(nd*2, l, md, x, y, vl) + upd(nd*2+1, md+1, r, x, y, vl);
}

int fnd(int nd, int l, int r, int ind){
	st[nd] += ((r-l+1) * lz[nd]);
	lz[nd*2] += lz[nd];
	lz[nd*2+1] += lz[nd];
	lz[nd] = 0;
	if(l > ind or r < ind) return st[nd];
	if(l == r){
		k = st[nd];
		return st[nd];
	}
	int md = (l + r) / 2;
	return st[nd] = fnd(nd*2, l, md, ind) + fnd(nd*2+1, md+1, r, ind);
}

int main(){
	ios::sync_with_stdio(false); cin.tie(0);

	cin >> n >> q >> s >> t;

	for(int i = 1; i <= n+1; i++){
		cin >> a[i];
	}
	bld(1,1,n+1);

	ll ans = 0;
	for(int i = 1; i <= n; i++){
		if(a[i] < a[i+1]) b[i] = -s;
		else b[i] = t;
		b[i] *= (abs(a[i]-a[i+1]));
		ans += b[i];
	}

	for(int i = 1; i <= q; i++){
		ll l, r, x;
		cin >> l >> r >> x;
		l++;
		r++;
		upd(1,1,n+1,l,r,x);
		ans -= b[l-1];
		ans -= b[r];
		fnd(1,1,n+1,l-1);
		ll al1 = k;
		fnd(1,1,n+1,l);
		ll al = k;
		fnd(1,1,n+1,r);
		ll ar = k;
		fnd(1,1,n+1,r+1);
		ll ar1 = k;
		if(al1 < al) b[l-1] = -s;
		else b[l-1] = t;
		b[l-1] *= (abs(al-al1));
		ans += b[l-1];
		if(r <= n){
			if(ar < ar1) b[r] = -s;
			else b[r] = t;
			b[r] *= (abs(ar-ar1));
			ans += b[r];
		}
		cout << ans << '\n';
	}
}

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