Submission #1145554

#	Time	Username	Problem	Language	Result	Execution time	Memory
1145554		eloj	Foehn Phenomena (JOI17_foehn_phenomena)	C++20	100 / 100	93 ms	7340 KiB

foehn_phenomena

#include <bits/stdc++.h>

using namespace std;

struct FenwickTree {
    int n;
    vector<long long> tree;

    FenwickTree(int _n) : n(_n), tree(_n + 2, 0) {}

    void add(int pos, long long delta) {
        for (; pos <= n; pos += pos & -pos) {
            tree[pos] += delta;
        }
    }

    long long sum(int pos) {
        long long res = 0;
        for (; pos > 0; pos -= pos & -pos) {
            res += tree[pos];
        }
        return res;
    }

    void range_add(int l, int r, long long delta) {
        add(l, delta);
        if (r + 1 <= n) {
            add(r + 1, -delta);
        }
    }
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, Q, S, T;
    cin >> N >> Q >> S >> T;

    vector<long long> initial_A(N + 1);
    for (int i = 0; i <= N; ++i) {
        cin >> initial_A[i];
    }

    FenwickTree bit(N);

    long long total = 0;
    for (int i = 0; i < N; ++i) {
        long long a_prev = initial_A[i];
        long long a_curr = initial_A[i + 1];
        if (a_prev < a_curr) {
            total += (a_curr - a_prev) * (-S);
        } else {
            total += (a_prev - a_curr) * T;
        }
    }

    while (Q--) {
        int L, R, X;
        cin >> L >> R >> X;

        long long current_total = total;

        // Process pair (L-1, L)
        if (L >= 1) {
            int i = L - 1;
            long long a_prev = initial_A[i];
            if (i >= 1) {
                a_prev += bit.sum(i);
            }
            long long a_curr = initial_A[L] + bit.sum(L);
            if (a_prev < a_curr) {
                current_total -= (a_curr - a_prev) * (-S);
            } else {
                current_total -= (a_prev - a_curr) * T;
            }
        }

        // Process pair (R, R+1)
        if (R + 1 <= N) {
            long long a_prev = initial_A[R] + bit.sum(R);
            long long a_curr = initial_A[R + 1] + bit.sum(R + 1);
            if (a_prev < a_curr) {
                current_total -= (a_curr - a_prev) * (-S);
            } else {
                current_total -= (a_prev - a_curr) * T;
            }
        }

        // Apply the update
        bit.range_add(L, R, X);

        // Add new contributions
        if (L >= 1) {
            int i = L - 1;
            long long a_prev = initial_A[i];
            if (i >= 1) {
                a_prev += bit.sum(i);
            }
            long long a_curr = initial_A[L] + bit.sum(L);
            if (a_prev < a_curr) {
                current_total += (a_curr - a_prev) * (-S);
            } else {
                current_total += (a_prev - a_curr) * T;
            }
        }

        if (R + 1 <= N) {
            long long a_prev = initial_A[R] + bit.sum(R);
            long long a_curr = initial_A[R + 1] + bit.sum(R + 1);
            if (a_prev < a_curr) {
                current_total += (a_curr - a_prev) * (-S);
            } else {
                current_total += (a_prev - a_curr) * T;
            }
        }

        total = current_total;

        cout << total << '\n';
    }

    return 0;
}

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