Submission #1345138

#TimeUsernameProblemLanguageResultExecution timeMemory
1345138nathlol2Foehn Phenomena (JOI17_foehn_phenomena)C++20
100 / 100
64 ms7292 KiB
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2e5 + 5;
int n, ans, q, s, t, a[N];

struct fenwick{
    int bit[N];
    void upd(int i, int x){
        for(; i<N; i += i & -i) bit[i] += x;
    }
    int qry(int i){
        int res = 0;
        for(; i>0; i -= i & -i) res += bit[i];
        return res;
    }
}fw;

int f(int x, int y){
    if(y > x) return s * (x - y);
    return t * (x - y);
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n >> q >> s >> t;
    for(int i = 0;i<=n;i++) cin >> a[i];
    for(int i = 1;i<=n;i++){
        fw.upd(i, a[i] - a[i - 1]);
        ans += f(a[i - 1], a[i]);
    }
    while(q--){
        int l, r, x; cin >> l >> r >> x;
        if(r != n){
            ans -= f(fw.qry(r), fw.qry(r + 1));
            ans += f(fw.qry(r) + x, fw.qry(r + 1));
        }
        ans -= f(fw.qry(l - 1), fw.qry(l));
        ans += f(fw.qry(l - 1), fw.qry(l) + x);
        if(r != n) fw.upd(r + 1, -x);
        fw.upd(l, x);
        cout << ans << '\n';
    }
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...