Submission #43679

#	Time	Username	Problem	Language	Result	Execution time	Memory
43679		dqhungdl	Foehn Phenomena (JOI17_foehn_phenomena)	C++14	100 / 100	554 ms	169624 KiB

foehn_phenomena

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

int64_t n,T,s,t,res=0,a[200005],tree[200005];

void Update(int64_t idx,int64_t data)
{
    while(idx<=n)
    {
        tree[idx]+=data;
        idx+=idx&-idx;
    }
}

int64_t Query(int64_t idx)
{
    int64_t rs=0;
    while(idx>0)
    {
        rs+=tree[idx];
        idx-=idx&-idx;
    }
    return rs;
}

void Updateres(int64_t l,int64_t r,int64_t type)
{
    int64_t t1,t2;
    if(l==1)
        t1=0;
    else
        t1=Query(l-1);
    t2=Query(l);
    if(t1<t2)
        res-=s*(t2-t1)*type;
    else
        res+=t*(t1-t2)*type;
    if(r<n)
    {
        t1=Query(r);
        t2=Query(r+1);
        if(t1<t2)
            res-=s*(t2-t1)*type;
        else
            res+=t*(t1-t2)*type;
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    //freopen("TEST.INP","r",stdin);
    cin>>n>>T>>s>>t;
    for(int64_t i=0; i<=n; i++)
    {
        cin>>a[i];
        if(i>0)
        {
            Update(i,a[i]);
            Update(i+1,-a[i]);
        }
    }
    for(int64_t i=1; i<=n; i++)
        if(a[i-1]<a[i])
            res-=s*(a[i]-a[i-1]);
        else
            res+=t*(a[i-1]-a[i]);
    int64_t l,r,val;
    while(T--)
    {
        cin>>l>>r>>val;
        Updateres(l,r,-1);
        Update(l,val);
        Update(r+1,-val);
        Updateres(l,r,1);
        cout<<res<<"\n";
    }
}

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