Submission #887637

#	Time	Username	Problem	Language	Result	Execution time	Memory
887637		BBart888	Foehn Phenomena (JOI17_foehn_phenomena)	C++17	100 / 100	487 ms	26628 KiB

foehn_phenomena

#include <cstdio>
#include <iostream>
#include <vector>
#include <list>
#include <string>
#include <set>
#include <map>
#include <algorithm>
#include <fstream>
#include <cmath>
#include <queue>
#include <stack>
#include <cassert>
#include <cstring>
#include <climits>
#include <functional>
#include<cstdlib>
//#include "arc.h"
//#include "dreaming.h"


using namespace std;
typedef pair<int, int> PII;
typedef vector<int> VI;
typedef long long LL;



const int MAXN = 4e5 + 11; 
using ll = long long;
const ll mod1 = 1e9 + 7;
const ll mod2 = 1000000021;
const ll P = 31;



void setIO(string name = "") {
	cin.tie(0)->sync_with_stdio(0); // see /general/fast-io
	if ((name.size())) {
		//freopen((name + ".in").c_str(), "r", stdin); // see /general/input-output
		//freopen((name + ".out").c_str(), "w", stdout);
	}
}

ll n, q, S,T;
ll t[4 * MAXN];
ll lazy[4 * MAXN];
ll ans;
ll x[MAXN];

void push(int v,int tl,int tm,int tr)
{
	if (lazy[v])
	{
		t[2 * v + 1] += (tr - tm) * lazy[v];
		t[2 * v] += (tm - tl + 1) * (lazy[v]);
		lazy[2 * v + 1] += lazy[v];
		lazy[2 * v] += lazy[v];
		lazy[v] = 0;
	}
}


void upd(int v, int tl, int tr, int l, int r, ll val)
{
	if (l > r)
		return;
	if (tl == l && tr == r)
	{
		t[v] += val * (tr - tl + 1);
		lazy[v] += val;
		return;
	}
	int tm = (tl + tr) / 2;
	push(v, tl, tm, tr);
	upd(2 * v, tl, tm, l, min(r, tm), val);
	upd(2 * v + 1, tm + 1, tr, max(l, tm + 1), r, val);
	t[v] = t[2 * v] + t[2 * v + 1];
}


ll query(int v, int tl, int tr, int l, int r)
{
	if (l > r)
		return 0;
	if (tl == l && tr == r)
		return t[v];
	int tm = (tl + tr) / 2;
	push(v, tl, tm, tr);
	return query(2 * v, tl, tm, l, min(r, tm)) +
		query(2 * v + 1, tm + 1, tr, max(l, tm + 1), r); 
}


ll calc(int i1, int i2)
{
	ll I1 = query(1, 0, MAXN, i1, i1);
	ll I2 = query(1, 0, MAXN, i2, i2);
	if (I1 < I2)
		return  -(I2 - I1) * S;
	else
		return (I1 - I2) * T;
}


int main()
{
	cin.tie(0);
	cout.tie(0);
	ios_base::sync_with_stdio(false);
	//setIO("radio");
	
	cin >> n >> q >> S >> T;

	for (int i = 0; i <= n; i++)
	{
		cin >> x[i];
		upd(1, 0, MAXN, i, i, x[i]);
	}

	for (int i = 1; i <= n; i++)
	{
		if (x[i] > x[i - 1])
		{
			ans -= S * (x[i] - x[i - 1]);
		}
		else
			ans += T * (x[i - 1] - x[i]);
	}

	for (int i = 0; i < q; i++)
	{
		ll a, b, d;
		cin >> a >> b >> d;

		ll L = calc(a - 1, a);
		ll R = calc(b, b + 1);
		upd(1, 0, MAXN, a, b, d);
		if (a >= 1)
		{
			ans -= L;
			ans += calc(a - 1, a);
		}
		if (b < n)
		{
			ans -= R;
			ans += calc(b, b + 1);
		}
		
		cout << ans << '\n';
	}



	


	

	return 0;
}

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