제출 #170648

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
170648		mdn2002	Foehn Phenomena (JOI17_foehn_phenomena)	C++14	30 / 100	1042 ms	10212 KiB

foehn_phenomena

#include<bits/stdc++.h>
using namespace std;
const long long mod=998244353;
long long n,q,s,t,tree[800005],lazy[800005],ans;
void up(int nod,int l,int r,int x,int y,long long val)
{
    if(lazy[nod]!=0)
    {
        tree[nod]+=(r-l+1)*lazy[nod];
        if(l!=r)
        {
            lazy[nod*2]+=lazy[nod];
            lazy[nod*2+1]+=lazy[nod];
        }
        lazy[nod]=0;
    }
    if(r<x||y<l)return;
    if(x<=l&&r<=y)
    {
        tree[nod]+=(r-l+1)*val;
        if(l!=r)
        {
            lazy[nod*2]+=val;
            lazy[nod*2+1]+=val;
        }
        return;
    }
    int mid=(l+r)/2;
    up(nod*2,l,mid,x,y,val);
    up(nod*2+1,mid+1,r,x,y,val);
    tree[nod]=tree[nod*2]+tree[nod*2+1];
}
long long qu(int nod,int l,int r,int x)
{
    if(lazy[nod]!=0)
    {
        tree[nod]+=(r-l+1)*lazy[nod];
        if(l!=r)
        {
            lazy[nod*2]+=lazy[nod];
            lazy[nod*2+1]+=lazy[nod];
        }
        lazy[nod]=0;
    }
    if(x<l||r<x)return 0;
    if(l==r)return tree[nod];
    int mid=(l+r)/2;
    if(l<=x&&x<=mid)return qu(nod*2,l,mid,x);
    return qu(nod*2+1,mid+1,r,x);
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    //freopen(".in","r",stdin);
    //freopen(".out","w",stdout);
    cin>>n>>q>>s>>t;
    long long b;
    cin>>b;
    up(1,0,n,0,0,b);
    for(int i=0;i<n;i++)
    {
        long long a;
        cin>>a;
        long long dif=b-a;
        if(dif>=0)ans+=dif*t;
        else ans+=dif*s;
        up(1,0,n,i+1,i+1,a);
        b=a;
    }
    while(q--)
    {
        int l,r;
        long long x;
        cin>>l>>r>>x;
        long long oa=qu(1,0,n,l);
        long long ob=qu(1,0,n,r);
        up(1,0,n,l,r,x);
        long long a=oa+x;
        long long b=ob+x;
        long long c=qu(1,0,n,l-1);
        long long d=qu(1,0,n,r+1);
        if(l>0)
        {
            long long dif=c-oa;
            if(dif>=0)ans-=dif*t;
            else ans-=dif*s;
            dif=c-a;
            if(dif>=0)ans+=dif*t;
            else ans+=dif*s;
        }
        if(r<n)
        {
            long long dif=ob-d;
            if(dif>=0)ans-=dif*t;
            else ans-=dif*s;
            dif=b-d;
            if(dif>=0)ans+=dif*t;
            else ans+=dif*s;
        }
        cout<<ans<<endl;
    }
}

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