Submission #1258751

#	Time	Username	Problem	Language	Result	Execution time	Memory
1258751		khanhtt	Foehn Phenomena (JOI17_foehn_phenomena)	C++20	30 / 100	380 ms	12500 KiB

foehn_phenomena

#include <iostream>
using namespace std;
int n,q,A[200005];
long long s,t,st[800005],laz[800005],res=0;
void build(int id, int l, int r){
    if (l==r){
        st[id]=A[l];
        return;
    }
    int m=(l+r)>>1;
    build(id<<1,l,m);
    build(id<<1|1,m+1,r);
    st[id]=st[id<<1]+st[id<<1|1];
}
void fix(int id, int l, int r){
    if (!laz[id]) return;
    st[id]+=laz[id]*(r-l+1);
    if (l!=r){
        laz[id<<1]+=laz[id];
        laz[id<<1|1]+=laz[id];
    }
    laz[id]=0;
}
void update(int id, int l, int r, int u, int v, int val){
    fix(id,l,r);
    if (v<l || r<u) return;
    if (u<=l && r<=v){
        laz[id]+=val;
        fix(id,l,r);
        return;
    }
    int m=(l+r)>>1;
    update(id<<1,l,m,u,v,val);
    update(id<<1|1,m+1,r,u,v,val);
    st[id]=st[id<<1]+st[id<<1|1];
}
int get(int id, int l, int r, int i){
    fix(id,l,r);
    if (i<l || r<i) return 0;
    if (l==r) return st[id];
    int m=(l+r)>>1;
    return get(id<<1,l,m,i)+get(id<<1|1,m+1,r,i);
}
main(){
    ios::sync_with_stdio(0);
    cin.tie(nullptr);
    cin >> n >> q >> s >> t;
    for (int i=0; i<=n; i++){
        cin >> A[i];
        if (i==0) continue;
        if (A[i]>A[i-1]){
            res-=(A[i]-A[i-1])*s;
        }
        else{
            res+=(A[i-1]-A[i])*t;
        }
    }
    build(1,0,n);
    while (q--){
        int l,r,x; cin >> l >> r >> x;
        int beff=get(1,0,n,l-1),leff=get(1,0,n,l);
        if (leff>beff){
            res+=(leff-beff)*s;
        }
        else{
            res-=(beff-leff)*t;
        }
        if (r<n){
            int aeff=get(1,0,n,r+1),reff=get(1,0,n,r);
            if (aeff>=reff){
                res+=(aeff-reff)*s;
            }
            else{
                res-=(reff-aeff)*t;
            }
        }
        update(1,0,n,l,r,x);
        int bef=get(1,0,n,l-1),lef=get(1,0,n,l);
        if (lef>=bef){
            res-=(lef-bef)*s;
        }
        else{
            res+=(bef-lef)*t;
        }
        if (r<n){
            int aef=get(1,0,n,r+1),ref=get(1,0,n,r);
            if (aef>=ref){
                res-=(aef-ref)*s;
            }
            else{
                res+=(ref-aef)*t;
            }
        }
        cout << res << "\n";
    }
}

Compilation message (stderr)

foehn_phenomena.cpp:44:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   44 | main(){
      | ^~~~

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