Submission #74565

#	Time	Username	Problem	Language	Result	Execution time	Memory
74565		shoemakerjo	Foehn Phenomena (JOI17_foehn_phenomena)	C++14	100 / 100	299 ms	167452 KiB

foehn_phenomena

#include <bits/stdc++.h>

using namespace std;
#define ll long long
#define maxn 200010

int N, Q;
ll S, T;

ll A[maxn];
ll BIT[maxn]; //store offsets

void up(int spot, ll diff) {
	while (spot < maxn) {
		BIT[spot] += diff;
		spot += spot & (-spot);
	}
}

void update(int l, int r, ll diff) {
	l+=2;
	r+=2;
	up(l, diff);
	up(r+1, 0-diff);
}

ll query(int spot) {
	spot+=2;
	ll res = 0LL;
	while (spot > 0) {
		res += BIT[spot];
		spot -= spot & (-spot);
	}
	return res;
}

ll getval(int spot) {
	return A[spot] + query(spot); //think this is good
}

ll docons(ll v1, ll v2) {
	if (v1 < v2) {
		return -1LL*S*(v2-v1);
	}
	return T*(v1-v2);
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> N >> Q >> S >> T;
	for (int i = 0; i <= N; i++) {
		cin >> A[i];
	}
	ll cans = 0LL;
	for (int i = 1; i <= N; i++) {
		cans += docons(A[i-1], A[i]);
	}
	int l, r;
	ll x;
	while (Q--) {
		cin >> l >> r >> x;
		ll odiff = 0LL;
		ll v1, v2;
		if (l != 0) {
			odiff += docons(getval(l-1), getval(l));
		}
		if (r != N) {
			odiff += docons(getval(r), getval(r+1));
		}
		cans -= odiff;
		update(l, r, x);
		if (l != 0) cans += docons(getval(l-1), getval(l));
		if (r != N) cans += docons(getval(r), getval(r+1));

		cout << cans << '\n';
	}	
	cout.flush();

}

Compilation message (stderr)

foehn_phenomena.cpp: In function 'int main()':
foehn_phenomena.cpp:64:6: warning: unused variable 'v1' [-Wunused-variable]
   ll v1, v2;
      ^~
foehn_phenomena.cpp:64:10: warning: unused variable 'v2' [-Wunused-variable]
   ll v1, v2;
          ^~

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