Submission #209144

#	Time	Username	Problem	Language	Result	Execution time	Memory
209144		pavement	Foehn Phenomena (JOI17_foehn_phenomena)	C++17	100 / 100	191 ms	8904 KiB

foehn_phenomena

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

int N, Q, S, T, O, L, R, X, A[200005], ft[200005];

inline int ls(int x) { return x & -x; }

int qry(int p) {
	int r = 0;
	for (; p; p -= ls(p)) r += ft[p];
	return r;
}

void upd(int l, int r, int v) {
	for (; l <= N; l += ls(l)) ft[l] += v;
	for (r++; r <= N; r += ls(r)) ft[r] -= v;
}

main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> N >> Q >> S >> T >> A[0];
	for (int i = 1; i <= N; i++) {
		cin >> A[i];
		if (A[i - 1] >= A[i]) O += T * (A[i - 1] - A[i]);
		else O -= S * (A[i] - A[i - 1]);
		upd(i, i, A[i]);
	}
	while (Q--) {
		cin >> L >> R >> X;
		int gay1 = qry(L - 1), gay2 = qry(L), gay3 = qry(R), gay4 = qry(R + 1);
		if (gay1 >= gay2) O -= T * (gay1 - gay2);
		else O += S * (gay2 - gay1);
		if (R != N) {
			if (gay3 >= gay4) O -= T * (gay3 - gay4);
			else O += S * (gay4 - gay3);
		}
		upd(L, R, X);
		gay2 += X;
		gay3 += X;
		if (gay1 >= gay2) O += T * (gay1 - gay2);
		else O -= S * (gay2 - gay1);
		if (R != N) {
			if (gay3 >= gay4) O += T * (gay3 - gay4);
			else O -= S * (gay4 - gay3);
		}
		cout << O << '\n';
	}
}

Compilation message (stderr)

foehn_phenomena.cpp:20:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main() {
      ^

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