Submission #33278

#	Time	Username	Problem	Language	Result	Execution time	Memory
33278		Kanvie	Foehn Phenomena (JOI17_foehn_phenomena)	C++14	30 / 100	366 ms	17800 KiB

foehn_phenomena

#include<bits/stdc++.h>
using namespace std;
int x, y, n, q;
long long z, s, t, a[200001], f[800001], tg[200001], lazy[800001], ans;
long long cal(int i)
{
    return t*max(0ll,a[i-1]-a[i])-s*max(0ll,a[i]-a[i-1]);
}
void init(int k, int l, int r)
{
    if(l>r)return;
    if(l==r)
    {
        f[k]=a[l];
        return;
    }
    int mid=(l+r)/2;
    init(2*k,l,mid);
    init(2*k+1,mid+1,r);
    f[k]=max(f[2*k],f[2*k+1]);
}
void dolazy(int k, int l, int r)
{
    if(lazy[k]==0)return;
    f[k]+=lazy[k];
    if(l!=r)
    {
        lazy[2*k]+=lazy[k];
        lazy[2*k+1]+=lazy[k];
    }
    lazy[k]=0;
}
void upd(int k, int l, int r, int L, int R, long long x)
{
    dolazy(k,l,r);
    if(l>r||L>R||R<l||L>r)return;
    if(L<=l&&r<=R)
    {
        f[k]+=x;
        if(l!=r)
        {
            lazy[2*k]+=x;
            lazy[2*k+1]+=x;
        }
        return;
    }
    int mid=(l+r)/2;
    upd(2*k,l,mid,L,R,x);
    upd(2*k+1,mid+1,r,L,R,x);
    f[k]=max(f[2*k],f[2*k+1]);
}
long long gets(int k, int l, int r, int vt)
{
    dolazy(k,l,r);
    if(l>r||vt>r||vt<l)return 0ll;
    if(l==r)return f[k];
    int mid=(l+r)/2;
    return gets(2*k,l,mid,vt)+gets(2*k+1,mid+1,r,vt);
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin>>n>>q>>s>>t;
    for(int i=0;i<=n;++i)
    {
        cin>>a[i];
        if(i>=1)
        {
            tg[i]=cal(i);
            ans+=tg[i];
        }
    }
    init(1,1,n);
    while(q--)
    {
        cin>>x>>y>>z;
        upd(1,1,n,x,y,z);
        a[x]=gets(1,1,n,x);
        a[x-1]=gets(1,1,n,x-1);
        ans+=cal(x)-tg[x];
        tg[x]=cal(x);
        if(y!=n)
        {
            a[y]=gets(1,1,n,y);
            a[y+1]=gets(1,1,n,y+1);
            ans+=cal(y+1)-tg[y+1];
            tg[y+1]=cal(y+1);
        }
        cout<<ans<<"\n";
    }
}

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