제출 #1116148

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1116148		staszic_ojuz	Foehn Phenomena (JOI17_foehn_phenomena)	C++17	100 / 100	124 ms	11336 KiB

foehn_phenomena

#include <iostream>

using namespace std;

typedef long long ll;

const int MAXN = 200002;

int n, q;

ll s, t;

ll wartosci_miedzy[MAXN];

int stala;

ll drzewo_przedzialowe_przedzial_punkt[(1 << 19) + 2];

ll val[MAXN];

ll wynik = 0;

void zrob_wartosci_miedzy() {
	for (int i = 1; n >= i; i++) {
		if (val[i] > val[i - 1]) {
			wartosci_miedzy[i] = s * (val[i - 1] - val[i]);
		} else {
			wartosci_miedzy[i] = t * (val[i - 1] - val[i]);
		}
		wynik+= wartosci_miedzy[i];
	}
}

int find_stala() {
	int x = 1;
	while (n > x) {
		x*=2;
	}
	return x;
}

ll find_val(int ind) {
	ll wynik = 0;
	while (ind) {
		wynik += drzewo_przedzialowe_przedzial_punkt[ind];
		ind /= 2;
	}
	return wynik;
}

void update(int l, int r, ll co_dodac) {
	if (l == r) {
		drzewo_przedzialowe_przedzial_punkt[l] += co_dodac;
		return;
	}
	drzewo_przedzialowe_przedzial_punkt[l] += co_dodac;
	drzewo_przedzialowe_przedzial_punkt[r] += co_dodac;
	while ((r - 1) > l) {
		if (l%2 == 0) {
			drzewo_przedzialowe_przedzial_punkt[l + 1] += co_dodac;
		}
		if (r%2 == 1) {
			drzewo_przedzialowe_przedzial_punkt[r - 1] += co_dodac;
		}
		r /= 2;
		l /= 2;
	}
}
	
void poj() {
	//cout << "\n\nprzyklad\n\n";
	
	int l, r;
	ll x;
	
	cin >> l >> r >> x;
	
	update(l + stala, r + stala, x);
	
	ll val_left = val[l] + find_val(l + stala);
	ll val_left_left = val[l - 1] + find_val(l - 1 + stala);
	
	ll val_right = val[r] + find_val(r + stala);
	ll val_right_right= -1;
	if (r != n) {
		val_right_right = val[r + 1] + find_val(r + 1 + stala);
	}
	
	ll stare_left = val_left - x;
	ll stare_right = val_right - x;
	
	if (stare_left > val_left_left) {
		//cout << "w ynik -= " << s * (val_left_left - stare_left) << "\n";
		wynik -= s * (val_left_left - stare_left);
	} else {
		//cout << "wynik -= " << t * (val_left_left - stare_left) << "\n";
		wynik -= t * (val_left_left - stare_left);
	}
	
	if (val_right_right != -1) {
		//cout << "wynik -= ";
		if (stare_right < val_right_right) {
			//cout << s * (stare_right - val_right_right);
			wynik -= s * (stare_right - val_right_right);
		} else {
			//cout << t * (stare_right - val_right_right);
			wynik -= t * (stare_right - val_right_right);
		}
		//cout << "\n";
	}
	//cout << "wynik += ";
	if (val_left > val_left_left) {
		//cout << s * (val_left_left - val_left);
		wynik += s * (val_left_left - val_left);
	} else {
		//cout << t * (val_left_left - val_left);
		wynik += t * (val_left_left - val_left);
	}
	//cout << "\n";
	//cout << "wynik += ";
	if (val_right_right != -1) {
		if (val_right < val_right_right) {
			//cout << s * (val_right - val_right_right);
			wynik += s * (val_right - val_right_right);
		} else {
			//cout << t * (val_right - val_right_right);
			wynik += t * (val_right - val_right_right);
		}	
	}
	//cout << "\n";
	//cout << "val_left " << val_left << " val_right "<< val_right << " val_left_left " << val_left_left << " val_right_right "<< val_right_right << "\n";
	//cout << "stare_left " << stare_left <<" stare_right "<< stare_right << "\n";
	//cout << "wynik: " << wynik << "\n";
	cout << wynik << "\n";
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> n >> q >> s >> t;
	
	for (int i = 0; n >= i; i++) {
		cin >> val[i];
	}
	
	zrob_wartosci_miedzy();
	stala = find_stala();
	
	for (int i = 0; q > i; i++) {
		poj();
	}
	
	return 0;
}

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