Submission #521856

#	Time	Username	Problem	Language	Result	Execution time	Memory
521856		AdamGS	Foehn Phenomena (JOI17_foehn_phenomena)	C++17	100 / 100	220 ms	13244 KiB

foehn_phenomena

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const int LIM=2e5+7;
ll tr[4*LIM], N=1;
void upd(int l, int r, ll x) {
	l+=N; r+=N;
	tr[l]+=x;
	if(l!=r) tr[r]+=x;
	while(l/2!=r/2) {
		if(l%2==0) tr[l+1]+=x;
		if(r%2==1) tr[r-1]+=x;
		l/=2; r/=2;
	}
}
ll cnt(int v) {
	v+=N;
	ll ans=0;
	while(v) {
		ans+=tr[v];
		v/=2;
	}
	return ans;
}
int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	ll n, q, s, t, ans=0;
	cin >> n >> q >> s >> t;
	while(N<=n) N*=2;
	rep(i, n+1) {
		cin >> tr[N+i];
		if(tr[N+i-1]<tr[N+i]) ans-=s*(tr[N+i]-tr[N+i-1]);
		else ans+=t*(tr[N+i-1]-tr[N+i]);
	}
	while(q--) {
		int l, r, x;
		cin >> l >> r >> x;
		if(cnt(l-1)<cnt(l)) ans+=s*(cnt(l)-cnt(l-1));
		else ans-=t*(cnt(l-1)-cnt(l));
		if(r<n) {
			if(cnt(r)<cnt(r+1)) ans+=s*(cnt(r+1)-cnt(r));
			else ans-=t*(cnt(r)-cnt(r+1));
		}
		upd(l, r, x);
		if(cnt(l-1)<cnt(l)) ans-=s*(cnt(l)-cnt(l-1));
		else ans+=t*(cnt(l-1)-cnt(l));
		if(r<n) {
			if(cnt(r)<cnt(r+1)) ans-=s*(cnt(r+1)-cnt(r));
			else ans+=t*(cnt(r)-cnt(r+1));
		}
		cout << ans << '\n';
	}
}

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