Submission #1158507

#	Time	Username	Problem	Language	Result	Execution time	Memory
1158507		achi	Foehn Phenomena (JOI17_foehn_phenomena)	C++20	0 / 100	63 ms	7748 KiB

foehn_phenomena

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

#define ll long long
#define fastio ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

int main() {
    fastio;

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

    vector<ll> altitudes(N + 1), diff(N + 2, 0), tempDiff(N + 1, 0);
    ll temp = 0;

    for (ll i = 0; i <= N; i++) {
        cin >> altitudes[i];
        if (i > 0) {
            if (altitudes[i - 1] < altitudes[i])
                temp += (altitudes[i - 1] - altitudes[i]) * S;
            else
                temp += (altitudes[i - 1] - altitudes[i]) * T;
            tempDiff[i] = temp;
        }
    }

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

        // Revert previous temperature contribution
        if (L > 0) {
            if (altitudes[L - 1] < altitudes[L])
                temp -= (altitudes[L - 1] - altitudes[L]) * S;
            else
                temp -= (altitudes[L - 1] - altitudes[L]) * T;
        }
        if (R < N) {
            if (altitudes[R] < altitudes[R + 1])
                temp -= (altitudes[R] - altitudes[R + 1]) * S;
            else
                temp -= (altitudes[R] - altitudes[R + 1]) * T;
        }

        // Apply update with difference array
        diff[L] += X;
        diff[R + 1] -= X;

        // Recalculate only the affected edges
        altitudes[L] += X;
        if (L > 0) {
            if (altitudes[L - 1] < altitudes[L])
                temp += (altitudes[L - 1] - altitudes[L]) * S;
            else
                temp += (altitudes[L - 1] - altitudes[L]) * T;
        }

        if (R < N) {
            altitudes[R] += X;
            if (altitudes[R] < altitudes[R + 1])
                temp += (altitudes[R] - altitudes[R + 1]) * S;
            else
                temp += (altitudes[R] - altitudes[R + 1]) * T;
        }

        cout << temp << "\n";
    }

    return 0;
}

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