Submission #931536

#	Time	Username	Problem	Language	Result	Execution time	Memory
931536		AnasAAF	Foehn Phenomena (JOI17_foehn_phenomena)	C++17	100 / 100	373 ms	30488 KiB

foehn_phenomena

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
#define float double
#define ld long double

ll N = 2e5+10;
ll n, S, T, Q;
vector<ll>v(N);
vector<ll>tree(6*N);
vector<ll>lazy(6*N);

void update(int node, ll l, ll r, ll ql, ll qr, ll val){
    //cout<<node<<" "<<l<<" "<<r<<" "<<ql<<" "<<qr<<" "<<val<<endl;
    if(lazy[node]!=0){
        tree[node]+=lazy[node]*(r-l+1);
        if(l!=r){
            lazy[node*2]+=lazy[node];
            lazy[node*2+1]+=lazy[node];
        }
        lazy[node]=0;
    }
    if(ql>r || qr<l)return;
    if(ql<=l && qr>=r){
        tree[node]+=(val*(r-l+1));
        //cout<<"BINGO"<<endl;
        if(l!=r){
            lazy[node*2]+=val;
            lazy[node*2+1]+=val;
        }
        return;
    }
    ll mid = (l+r)/2;
    update(node*2, l, mid, ql, qr, val);
    update(node*2+1, mid+1, r, ql, qr, val);
    return;
}

ll get(int node, ll l, ll r, ll ind){
    if(lazy[node]!=0){
        tree[node]+=lazy[node]*(r-l+1);
        if(l!=r){
            lazy[node*2]+=lazy[node];
            lazy[node*2+1]+=lazy[node];
        }
        lazy[node]=0;
    }
    if(l==r)return tree[node];
    int mid = (l+r)/2;
    if(ind<=mid)return get(node*2, l, mid, ind);
    else return get(node*2+1, mid+1, r, ind);
}

int main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>n>>Q>>S>>T;
    for(int i=0;i<=n;i++)cin>>v[i];
    ll nxp2 = (1<<(ll)ceil(log2(double(N))));
    for(int i=0;i<=n;i++){
        update(1, 0, nxp2, i, i, v[i]);
    }
    ll ans(0);
    for(int i=0;i<n;i++){
        if(v[i]<v[i+1])ans-=(v[i+1]-v[i])*S;
        else ans+=(v[i]-v[i+1])*T;
    }
    while(Q--){
        ll l, r, x;cin>>l>>r>>x;
        ll bl = get(1, 0, nxp2, l-1);
        ll al = get(1, 0, nxp2, l);
        ll br, ar;
        br = get(1, 0, nxp2, r);
        if(r!=n)ar = get(1, 0, nxp2, r+1);

        if(bl<al)ans+=(al-bl)*S;
        else ans-=(bl-al)*T;
        if(r!=n){
            if(br<ar)ans+=(ar-br)*S;
            else ans-=(br-ar)*T;
        }

        update(1, 0, nxp2, l, r, x);
        //for(int i=0;i<=n;i++)cout<<get(1, 0, nxp2, i)<<" ";
        //cout<<endl;

        bl = get(1, 0, nxp2, l-1);
        al = get(1, 0, nxp2, l);
        br = get(1, 0, nxp2, r);
        if(r!=n)ar = get(1, 0, nxp2, r+1);
        if(bl<al)ans-=(al-bl)*S;
        else ans+=(bl-al)*T;
        if(r!=n){
            if(br<ar)ans-=(ar-br)*S;
            else ans+=(br-ar)*T;
        }
        cout<<ans<<endl;
    }

    return 0;
}

Compilation message (stderr)

foehn_phenomena.cpp: In function 'int main()':
foehn_phenomena.cpp:80:26: warning: 'ar' may be used uninitialized in this function [-Wmaybe-uninitialized]
   80 |             else ans-=(br-ar)*T;
      |                       ~~~^~~~

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