Submission #998521

#	Time	Username	Problem	Language	Result	Execution time	Memory
998521		spensa	Foehn Phenomena (JOI17_foehn_phenomena)	C++14	100 / 100	92 ms	14672 KiB

foehn_phenomena

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pb push_back
#define pii pair<int,int>
#define FOR(i, a, b) for(int i=(signed)(a); i<=(signed)(b); i++)
#define F0R(i, a) for(int i=(0); i<(signed)(a); i++)

const int MXN = 2e5 + 10;
ll arr[MXN] = {0};
ll updL[MXN] = {0};
ll updR[MXN] = {0};

int main(){
    //faster io
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    ll N, Q, S, T;
    cin>>N>>Q>>S>>T;

    ll ans = 0;
    cin>>arr[0]; //always zero
    FOR(i, 1, N){
        cin>>arr[i];
        if(arr[i-1]<arr[i]){
            ans -= S * abs(arr[i]-arr[i-1]);
        }
        else{
            ans += T * abs(arr[i]-arr[i-1]);
        }
    }

    // FOR(i, 1, N) cout<<arr[i]<<" ";
    // cout<<"\n";

    // cout<<"ans="<<ans<<"!";
    ll L, R, X;
    while(Q--){
        cin>>L>>R>>X;
        // upd[L]+=X;
        if(((arr[L-1]+updR[L-1])<(arr[L]+updL[L])) &&
            ((arr[L-1]+updR[L-1])>=(arr[L]+updL[L]+X)))
        {
            ans += (S * abs((arr[L-1]+updR[L-1])-(arr[L]+updL[L])));
            ans += (T * abs((arr[L-1]+updR[L-1])-(arr[L]+updL[L]+X)));
        }
        else if(((arr[L-1]+updR[L-1])>=(arr[L]+updL[L])) &&
            ((arr[L-1]+updR[L-1])<(arr[L]+updL[L]+X)))
        {
            ans-= (T * abs((arr[L-1]+updR[L-1])-(arr[L]+updL[L])));
            ans-= (S * abs((arr[L-1]+updR[L-1])-(arr[L]+updL[L]+X)));
        }
        else{
            if((arr[L-1]+updR[L-1])<(arr[L]+updL[L]+X)) ans -= (S*X);
            else ans -= (T*X);
        }

        if(R==N){
            updL[L]+=X;
            // if(L!=R) 
            updR[R]+=X;
            cout<<ans<<"\n";
            continue;
        }

        if(((arr[R]+updR[R])<(arr[R+1]+updL[R+1])) &&
            ((arr[R]+updR[R]+X)>=(arr[R+1]+updL[R+1])))
        {
            ans+= (S * abs((arr[R]+updR[R])-(arr[R+1]+updL[R+1])));
            ans+= (T * abs((arr[R]+updR[R]+X)-(arr[R+1]+updL[R+1])));
        }
        else if(((arr[R]+updR[R])>=(arr[R+1]+updL[R+1])) &&
            ((arr[R]+updR[R]+X)<(arr[R+1]+updL[R+1])))
        {
            ans-= (T * abs((arr[R]+updR[R])-(arr[R+1]+updL[R+1])));
            ans-= (S * abs((arr[R]+updR[R]+X)-(arr[R+1]+updL[R+1])));
        }
        else{
            if((arr[R]+updR[R]+X)<(arr[R+1]+updL[R+1])) ans += (S*X);
            else ans += (T*X);
            
        }

        updL[L]+=X;
        // if(L!=R) 
        updR[R]+=X;
        cout<<ans<<"\n";
    }

}

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