Submission #761779

#	Time	Username	Problem	Language	Result	Execution time	Memory
761779		KN200711	Foehn Phenomena (JOI17_foehn_phenomena)	C++14	100 / 100	250 ms	15664 KiB

foehn_phenomena

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

ll A[200001];
ll ans;

ll seg[800010];

void build(int lf, int rg, int nd) {
	if(lf == rg) seg[nd] = A[lf];
	else {
		seg[nd] = 0ll;
		int mid = (lf + rg)/2;
		build(lf, mid, 2*nd+1);
		build(mid+1, rg, 2*nd+2);
	}	
}

void upd(int lf, int rg, int nd, int clf, int crg, ll ad) {
	if(clf > rg || crg < lf) return;
	if(clf <= lf && rg <= crg) seg[nd] += ad;
	else {
		int mid = (lf + rg)/2;
		upd(lf, mid, 2*nd+1, clf, crg, ad);
		upd(mid+1, rg, 2*nd+2, clf, crg, ad);
	}
}

ll qry(int lf, int rg, int nd, int pos, ll ad) {
	if(lf == rg) return seg[nd] + ad;
	else {
		int mid = (lf + rg)/2;
		if(pos <= mid) return qry(lf, mid, 2*nd+1, pos, ad + seg[nd]);
		else return qry(mid+1, rg, 2*nd+2, pos, ad + seg[nd]);
	}
}

int main() {
	int N, Q;
	ll S, T;
	scanf("%d %d %lld %lld", &N, &Q, &S, &T);
	
	for(int i=0;i<=N;i++) scanf("%lld", &A[i]);
	ans = 0ll;
	for(int i=0;i<N;i++) {
		if(A[i] < A[i + 1]) {
			ans -= S * (A[i + 1] - A[i]);
		} else {
			ans += T * (A[i] - A[i + 1]);
		}
	}
	build(0, N, 0);
	
	while(Q--) {
		int l, r;
		ll x;
		scanf("%d %d %lld", &l, &r, &x);
		
		if(l > 0) {
			ll g = qry(0, N, 0, l - 1, 0);
			ll h = qry(0, N, 0, l, 0);
			
			if(g < h) ans += S * (h - g);
			else ans -= T * (g - h);
			
			h += x;
			if(g < h) ans -= S * (h - g);
			else ans += T * (g - h);
		}
		
		if(r + 1 <= N) {
			ll g = qry(0, N, 0, r, 0);
			ll h = qry(0, N, 0, r + 1, 0);
			
			if(g < h) ans += S * (h - g);
			else ans -= T * (g - h);
			
			g += x;
			if(g < h) ans -= S * (h - g);
			else ans += T * (g - h);
		}
		
		upd(0, N, 0, l, r, x);
		printf("%lld\n", ans);
	}
}

Compilation message (stderr)

foehn_phenomena.cpp: In function 'int main()':
foehn_phenomena.cpp:42:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   42 |  scanf("%d %d %lld %lld", &N, &Q, &S, &T);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
foehn_phenomena.cpp:44:29: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   44 |  for(int i=0;i<=N;i++) scanf("%lld", &A[i]);
      |                        ~~~~~^~~~~~~~~~~~~~~
foehn_phenomena.cpp:58:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   58 |   scanf("%d %d %lld", &l, &r, &x);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

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