Submission #1116148

#TimeUsernameProblemLanguageResultExecution timeMemory
1116148staszic_ojuzFoehn Phenomena (JOI17_foehn_phenomena)C++17
100 / 100
124 ms11336 KiB
#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; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...