Submission #231628

#	Time	Username	Problem	Language	Result	Execution time	Memory
231628		peijar	Foehn Phenomena (JOI17_foehn_phenomena)	C++17	100 / 100	240 ms	19932 KiB

foehn_phenomena

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

#define SZ(v) ((int)(v).size())
using ll = long long;

template<class T>
struct Segtree_rangeAdd_pointQuery
{
	int nb_elem;
	int LIM;
	vector<T> seg;
	int deb;

	Segtree_rangeAdd_pointQuery(int N)
	{
		nb_elem = 1;
		while (nb_elem < N)
			nb_elem *= 2;
		LIM = 4 * nb_elem;
		deb = nb_elem-1;
		seg.resize(LIM);
	}

	Segtree_rangeAdd_pointQuery(vector<T> arr)
	{
		*this = Segtree_rangeAdd_pointQuery(SZ(arr));
		for (int i(0); i < SZ(arr); ++i)
			seg[deb + i] = arr[i];
	}

	void add(int lo, int up, T delta)
	{
		lo += deb;
		up += deb;
		while (lo < up)
		{
			if (up%2)
				seg[up] += delta;
			if (lo%2==0)
				seg[lo] += delta;
			lo /= 2;
			up = (up-2)/2;
		}
		if (lo == up)
			seg[lo] += delta;
	}

	T query(int id)
	{
		id += deb;
		T ans(seg[id]);
		while (id)
		{
			id = (id-1)/2;
			ans += seg[id];
		}
		return ans;
	}
};

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

	ll nb_elem, nb_requetes, up, down;
	cin >> nb_elem >> nb_requetes >> up >> down;
	vector<ll> arr(nb_elem+1);
	for (auto &v : arr)
		cin >> v;
	Segtree_rangeAdd_pointQuery<ll> seg = Segtree_rangeAdd_pointQuery<ll>(arr);
	ll temp(0);

	auto find_delta = [&](ll a, ll b)
	{
		if (a >= b)
			return -down * (b - a);
		else
			return -up * (b-a);
	};
	for (int i(0); i < nb_elem; ++i)
		temp += find_delta(arr[i], arr[i+1]);

	while (nb_requetes--)
	{
		ll L, R, delta;
		cin >> L >> R >> delta;
		ll u1 = seg.query(L-1);
		ll u2 = seg.query(L);
		ll v1 = seg.query(R);
		ll v2 = (R < nb_elem ? seg.query(R+1) : v1);
		temp -= find_delta(u1, u2);
		temp -= find_delta(v1, v2);
		seg.add(L, R, delta);
		u2 = seg.query(L);
		v1 = seg.query(R);
		temp += find_delta(u1, u2);
		if (R < nb_elem)
			temp += find_delta(v1, v2);
		cout << temp << '\n';

	}
}

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