Submission #926542

#	Time	Username	Problem	Language	Result	Execution time	Memory
926542		SuPythony	Foehn Phenomena (JOI17_foehn_phenomena)	C++17	100 / 100	517 ms	17744 KiB

foehn_phenomena

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int MAX=2*1e5+7;
vector<ll> bit1(MAX,0);
vector<ll> bit2(MAX,0);
vector<ll> incr(MAX,0);
vector<ll> decr(MAX,0);
ll n;

void upd1(int pos, ll val) {
    while (pos<=n) {
        bit1[pos]+=val;
        pos+=pos&-pos;
    }
}

void upd2(int pos, ll val) {
    while (pos<=n) {
        bit2[pos]+=val;
        pos+=pos&-pos;
    }
}

ll query1(int pos) {
    ll ans=0;
    while (pos>0) {
        ans+=bit1[pos];
        pos-=pos&-pos;
    }
    return ans;
}

ll query2(int pos) {
    ll ans=0;
    while (pos>0) {
        ans+=bit2[pos];
        pos-=pos&-pos;
    }
    return ans;
}

int main() {
    ll q,s,t; cin>>n>>q>>s>>t;
    vector<ll> a(n+1);
    for (int i=0; i<=n; i++) cin>>a[i];
    for (int i=1; i<=n; i++) {
        if (a[i]>a[i-1]) {
            incr[i]=a[i]-a[i-1];
            upd1(i,incr[i]);
        }
        else {
            decr[i]=a[i-1]-a[i];
            upd2(i,decr[i]);
        }
    }
    while (q--) {
        ll l,r,x; cin>>l>>r>>x;
        if (incr[l]!=0) {
            if (incr[l]+x>=0) {
                upd1(l,x);
                incr[l]+=x;
            }
            else {
                upd2(l,-x-incr[l]);
                decr[l]+=-x-incr[l];
                upd1(l,-incr[l]);
                incr[l]+=-incr[l];
            }
        } else {
            x=-x;
            if (decr[l]+x>=0) {
                upd2(l,x);
                decr[l]+=x;
            }
            else {
                upd1(l,-x-decr[l]);
                incr[l]+=-x-decr[l];
                upd2(l,-decr[l]);
                decr[l]+=-decr[l];
            }
            x=-x;
        }
        if (r<n) {
            x=-x;
            l=r+1;
            if (incr[l]!=0) {
                if (incr[l]+x>=0) {
                    upd1(l,x);
                    incr[l]+=x;
                }
                else {
                    upd2(l,-x-incr[l]);
                    decr[l]+=-x-incr[l];
                    upd1(l,-incr[l]);
                    incr[l]+=-incr[l];
                }
            } else {
                x=-x;
                if (decr[l]+x>=0) {
                    upd2(l,x);
                    decr[l]+=x;
                }
                else {
                    upd1(l,-x-decr[l]);
                    incr[l]+=-x-decr[l];
                    upd2(l,-decr[l]);
                    decr[l]+=-decr[l];
                }
                x=-x;
            }
        }
        cout<<t*query2(n)-s*query1(n)<<"\n";
    }
    return 0;
}

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