Submission #977407

#	Time	Username	Problem	Language	Result	Execution time	Memory
977407		Kalata_56	Foehn Phenomena (JOI17_foehn_phenomena)	C++14	100 / 100	279 ms	17212 KiB

foehn_phenomena

#include<bits/stdc++.h>
using namespace std;
long long mas[200001];
long long tree[1000001];
void update(long long in,long long l,long long r,long long ot,long long du,long long k){
    if(l>=ot && r<=du){
        tree[in]+=k;
        return ;
    }
    long long mid=(l+r)/2;
    if(ot<=mid){
        update(in*2,l,mid,ot,du,k);
    }if(du>mid){
        update(in*2+1,mid+1,r,ot,du,k);
    }
    return ;
}
long long ans(long long in,long long l,long long r,long long koj){
    if(l==r){
        return mas[l]+tree[in];
    }
    long long mid=(l+r)/2;
    long long otg;
    if(koj<=mid){
        otg=ans(in*2,l,mid,koj);
    }else{
        otg=ans(in*2+1,mid+1,r,koj);
    }
    return otg+tree[in];
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
    long long N,Q,S,T;
    cin>>N>>Q>>S>>T;
    long long nach=0;
    cin>>mas[0];
    for(long long i=1;i<=N;i++){
        cin>>mas[i];
        if(mas[i-1]<mas[i]){
            nach-=(S*(mas[i]-mas[i-1]));
        }else{
            nach+=(T*(mas[i-1]-mas[i]));
        }
    }
    //cout<<nach<<"\n";
    long long l,r,x;
    for(long long i=0;i<Q;i++){
        cin>>l>>r>>x;
        if(l!=0){
            long long a1=ans(1,0,N,l-1);
            long long a2=ans(1,0,N,l);
            if(a1<a2){
                nach+=(S*(a2-a1));
            }else{
                nach-=(T*(a1-a2));
            }
        }if(r!=N){
            long long a1=ans(1,0,N,r);
            long long a2=ans(1,0,N,r+1);
            if(a1<a2){
                nach+=(S*(a2-a1));
            }else{
                nach-=(T*(a1-a2));
            }
        }
        update(1,0,N,l,r,x);
        if(l!=0){
            long long a1=ans(1,0,N,l-1);
            long long a2=ans(1,0,N,l);
            if(a1<a2){
                nach-=(S*(a2-a1));
            }else{
                nach+=(T*(a1-a2));
            }
        }if(r!=N){
            long long a1=ans(1,0,N,r);
            long long a2=ans(1,0,N,r+1);
            if(a1<a2){
                nach-=(S*(a2-a1));
            }else{
                nach+=(T*(a1-a2));
            }
        }
        cout<<nach<<"\n";
    }

    return 0;
}

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