Submission #1273799

#	Time	Username	Problem	Language	Result	Execution time	Memory
1273799		ducky	Foehn Phenomena (JOI17_foehn_phenomena)	C++20	100 / 100	110 ms	7740 KiB

foehn_phenomena

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<ll, ll>;
using piii = pair<ll, pii>;
#define fi first 
#define se second
#define pb push_back
 
const ll INF = 1e9, mod = 1e9+7, mxn = 2e5+99;
ll N, M, K, S, T;

ll a[mxn], bit[mxn];

void upd(ll x, ll y){
    for(; x<mxn; x+=x&(-x)) bit[x] += y;
}
ll que(ll x){
    ll res = 0;
    for(; x>0; x-=x&(-x))res+=bit[x];
    return res;
}

void solve(){
    cin >> N >> M >> S >> T;
    for(int i=0; i<=N; i++)cin >> a[i];
    ll ans = 0;
    for(int i=1; i<=N; i++){
        if(a[i-1]-a[i] < 0){
            ans -= (a[i]-a[i-1])*S;
        }else {
            ans += (a[i-1]-a[i])*T;
        }
    }
    while(M--){
        ll l, r, x;
        cin >> l >> r >> x;

        ll l1 = que(l), l2 = que(l-1);
        if(a[l-1]+l2 - (a[l]+l1) < 0)ans += S * (a[l]+l1 -(a[l-1]+l2));
        else ans -= T * (a[l-1]+l2 - (a[l]+l1));

        if(r != N){
            ll r1 = que(r), r2 = que(r+1);
            if((a[r]+r1) - (a[r+1]+r2)< 0)ans += S * ((a[r+1]+r2) - (a[r]+r1));
            else ans -= T * ((a[r]+r1) - (a[r+1]+r2));
        }
        upd(l, x); upd(r+1, -x);

        l1 = que(l), l2 = que(l-1);
        if(a[l-1]+l2 - (a[l]+l1) < 0)ans -= S * (a[l]+l1 -(a[l-1]+l2));
        else ans += T * (a[l-1]+l2 - (a[l]+l1));

        if(r != N){
            ll r1 = que(r), r2 = que(r+1);
            if((a[r]+r1) - (a[r+1]+r2)< 0)ans -= S * ((a[r+1]+r2) - (a[r]+r1));
            else ans += T * ((a[r]+r1) - (a[r+1]+r2));
        }

        cout << ans << "\n";
    }
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    // int tc; cin >> tc; while(tc--)
    solve();
    return 0;
}

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