Submission #670443

#	Time	Username	Problem	Language	Result	Execution time	Memory
670443		Mahdi	Foehn Phenomena (JOI17_foehn_phenomena)	C++17	100 / 100	122 ms	6412 KiB

foehn_phenomena

#include<bits/stdc++.h>
using namespace std;
#define all(v) v.begin(), v.end()
#define F first
#define S second
typedef long long ll;
typedef pair<int, int> pii;
const int N=2e5+5;
int n, q, s, t, a[N];
ll ans;

struct fenwick{
    vector<ll>bit;

    void add(int i, int val){
        for(;i<=n;i|=(i+1))
            bit[i]+=val;
    }

    void add(int l, int r, int val){
        add(l, val);
        add(r, -val);
    }

    ll sum(int i){
        ll res=0;
        for(;i>=0;i=(i&(i+1))-1)
            res+=bit[i];
        return res;
    }
} A;

inline ll num(int i){
    return A.sum(i)+a[i];
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin>>n>>q>>s>>t;
    for(int i=0;i<=n;++i)
        cin>>a[i];
    for(int i=1;i<=n;++i){
        if(a[i]>a[i-1])
            ans-=1LL*(a[i]-a[i-1])*s;
        else
            ans+=1LL*(a[i-1]-a[i])*t;
    }
    A.bit.assign(n+1, 0);
    while(q--){
        int l, r, x;
        cin>>l>>r>>x;
        ll y=num(l-1), z=num(l);
        if(z>y)
            ans+=1LL*(z-y)*s;
        else
            ans-=1LL*(y-z)*t;
        z+=x;
        if(z>y)
            ans-=1LL*(z-y)*s;
        else
            ans+=1LL*(y-z)*t;
        if(r<n){
            y=num(r);z=num(r+1);
            if(z>y)
                ans+=1LL*(z-y)*s;
            else
                ans-=1LL*(y-z)*t;
            y+=x;
            if(z>y)
                ans-=1LL*(z-y)*s;
            else
                ans+=1LL*(y-z)*t;
        }
        A.add(l, r+1, x);
        cout<<ans<<'\n';
    }
}

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