Submission #51005

#	Time	Username	Problem	Language	Result	Execution time	Memory
51005		Diuven	Foehn Phenomena (JOI17_foehn_phenomena)	C++11	100 / 100	242 ms	168092 KiB

foehn_phenomena

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
typedef long long lld;
const int MX=200010, inf=2e9;

int n, q, s, t;
lld now;
lld tree[MX];

void upt(int r, int val){
    for(; r>0; r-=r&(-r))
        tree[r]+=val;
}
void upt(int l, int r, int x){
    upt(r,x); upt(l-1, -x);
}
lld val(int pos){
    lld ans=0;
    for(; 0<pos && pos<=n; pos+=pos&(-pos))
        ans+=tree[pos];
    return ans;
}

inline lld f(lld a, lld b){
    return (a-b) * (a>b ? t : s);
}

void debug(){
    return;
    cout<<"DEBUG!!\n";
    for(int i=1; i<=n; i++) cout<<val(i)<<' ';
    cout<<'\n';
}

int main(){
    ios::sync_with_stdio(0); cin.tie(0);
    cin>>n>>q>>s>>t;
    for(int i=0; i<=n; i++){
        int h; cin>>h;
        upt(i,i,h);
        lld prv=val(i-1);
        now += f(prv, h);
        debug();
    }
    for(int i=1; i<=q; i++){
        int l, r, x;
        cin>>l>>r>>x;
        lld ll = val(l-1), rr = val(r+1);
        lld lr1 = val(l), rl1 = val(r);
        upt(l,r,x);
        lld lr2 = val(l), rl2 = val(r);
        if(r<n) now += f(rl2, rr) - f(rl1, rr);
        now += f(ll, lr2) - f(ll, lr1);
        cout<<now<<'\n';
    }
    return 0;
}

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