Submission #480852

#	Time	Username	Problem	Language	Result	Execution time	Memory
480852		ymm	Foehn Phenomena (JOI17_foehn_phenomena)	C++17	100 / 100	216 ms	11460 KiB

foehn_phenomena

///
///   breakdown breakdown
///

#include <bits/stdc++.h>
#define Loop(x,l,r) for(ll x = ll(l); x < ll(r); ++x)
#define LoopR(x,l,r) for(ll x = ll(r)-1; x >= ll(l); --x)
typedef long long ll;
using namespace std;

const int N = 200'010;

ll fen[N];
void add(int r, ll x)
{
	while(r > 0)
	{
		fen[r] += x;
		r -= r&-r;
	}
}
void add(int l, int r, ll x)
{
	add(r, x);
	add(l, -x);
}
ll get(int i)
{
	++i;
	ll ans = 0;
	while(i < N){
		ans += fen[i];
		i += i&-i;
	}
	return ans;
}

int n, q;
ll s, t;

inline ll foo(ll x, ll y){return x < y? (x-y)*s: (x-y)*t;}
inline ll foo(int i){return i>n?0:foo(get(i-1),get(i));}

ll up(int l, int r, ll x)
{
	ll ans = foo(l)+foo(r);
	add(l,r,x);
	ans = foo(l)+foo(r)-ans;
	return ans;
}

int main()
{
	ios::sync_with_stdio(false); cin.tie(0);
	cin >> n >> q >> s >> t;
	ll ans = 0;
	Loop(i,0,n+1)
	{
		int x;
		cin >> x;
		if(i) ans += up(i,i+1,x);
	}
	while(q--)
	{
		int l, r, x;
		cin >> l >> r >> x; ++r;
		ans += up(l,r,x);
		cout << ans << '\n';
	}
}

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