Submission #1051586

#	Time	Username	Problem	Language	Result	Execution time	Memory
1051586		gagik_2007	Foehn Phenomena (JOI17_foehn_phenomena)	C++17	30 / 100	609 ms	19596 KiB

foehn_phenomena

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

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

#define ff first
#define ss second

ll ttt;
const ll INF=1e18;
const ll MOD=1e9+7;
const ll N=200007;
ll n,m,k;
ll t[4*N];
ll lazy[8*N];
ll a[N];

void push(int v, int tl, int tr){
    if(lazy[v]!=0){
        int len=tr-tl+1;
        t[v]+=lazy[v]*len;
        lazy[2*v]+=lazy[v];
        lazy[2*v+1]+=lazy[v];
        lazy[v]=0;
    }
}

void build(int v, int tl, int tr){
    if(tl==tr){
        t[v]=a[tl];
    }
    else{
        int tm=(tl+tr)/2;
        build(2*v,tl,tm);
        build(2*v+1,tm+1,tr);
        t[v]=t[2*v]+t[2*v+1];
    }
}

void add(int v, int tl, int tr, int l, int r, ll vl){
    push(v,tl,tr);
    if(l>r)return;
    if(l==tl&&r==tr){
        lazy[v]+=vl;
        push(v,tl,tr);
    }
    else{
        int tm=(tl+tr)/2;
        add(2*v,tl,tm,l,min(r,tm),vl);
        push(v,tl,tr);
        add(2*v+1,tm+1,tr,max(tm+1,l),r,vl);
        push(v,tl,tr);
        t[v]=t[2*v]+t[2*v+1];
    }
}

int getsum(int v, int tl, int tr, int l, int r){
    push(v,tl,tr);
    if(l>r)return 0;
    if(tl==l&&tr==r){
        return t[v];
    }
    else{
        int tm=(tl+tr)/2;
        push(v,tl,tr);
        return getsum(2*v,tl,tm,l,min(r,tm))+
            getsum(2*v+1,tm+1,tr,max(tm+1,l),r);
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    // freopen("Ainput.txt","r",stdin);
    // freopen("Aoutput.txt","w",stdout);
    ll s,t;
    cin>>n>>m>>s>>t;
    n++;
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    build(1,0,n-1);
    ll ans=0;
    for(int i=0;i<n-1;i++){
        if(a[i]<a[i+1]){
            ans-=s*(a[i+1]-a[i]);
        }
        else{
            ans+=t*(a[i]-a[i+1]);
        }
    }
    for(int i=0;i<m;i++){
        int l,r;
        ll w;
        cin>>l>>r>>w;
        a[l-1]=getsum(1,0,n-1,l-1,l-1);
        a[l]=getsum(1,0,n-1,l,l);
        // cout<<a[l-1]<<" "<<a[l]<<endl;
        // cout<<"OK"<<endl;
        if(r!=n-1){
            a[r]=getsum(1,0,n-1,r,r);
            a[r+1]=getsum(1,0,n-1,r+1,r+1);
            // cout<<a[r]<<" "<<a[r+1]<<endl;
        }
        if(a[l-1]<a[l]){
            ans+=s*(a[l]-a[l-1]);
        }
        else{
            ans-=t*(a[l-1]-a[l]);
        }
        if(r!=n-1){
            if(a[r]<a[r+1]){
                ans+=s*(a[r+1]-a[r]);
            }
            else{
                ans-=t*(a[r]-a[r+1]);
            }
        }
        add(1,0,n-1,l,r,w);
        a[l-1]=getsum(1,0,n-1,l-1,l-1);
        a[l]=getsum(1,0,n-1,l,l);
        // cout<<a[l-1]<<" "<<a[l]<<endl;
        // cout<<"OK"<<endl;
        if(r!=n-1){
            a[r]=getsum(1,0,n-1,r,r);
            a[r+1]=getsum(1,0,n-1,r+1,r+1);
            // cout<<a[r]<<" "<<a[r+1]<<endl;
        }
        if(a[l-1]<a[l]){
            ans-=s*(a[l]-a[l-1]);
        }
        else{
            ans+=t*(a[l-1]-a[l]);
        }
        if(r!=n-1){
            if(a[r]<a[r+1]){
                ans-=s*(a[r+1]-a[r]);
            }
            else{
                ans+=t*(a[r]-a[r+1]);
            }
        }
        cout<<ans<<endl;
    }
}

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