제출 #209138

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
209138		pavement	Foehn Phenomena (JOI17_foehn_phenomena)	C++17	0 / 100	157 ms	5444 KiB

foehn_phenomena

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

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;
}

void build() {
	for (int i = 1; i <= N; i++) {
		ft[i] += A[i] - A[i - 1];
		if (i + ls(i) <= N) ft[i + ls(i)] += A[i] - A[i - 1];
	}
}

int 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]);
	}
	build();
	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';
	}
}

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