Submission #1109551

#	Time	Username	Problem	Language	Result	Execution time	Memory
1109551		Zero_OP	Foehn Phenomena (JOI17_foehn_phenomena)	C++14	100 / 100	129 ms	13896 KiB

foehn_phenomena

#include <bits/stdc++.h>

using namespace std;

struct Fenwick{
    vector<long long> bit;
    Fenwick(int n) : bit(n + 1, 0) {}

    void update(int id, long long val){
        for(; id < (int)bit.size(); id += id & (-id)){
            bit[id] += val;
        }
    }

    void updateRange(int l, int r, long long delta){
        update(l, delta);
        update(r + 1, -delta);
    }

    long long query(int id){
        long long sum = 0;
        for(; id > 0; id -= id & (-id)){
            sum += bit[id];
        }
        return sum;
    }
};

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

    int N, Q, S, T;

    cin >> N >> Q >> S >> T;
    vector<int> a(N + 1);
    for(int i = 0; i <= N; ++i){
        cin >> a[i];
    }

    long long cur = 0;
    vector<long long> diff(N + 1);
    for(int i = 1; i <= N; ++i){
        diff[i] = abs(a[i] - a[i - 1]);
        cur += (a[i - 1] < a[i] ? -S : +T) * diff[i];
    }

    Fenwick ft(N + 1);

    auto cost = [&](int i){
        long long pre = a[i - 1] + ft.query(i - 1), cur = a[i] + ft.query(i);
        long long delta = abs(cur - pre);
        if(pre < cur) delta *= -S;
        else delta *= T;
        return delta;
    };

    while(Q--){
        int l, r; long long x;
        cin >> l >> r >> x;

        cur -= cost(l);
        if(r < N) cur -= cost(r + 1);

        ft.updateRange(l, r, x);

        cur += cost(l);
        if(r < N) cur += cost(r + 1);

        cout << cur << '\n';
    }

    return 0;
}

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