Submission #83466

#	Time	Username	Problem	Language	Result	Execution time	Memory
83466		ekrem	Foehn Phenomena (JOI17_foehn_phenomena)	C++98	100 / 100	431 ms	153660 KiB

foehn_phenomena

#include <bits/stdc++.h>
#define st first
#define nd second
#define mp make_pair
#define pb push_back
#define sol (k+k)
#define sag (k+k+1)
#define orta ((bas+son)/2)
#define N 200005
using namespace std;

typedef long long ll;

ll n, q, s, t, l, r, x, ans, a[N], b[N], seg[4*N];

void bu(ll k, ll bas, ll son){
	if(bas == son){
		seg[k] = a[bas];
		return;
	}
	bu(sol, bas, orta);
	bu(sag, orta + 1, son);
}

ll qu(ll k, ll bas, ll son, ll x){
	if(x == 0)
		return 0;
	if(bas == son)
		return seg[k];
	if(x <= orta)
		return seg[k] + qu(sol, bas, orta, x);
	return seg[k] + qu(sag, orta + 1, son, x);
}

void up(ll k, ll bas, ll son, ll x, ll y, ll z){
	if(bas > y or son < x)
		return;
	if(bas >= x and son <= y){
		seg[k] += z;
		return;
	}
	up(sol, bas, orta, x, y, z);
	up(sag, orta + 1, son, x, y, z);
}

int main() {
	// freopen("in.txt", "r", stdin);
	// freopen("out.txt", "w", stdout);
	scanf("%lld %lld %lld %lld",&n ,&q ,&s ,&t);
	for(ll i = 0; i <= n; i++)
		scanf("%lld",a + i);
	for(ll i = 1; i <= n; i++){
		if(a[i] > a[i - 1])
			b[i] = -s * (a[i] - a[i - 1]);
		else
			b[i] = t * (a[i - 1] - a[i]);
		ans += b[i];
	}
	bu(1, 1, n);
	while(q--){
		scanf("%lld %lld %lld",&l ,&r ,&x);
		ans -= b[r + 1] + b[l];
		up(1, 1, n, l, r, x);
		ll a1 = qu(1, 1, n, l - 1);
		ll a2 = qu(1, 1, n, l);
		ll a3 = qu(1, 1, n, r);
		ll a4 = qu(1, 1, n, r + 1);
		if(a2 > a1)
			b[l] = -s * (a2 - a1);
		else
			b[l] = t * (a1 - a2);

		if(a4 > a3)
			b[r + 1] = -s * (a4 - a3);
		else
			b[r + 1] = t * (a3 - a4);
		ans += b[r + 1] + b[l];
		printf("%lld\n", ans);
	}
	return 0;
}

Compilation message (stderr)

foehn_phenomena.cpp: In function 'int main()':
foehn_phenomena.cpp:49: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:51: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:61: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