제출 #1289726

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1289726		kubinsgk8	Foehn Phenomena (JOI17_foehn_phenomena)	C++20	100 / 100	317 ms	13820 KiB

foehn_phenomena

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

//---------------------------------------------
const int N=2e5+2;

long long n, q, s, t;

long long node[N*4];
long long lazy[N*4];

long long a[N];
long long ans=0;

//---------------------------------------------


void update_lazy(int goc, int l, int r)
{
    node[goc]+=lazy[goc];

    if(l!=r)
    {
        lazy[goc*2]+=lazy[goc];
        lazy[goc*2+1]+=lazy[goc];
    }

    lazy[goc]=0;

}

void build(int goc, int l, int r)
{
    if(l==r)
    {
        node[goc]=a[l];
        return;
    }

    int mid=(l+r)>>1;

    build(goc*2, l , mid);
    build(goc*2+1, mid+1, r);
    node[goc]=node[goc*2]+node[goc*2+1];

}




void update(int goc, int l, int r, int trai, int phai, long long value)
{
    update_lazy(goc, l, r);

    if(l>phai or r<trai)return ;

    if(trai<=l and r<=phai)
    {
        lazy[goc]+=value;

        update_lazy(goc, l, r);

        return;
    }

    int mid=(l+r)>>1;

    update(goc*2, l, mid, trai, phai, value);

    update(goc*2+1, mid+1, r, trai, phai, value);

    node[goc]=node[goc*2]+node[goc*2+1];


}



long long get(int goc, int l, int r, int pos)
{
    update_lazy(goc, l, r);

    if(pos<l or pos>r)return 0;

    if(l==r)return node[goc];

    int mid=(l+r)>>1;

    return get(goc*2, l, mid, pos)+get(goc*2+1, mid+1, r ,pos);



}








int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);

    cin>>n>>q>>s>>t;

    s*=-1;
    n++;


    for(int i=1; i<=n; i++)cin>>a[i];

    for(int i=1; i<n; i++)
    {
        if(a[i]<a[i+1])ans+=(a[i+1]-a[i])*s;
        else ans+=(a[i]-a[i+1])*t;
    }


    build(1, 1, n);


    while(q--)
    {
        int l, r, x;

        cin>>l>>r>>x;

        l++, r++;

        long long h_l=get(1, 1, n, l-1);
        long long h_r=get(1, 1, n, r+1);

        long long h_trai=get(1, 1, n, l);
        long long h_phai=get(1, 1, n, r);

        if(h_l<h_trai)ans-=(h_trai-h_l)*s; else ans-=(h_l-h_trai)*t;

        if(r+1<=n)
        if(h_r>h_phai)ans-=(h_r-h_phai)*s; else ans-=(h_phai-h_r)*t;

        h_trai+=x; h_phai+=x;


        if(h_l<h_trai)ans+=(h_trai-h_l)*s; else ans+=(h_l-h_trai)*t;

        if(r+1<=n)
        if(h_r>h_phai)ans+=(h_r-h_phai)*s; else ans+=(h_phai-h_r)*t;

        update(1, 1, n, l, r, x);

        cout<<ans<<"\n";

    }

    return 0;
}

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