Submission #993157

#	Time	Username	Problem	Language	Result	Execution time	Memory
993157		Nu_Pogodi	Foehn Phenomena (JOI17_foehn_phenomena)	C++17	100 / 100	595 ms	17236 KiB

foehn_phenomena

#include<bits/stdc++.h>
#define int long long
#define fr first
#define sc second
#define pow powl
using namespace std;
const int MAX = 2e5+5;
const int MOD = 1e9+7;
const int MIX = 1e15+9;
int cold,hot,sum=0;
int bl[MAX];
struct tree{
    int sz=1;
    vector<int> vec;
    void sout(){
        for(auto i : vec){
            cout<<i<<' ';
        }
    }
    void full(int n){
        while(sz<n){
            sz*=2;
        }
        vec.assign(sz*2-1,0);
    }
    void add(int L, int R, int v){
        add(L, R, v, 0, sz-1, 0);
    }
    void add(int L, int R, int v, int lr, int rl, int x){
        if(lr>=L && rl<=R){
            vec[x]+=v;
            return;
        }
        if(rl<L || lr>R){
            return;
        }
        int mid=(rl+lr)/2;
        add(L, R, v, mid+(rl+lr)%2, rl, x*2+2);
        add(L, R, v, lr, mid, x*2+1);
    }
    int take(int ps){
        return take(ps, 0, sz, 0, 0);
    }
    int take(int ps, int lr, int rl, int x, int op){
        if(rl-lr==1){
            return vec[x]+op;
        }
        int mid=(rl+lr)/2;
        if(mid<=ps){
            return take(ps, mid+(rl+lr)%2, rl, x*2+2, op+vec[x]);
        }
        else{
            return take(ps, lr, mid, x*2+1, op+vec[x]);
        }
    }
};
void solve(){
    tree tr;
    int n,q;
    cin>>n>>q>>cold>>hot;
    tr.full(n+1);
    int a[n+1];
    for(int i=0;i<=n;i++){
        cin>>a[i];
        tr.add(i,i,a[i]);
    }
    for(int i=1;i<=n;i++){
        if(a[i]>a[i-1]){
            sum-=(a[i]-a[i-1])*cold;
            bl[i-1]-=(a[i]-a[i-1])*cold;
        }
        else{
            sum+=(a[i-1]-a[i])*hot;
            bl[i-1]=(a[i-1]-a[i])*hot;
        }
    }
    // cout<<sum<<endl;
    // tr.sout();
    while(q--){
        int l, r, u;
        cin>>l>>r>>u;
        tr.add(l, r, u);
        if(l!=0){
            int x1=tr.take(l-1),x2=tr.take(l);
            // cout<<x1<<' '<<x2<<' ';
            sum-=bl[l-1];
            if(x2>x1){
                bl[l-1]=-(x2-x1)*cold;
            }
            else{
                bl[l-1]=(x1-x2)*hot;
            }
            sum+=bl[l-1];
        }
        if(r!=n){
            int x1=tr.take(r),x2=tr.take(r+1);
            // cout<<x1<<' '<<x2<<' ';
            sum-=bl[r];
            if(x2>x1){
                bl[r]=-(x2-x1)*cold;
            }
            else{
                bl[r]=(x1-x2)*hot;
            }
            sum+=bl[r];
        }
        cout<<sum<<endl;
    }

}
signed main()
{
    int t=1;
    // cin>>t;
    while(t --){
        solve();
        // cout<<endl;    
    }
}

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