Submission #364238

#	Time	Username	Problem	Language	Result	Execution time	Memory
364238		Rainbowbunny	Foehn Phenomena (JOI17_foehn_phenomena)	C++17	100 / 100	195 ms	13164 KiB

foehn_phenomena

#include <iostream>
#include <queue>
#include <algorithm>
#include <utility>
#include <vector>

int n, q;
long long S, T;
long long BIT[200005], A[200005];

void Add(int node, long long val)
{
	for(node; node <= n + 1; node += node & -node)
	{
		BIT[node] += val;
	}
}

long long Get(int node)
{
	long long ans = 0;
	for(node; node > 0; node -= node & -node)
	{
		ans += BIT[node];
	}
	return ans;
}

int main()
{
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(0);
	std::cout.tie(0);
	std::cin >> n >> q >> S >> T; 
	for(int i = 1; i <= n + 1; i++)
	{
		std::cin >> A[i];
		Add(i, A[i]);
		Add(i + 1, -A[i]);
	}
	long long ans = 0;
	for(int i = 1; i <= n; i++)
	{
		long long tmp = A[i + 1] - A[i];
		if(tmp > 0)
		{
			ans -= tmp * S;
		}
		else
		{
			ans -= tmp * T;
		}
	}
	while(q--)
	{
		int l, r;
		long long x;
		std::cin >> l >> r >> x;
		l++; r++;
		long long value = Get(l) - Get(l - 1);
		if(value > 0)
		{
			ans += value * S;
		}
		else
		{
			ans += value * T;
		}
		value += x;
		if(value > 0)
		{
			ans -= value * S;
		}
		else
		{
			ans -= value * T;
		}
		if(r != n + 1)
		{
			value = Get(r + 1) - Get(r);
			if(value > 0)
			{
				ans += value * S;
			}
			else
			{
				ans += value * T;
			}
			value -= x;
			if(value > 0)
			{
				ans -= value * S;
			}
			else
			{
				ans -= value * T;
			}
		}
		Add(l, x);
		Add(r + 1, -x);
		std::cout << ans << '\n';
	}
}

Compilation message (stderr)

foehn_phenomena.cpp: In function 'void Add(int, long long int)':
foehn_phenomena.cpp:13:6: warning: statement has no effect [-Wunused-value]
   13 |  for(node; node <= n + 1; node += node & -node)
      |      ^~~~
foehn_phenomena.cpp: In function 'long long int Get(int)':
foehn_phenomena.cpp:22:6: warning: statement has no effect [-Wunused-value]
   22 |  for(node; node > 0; node -= node & -node)
      |      ^~~~

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