Submission #669705

#	Time	Username	Problem	Language	Result	Execution time	Memory
669705		GrandTiger1729	Foehn Phenomena (JOI17_foehn_phenomena)	C++17	100 / 100	133 ms	7232 KiB

foehn_phenomena

#include <iostream>
#include <vector>
using namespace std;

struct BIT{
    vector<long long> bit;
    int n;
    BIT(int _n): n(_n){
        bit.resize(n + 1);
    }
    void add(int p, long long u){
        for (int i = p; i <= n; i += i & -i){
            bit[i] += u;
        }
    }
    long long query(int p){
        long long ret = 0;
        for (int i = p; i > 0; i -= i & -i){
            ret += bit[i];
        }
        return ret;
    }
};

int main(){
    cin.tie(0)->sync_with_stdio(0);
    int n, q;
    long long S, T; 
    cin >> n >> q >> S >> T;
    n++;
    long long a[n]{};
    for (int i = 0; i < n; i++){
        cin >> a[i];
    }
    auto val = [&](long long x, long long y) -> long long {
        if (x < y) return (x - y) * S;
        return (x - y) * T;
    };
    long long ans = 0;
    for (int i = 1; i < n; i++){
        ans += val(a[i - 1], a[i]);
    }
    BIT bit(n);
    for (int i = 1; i < n; i++){
        bit.add(i, a[i] - a[i - 1]);
    }
    while (q--){
        int l, r; cin >> l >> r;
        long long u; cin >> u;
        ans -= val(bit.query(l - 1), bit.query(l));
        if (r + 1 < n)
            ans -= val(bit.query(r), bit.query(r + 1));
        bit.add(l, u);
        if (r + 1 < n)
            bit.add(r + 1, -u);
        ans += val(bit.query(l - 1), bit.query(l));
        if (r + 1 < n)
            ans += val(bit.query(r), bit.query(r + 1));
        cout << ans << '\n';
    }
    return 0;
}

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