Submission #51448

#	Time	Username	Problem	Language	Result	Execution time	Memory
51448		MoesashiMinamoto	Foehn Phenomena (JOI17_foehn_phenomena)	C++14	100 / 100	764 ms	14264 KiB

foehn_phenomena

#include <bits/stdc++.h>

using namespace std;
#define int 	long long
int n, q, s, t;
long long a[200005];

long long it[800005], lazy[800005];
long long res = 0;

void init(int k, int l, int r)
{
	if (l == r)
	{
		it[k] = a[l];
		return;
	}
	int mid = (l + r)/2;
	init(k * 2, l, mid);
	init(k * 2 + 1, mid+1, r);
	it[k] = it[k * 2] + it[k * 2 + 1];
}

void update(int k, int l, int r, int L, int R, int val)
{
	if (l > R || r < L) return;
	if (L <= l && R >= r) 
	{
		it[k] += val * (r - l + 1);
		lazy[k] += val;
		return;
	}
    int mid = (l+r) / 2;
    int t = lazy[k];
    lazy[k * 2] += t;
    lazy[k * 2 + 1] += t;
    it[k * 2] += t * (mid - l + 1);
    it[k * 2 + 1] += t * (r - mid);
    lazy[k] = 0;
	update(k * 2, l, mid, L, R, val);
	update(k * 2 + 1, mid + 1, r, L, R, val);
	it[k] = it[k * 2] + it[k * 2 + 1];
}

long long get(int k, int l, int r, int L, int R)
{
    if (R < l || L > r) return 0ll;
    if (L <= l && r <= R) {
    	return it[k];
    }
    int mid = (l+r) / 2;
    int t = lazy[k];
    lazy[k * 2] += t;
    lazy[k * 2 + 1] += t;
    it[k * 2] += t * (mid - l + 1);
    it[k * 2 + 1] += t * (r - mid);
    lazy[k] = 0;
    return get(k * 2, l, mid, L, R) + get(k * 2 + 1, mid + 1, r, L, R);
}

void in()
{
	scanf("%lld%lld%lld%lld", &n, &q, &s, &t);
	for (int i = 0; i <= n; i++)
	{
		scanf("%lld", &a[i]);
	}
}

void ou()
{
	printf("%lld\n", res);
}

void solve()
{
	init(1, 1, n);
	for (int i = 1; i <= n; i++)
	{
		res += (a[i-1] - a[i] < 0) ? (s * (a[i-1] - a[i])) : (t * (a[i-1] - a[i]));
	}
	for (int i = 1; i <= q; i++)
	{
		int l, r, x;
		scanf("%lld%lld%lld", &l, &r, &x);
		long long precl, precr;
		precl = get(1, 1, n, l, l);
		precr = get(1, 1, n, r, r);
		update(1, 1, n, l, r, x);
		long long curl = get(1, 1, n, l, l);
		long long curr = get(1, 1, n, r, r);
		long long re1 = 0, re2 = 0;
		a[l - 1] = get(1, 1, n, l-1, l-1);
		re1 += (a[l-1] - precl < 0) ? (s * (a[l-1] - precl)) : (t * (a[l-1] - precl));
		re2 += (a[l-1] - curl < 0) ? (s * (a[l-1] - curl)) : (t * (a[l-1] - curl));
		if (r < n)
		{
			a[r+1] = get(1, 1, n, r+1, r+1);
			re1 += (precr - a[r+1] < 0) ? (s * (precr - a[r+1])) : (t * (precr - a[r+1]));
			re2 += (curr - a[r+1] < 0) ? (s * (curr - a[r+1])) : (t * (curr - a[r+1]));
		}
		res += re2 - re1;
		ou();
	}
}


signed main()
{
	in();
	solve();
}

Compilation message (stderr)

foehn_phenomena.cpp: In function 'void in()':
foehn_phenomena.cpp:63:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld%lld%lld%lld", &n, &q, &s, &t);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
foehn_phenomena.cpp:66:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld", &a[i]);
   ~~~~~^~~~~~~~~~~~~~~
foehn_phenomena.cpp: In function 'void solve()':
foehn_phenomena.cpp:85:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld%lld%lld", &l, &r, &x);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

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