Submission #948046

#	Time	Username	Problem	Language	Result	Execution time	Memory
948046		4QT0R	Foehn Phenomena (JOI17_foehn_phenomena)	C++17	100 / 100	123 ms	13648 KiB

foehn_phenomena

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

const ll base = 1<<18;
ll tree[2*base];

void zmien(ll a, ll b, ll v){
	a+=base-1;
	b+=base+1;
	while(a/2!=b/2){
		if (!(a&1))tree[a+1]+=v;
		if (b&1)tree[b-1]+=v;
		a>>=1;
		b>>=1;
	}
}

ll sprawdz(ll v){
	v+=base;
	ll ans=0;
	while(v){
		ans+=tree[v];
		v>>=1;
	}
	return ans;
}

ll cur=0,n,q,s,t;
void change_wind(ll v, ll diff){
	if (v==n+1)return;
	ll h1=sprawdz(v-1),h2=sprawdz(v);
	if (h1<h2)cur+=(h2-h1)*s;
	else cur+=(h2-h1)*t;
	if (h1<h2+diff)cur-=(h2+diff-h1)*s;
	else cur-=(h2+diff-h1)*t;
}

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

	ll a,b,c;
	cin >> n >> q >> s >> t;
	for (ll i = 0; i<=n; i++){
		cin >> tree[base+i];
	}
	for (ll i = 1; i<=n; i++){
		if ((tree[base+i]>tree[base+i-1]))cur-=(tree[base+i]-tree[base+i-1])*s;
		else cur-=(tree[base+i]-tree[base+i-1])*t;
	}
	for (ll i = 1; i<=q; i++){
		cin >> a >> b >> c;
		change_wind(a,c);
		change_wind(b+1,-c);
		zmien(a,b,c);
		cout << cur << '\n';
	}
}

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